You are not logged in. Please login at to post your questions!


INOI 2015 discussion.

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?

asked 31 Jan '15, 13:09

animesh_f's gravatar image

6★animesh_f ♦
accept rate: 9%

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 :( )


answered 31 Jan '15, 13:50

hackpert's gravatar image

accept rate: 0%

edited 31 Jan '15, 20:32

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! :D Thanks, neotech!


answered 31 Jan '15, 15:03

AnonymousBunny's gravatar image

accept rate: 10%

edited 31 Jan '15, 16:47


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

(31 Jan '15, 16:01) neo1tech9_76★

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


answered 31 Jan '15, 15:57

aalok_sathe's gravatar image

accept rate: 0%

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 :)


answered 31 Jan '15, 16:24

gladiator_98's gravatar image

accept rate: 0%

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}.


answered 31 Jan '15, 16:55

dibyo_99's gravatar image

accept rate: 0%

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


answered 31 Jan '15, 17:39

animesh_f's gravatar image

6★animesh_f ♦
accept rate: 9%

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.


answered 31 Jan '15, 17:48

nibnalin's gravatar image

accept rate: 0%

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


answered 31 Jan '15, 22:11

sakshi_garg's gravatar image

accept rate: 0%

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


answered 03 Feb '15, 10:47

data2000's gravatar image

accept rate: 0%

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

(03 Feb '15, 13:31) superty3★

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

(04 Feb '15, 08:49) data20003★

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:

(04 Feb '15, 14:13) superty3★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 31 Jan '15, 13:09

question was seen: 7,475 times

last updated: 04 Feb '15, 14:13