To get FREE & exclusive emails insert your email-id here

email id:

Tuesday, January 25, 2011

INOI 2011 Solutions

[Update on Jan 17, 2013: Some readers are reporting that the second solution is wrong. I cannot verify the same, but to be safe discretion is advised.]

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.

Friday, January 7, 2011

CBSE Class XII Date Sheet 2011 Class XII Time Table 2011 Board Examinations

The Date Sheet of CBSE Class XII 2011 was released today, on 7th, January,2011.
The main subjects are as follows:

All exams start at 10:30 AM. Subject codes in parenthesis.

Here's the copy of the original file CBSE uploaded (Click here):

Science (Biology) Stream
March 1, Tuesday: Physics (042)
March 7, Monday: Chemistry (043)
March 11, Friday: English Core (301)
March 14, Monday: Biology (044)
March 22, Tuesday: Mathematics (041)

Science (Computer) Stream 
March 1, Tuesday: Physics (042)
March 7, Monday: Chemistry (043)
March 11, Friday: English Core (301) March 22, Tuesday: Mathematics (041)
March 30, Wednesday: Computer Science (083)

Commerce Stream
March 3, Thursday: Business Studies (054)
March 9, Wednesday: Accountancy (055)
March 11, Friday: English Core (301)
March 16, Wednesday: Economics (030)
March 30, Wednesday: Informatics Practices (065)
Drop me a comment if anything is missing

Don't forget to visit and follow