Here are my solutions for the two INOI 2011 questions... (Indian National Olympiad in Informatics conducted by IARCS Indian Association for Research in Computing Science for Google's search :P)
The first question was about how many right angled triangles are possible with the given set of points and with sides parallel to x and y axes.
Arrays required: a 2*N array (xy[2][N])to store the coordinates. Two 10^4 long arrays (X[10000] and Y[10000] to store the number of times an x-coordinate and y-coordinate appears.
Input: Go into the loop. Get the coordinate and store it in the first array. Add 1 to X[x-coordinate], 1 to Y[y-coordinate]
The trick: Now, for every given point just multiply (X[x]-1) and (Y[y]-1)
This works because if you think of the points really as it is plotted in a graph, you'll see that for one point as the vertex with the adjacent sides perpendicular, there are as many triangles possible as the product of the remaining points left horizontal to it, and remaining points left vertical to it.
Add this for all points and do that %10000
The second question involving dynamic programming needs a solution to be constructed from one of the problems already discussed in online contest archive.
We store the marks in the array marks[N]
Now the best score at marks[0] is the same.
from marks[1] onwards, the best score is the maximum of (marks[1] alone),(best[i-1]+marks[1]),(best[i-1] dropping marks[i])
In the last case, when we drop marks[i], we must add one mark which we previously dropped to get the best mark.
Now, the trick in this is to store a best negative mark value for every i-1 so that if i is negative too, we can find dropping which is better. (where, by best negative, I mean the one closest to zero.. Because the one farthest from zero needs to be dropped.)
so we compare the best negative and marks[i] (obviously when marks[i] is negative) and keeps the one closest to zero, drops the other...
we must keep the count of K that is left. And we must also remember to restore K to maximum when we can best [i-1] is the same as marks[i] and they're both negative (or zero).
Both of the questions were particularly easy, if you thought like me. All the best for your results.
The first question was about how many right angled triangles are possible with the given set of points and with sides parallel to x and y axes.
Arrays required: a 2*N array (xy[2][N])to store the coordinates. Two 10^4 long arrays (X[10000] and Y[10000] to store the number of times an x-coordinate and y-coordinate appears.
Input: Go into the loop. Get the coordinate and store it in the first array. Add 1 to X[x-coordinate], 1 to Y[y-coordinate]
The trick: Now, for every given point just multiply (X[x]-1) and (Y[y]-1)
This works because if you think of the points really as it is plotted in a graph, you'll see that for one point as the vertex with the adjacent sides perpendicular, there are as many triangles possible as the product of the remaining points left horizontal to it, and remaining points left vertical to it.
Add this for all points and do that %10000
The second question involving dynamic programming needs a solution to be constructed from one of the problems already discussed in online contest archive.
We store the marks in the array marks[N]
Now the best score at marks[0] is the same.
from marks[1] onwards, the best score is the maximum of (marks[1] alone),(best[i-1]+marks[1]),(best[i-1] dropping marks[i])
In the last case, when we drop marks[i], we must add one mark which we previously dropped to get the best mark.
Now, the trick in this is to store a best negative mark value for every i-1 so that if i is negative too, we can find dropping which is better. (where, by best negative, I mean the one closest to zero.. Because the one farthest from zero needs to be dropped.)
so we compare the best negative and marks[i] (obviously when marks[i] is negative) and keeps the one closest to zero, drops the other...
we must keep the count of K that is left. And we must also remember to restore K to maximum when we can best [i-1] is the same as marks[i] and they're both negative (or zero).
Both of the questions were particularly easy, if you thought like me. All the best for your results.
your solution to the second problem as your formula for the ith best score (marks[i] alone),(best[i-1]+marks[1]),(best[i-1] dropping marks[i]) is wrong.
ReplyDeleteyour solution would fail for the following input:
1, -7, 3, -7, 6, -1, 10, -8, -8, 8.
hahhahaha! over confidence! :P
DeleteThe second solution is a total shit!
ReplyDelete