INOI 2015 discussion.

discussion
dynamic-programming
inoi
inoi2015

#1

Hey Guys. How was INOI ?

For me , it was a tough 3 hours.
I did the second one for 100 but I fear that it might time out as it was taking 6 seconds ( I use JAVA) to work for the last subtask. The complexity was O(N LOG N).
I ran out of time while debugging my first program source code so I think it will fetch me a mere 10 points :(.

How was INOI for you all?


#2

It was pretty much the same for me, except that I solved the first one completely, but am not confident of my solution for the second one, and it might get a TLE for subtasks with N>4000. @animesh_f, what was your N log N solution for the second one?

Overall, I feel I could have done better, had I not wasted half an hour in debugging the first one (freakish 1-indexed arrays :frowning: )


#3

I completely messed up this one. Wasted 2.5 hours on the first problem getting nowhere, the program always giving wrong answers (I probably messed up the recursions…). Coded the second problem with this algorithm:

Make an array containing the positive divisors of n (doable in O(sqrt(n)) and sort them (O(d(n) log d(n)). Now let the number of aperiodic sequences of length m be given by f(m). Note that any periodic binary string of length n must have its minimal period dividing n, so there are a total of sum f(d), d|n, d<n periodic sequences of length n, and hence, 2^n - sum f(d), d|n, d<n aperiodic sequences of length n. We can compute this recursively (f(1)= 2) in O(d(n)^2).

This algorithm gave the correct answer for small integers (I had about 5 minutes left at this time). Then I quickly replaced the ints by long long ints, but didn’t get time to compile/debug my code finally. Just after exiting the hall, I recalled that I had made a map from int to int which stores the values of 2^n mod m for all n < 150000. Before submitting, I didn’t change this to a map from long long int to long long int, and also forgot to declare it outside int main. I guess I’m getting a 0 in this exam.

EDIT: Judging by the comment below, I still might have a chance! :smiley: Thanks, neotech!


#4

3 hours of self pity and loathing. We shalt strike back next yeart :’(


#5

I did only the first one it worked for all the subtasks probably it will fetch me 100 pts, but moreover i am very disappointed with my performance since this was my 2nd INOI and yes We shall strike back harder next year :slight_smile:


#6

Did Problem 2, which in my opinion was easier. Couldn’t finish debugging Problem 1. It was getting AC for the first 2 subtasks and failing on exactly 2 of the testdata in subtasks 3 and 4. So, hopefully, with a bit of luck, I should get something in {100, 110, 120, 130}.


#7

Hopefully my code will be considered as I use JAVA (it is generally 2x for JAVA) so I might end up with 110 points :smiley: , Fingers Crossed !


#8

I did problem 1, don’t know why you guys find that difficult. That was way more easier than the second problem. The second problem was way too mathematical(atleast it was hard for me…). Anyways, what do you guys think the cutoff will be ? I’ve only solved one problem, so I’ll probably be getting 100, unless I did some silly mistake in handling corner cases etc.


#9

Is it true? I’ll be banking on 2x for Java in that case


#10

What was the last year’s cut-off? What is the expected cut-off this year?


#11

since m was at most 10^8 you don’t need to worry about int overflow if you took care of the modulo operations properly


#12

100 last year. I guess same this year, we know of only 20 people getting >= 100 this year.


#13

How do you know that only 20 people are getting >=100 this year?


#14

I don’t, and that’s not what I said. I said that collectively we know of twenty people totally who have gotten more than hundred. There may be others that we don’t know about. Are you in the INOI 15 discussion group? If you are, click this: http://inoi15.discuss.codechef.com/questions/63431/how-did-you-solve-the-problems-in-todays-paper-whats-the-expected-cutoff/63538