CodeChef invites you to participate in the September Mega Cook-off 2014 at http://www.codechef.com/COOK50. This is the Mega Warm-up Contest for ACM ICPC Regionals (India). The top 100 Indian Students shall have their ACM-ICPC expenses reimbursed. Find the details here.
Time: 21st September 2014 (2130 hrs) to 22nd September 2014 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: http://www.codechef.com/COOK50/
Registration: Just need to have a CodeChef user id to participate.
New users please register here
- Problem Setter : Lalit Kundu
- Problem Tester: Tasnim Imran Sunny
- Russian Translator : Sergey Kulik
- Editorialist: Devendra Agarwal
- Mandarin Translator: Gedi Zheng & Minako Kojima
It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.
"The top 100 Indian Students" : Suppose I get a rank of 101 among Indians and some people among the top 100 Indians are not university students then would I be considered among the "The top 100 Indian Students" ?
Contest starting soon, let's brace ourselves for 404s :D
I am getting 502 bad gateway :D
Yeah, the 404 was just a generalization (numbered errors). But we can get non-numbered ones, too.
502 instead ;d
502 and 503!...but not 404
Quite nice problem, I think the hardest problem is a bit easy, but it is still interesting. Some students from my school successfully persuaded me to participate in such a Sunday midnight =)
How was SUBLCM supposed to be solved?
There is a n * log(n) solution.
A subarray from i to j is considered valid if non of two elements from it share the same prime divisor. In other words every two elements of the subarray are co-prime.
Notice that a[i] <= 10^6. So we can easily get all the prime divisors for each 1 <= x <= 10^6. This can be done in n * log(n). Then we can use these precalculated arrays of divisors.
We have two pointers identifying the borders of subarray candidate. We also have a set of all prime divisors of the elements in current subarray.
We move right border. If all the prime divisors of the right-most element are absent in the set then new subarray is valid, add all new prime divisors to the set. If the set has any of prime divisors of the right-most element, then we move left border excluding prime divisors of the left-most element from the set. We move the left border until we eventually can add the right-most element.
Each time the right-most elements is added we receive a valid subarray. Its length is answer candidate.
Here is my code for this solution.
Hmm, I'm getting TLE in the hardest problem. The funny thing is, it runs in 3 seconds on the maximum random case and its runtime is pretty much fixed at O(20·(N + M)), so it probably fails because of the testing machine being slower than mine...
My solution is also O(20 * (N + M)), but all the constant 20 comes from finding LCA of two nodes, the rest are finished in O(1).
I've got more LCAs, but I don't like it when a problem's hard only because of constant-tight TL and (probably) slow testing machines.
I was calculating 6 LCA's per query, cout'ing with "endl" instead of "\n" and doing lot of other unnecessary stuff, and it passed with time 33.89:)
BTW, you said that you like CodeChef long contests for opportunity to fit into TL even with asymptotically bad solution, didn't you?:) What an irony:)
Hehe, all Codechef contests seem to favour asymptotically bad solutions over good ones. Here, my solution got the best time in-contest, while it was definitely supposed to not pass at all.
Yeah, and once i got 2 WA's, submitting unproven solution at some contest while saying to myself: "this one passed once before at same problem at CodeChef, it should be OK" :)
You definitely have some bug, because current codechef testing machine are able to do about 2*10^8 operations per second.
When just the input has 4 million numbers, it doesn't seem like much.
UPD: Also, got AC now. I've got no bug, the testing machines are just slow — I know it because one of my codes in practice that TLEd was made with only straightforward for-cycles without breaks (so it had pretty much fixed runtime) and took 2 seconds to run on random case on my machine.
Then again, it's not like I didn't consider SPOJ the worst choice for testing because of its speed even before this.
scanf in my solution did well. I hope you don't use cin :) You can also try implementing your own nextInt() by getchar(). This trick was damned popular when they used Pyramid testing machine.
Scanf isn't faster than optimized cin, it seems (I tried both and tested both on my machine). The difference is quite small, but using scanf didn't help me.
Test cases for SUBGCD are very weak. This solution passed — but it fails on following test:
oops! apparently the easiest problem wasn't tested much :/ btw, considering that this was my first cook off as setter, i feel nice that it went good(even though problems were on a easier side).
Did anybody manage to solve WW2 without matrix exponentiation?
is it even possible? i don't think so!