You are not logged in. Please login at www.codechef.com 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 ♦
8731422
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 :( )

link

answered 31 Jan '15, 13:50

hackpert's gravatar image

1★hackpert
1
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!

link

answered 31 Jan '15, 15:03

AnonymousBunny's gravatar image

5★AnonymousBunny
15718
accept rate: 10%

edited 31 Jan '15, 16:47

2

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

link

answered 31 Jan '15, 15:57

aalok_sathe's gravatar image

1★aalok_sathe
1724
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 :)

link

answered 31 Jan '15, 16:24

gladiator_98's gravatar image

0★gladiator_98
1
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}.

link

answered 31 Jan '15, 16:55

dibyo_99's gravatar image

3★dibyo_99
1
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 !

link

answered 31 Jan '15, 17:39

animesh_f's gravatar image

6★animesh_f ♦
8731422
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.

link

answered 31 Jan '15, 17:48

nibnalin's gravatar image

6★nibnalin
1611515
accept rate: 0%

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

link

answered 31 Jan '15, 22:11

sakshi_garg's gravatar image

2★sakshi_garg
11
accept rate: 0%

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

link

answered 03 Feb '15, 10:47

data2000's gravatar image

3★data2000
11
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: http://inoi15.discuss.codechef.com/questions/63431/how-did-you-solve-the-problems-in-todays-paper-whats-the-expected-cutoff/63538

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

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,882
×365
×144
×69

question asked: 31 Jan '15, 13:09

question was seen: 7,396 times

last updated: 04 Feb '15, 14:13