For your convenience, we make a new thread for discuss second round of the Algorithm. Will be held on may 30 05:00 (UTC +3).
While waiting for the round you can practice
Don't miss out!
UPD Round 3 will start on schedule at 13:00 on June 6, 2015 and will last 100 minutes.
The time and date of Round 2.2 will be specified later, stay tuned.
I understand that you wanted to make Yandex available for people all around the world, but since score from eliminations is summed and vast majority of people competing are from Europe and Asia (mainly Russia) then it's just sadism to schedule round on 4 AM :P (5AM for Russia). I guess that moving it 4 hours forward or 4 hours backward will make it much more available to many people and it won't make a significant difference for people which live in timezones where this hour is comfortable.
Nowadays, following TopCoder usually brings nothing good ( ͡° ͜ʖ ͡°)
Sadism is part of Russian culture :)
Indeed. Especially when you have "Internal Server Error" instead of the contest...
5AM in Moscow it's noon in Vladivostok.
Or 3AM in Dublin. Just no :) Sorry for top participants who will have to participate in this absurd.
Well, some top participants don't have to anymore :)
OK, you got me there :). Though I know that China despite its size is in one timezone :P.
By the way, are there many top competitive programmers in Russia outside bigger cities in west like Saint Petersburg, Moscow or Saratov?
Novosibirsk (UTC+06:00, CF) is the third most populous city in Russia.
Internal Server Error
And why i dont wonder why i waked up?
Internal Server Error
Is it really so difficult to handle 2,000 people online?
codechef working smooth .. yandex site down .. parallel universe!
and UVa is down from yesterday !!! why ???
I don't know why but, it's a pretty regular thing for UVa.
Ok, guys. Let's go back to sleep.
Internal Server Error ) 5 am is very nice time for jury :)
How to solve "Internal server error" problem (Spoilers):
Reduce it to external server error and then it is dynamic programming on servers
Can juri just paste problem statements here?
May be they will decide to change date of round, there is no reason to spoiler problems.
Yeah, and have us PM them our solutions.
You probably shouldn't (unfair advantage to ppl who don't visit CF frequently), but you probably can (as in: it probably won't be removed immediately). Mathematical answer! :D
Bad solution.
Many have read problem statements..
Several people managed to submit their solutions and got OK for them.
I think we have to sleep :(
I recommend open an incognito window/cleaning cookies for those getting ISE.
This didn't work (at least for me).
doesn't help
Doesn't help.
P.S. Post-mortem would be highly appreciated.
Maybe we should also restart PC/reinstall Windows?
Definitely. Also maybe restart our routers?
But if you have Windows, the PC restarts automatically :D
Doesn't help
Now it is saying "Problemset is not available" and "Submit form is not available now"
Doesn't help
It seems that some people have already seen some problems statements...
Yes, I already coded my solution for A, but can't submit. :(
Me too. :(
"The only thing that limits her is that she is unable to cover a height difference of more than m in a single step". Coundn't understand that part, because max(H_i) <= m, so we can go from i to j for any arbitrary i, j?
I suggest not to discuss now.
Yes, I've seen A
Come on!
It has been 20 minutes. Will you postpone it or what?
Are you waiting for gaining more hate of contestants who wake up in the middle of the night?
Am I need to register for this contest? I have participate in Round 1?
As far as I know, you don't need to register again.
Its 4:24 AM in the morning here, i slept only 2 hours and woke to participate this contest and now its Internal Server Error, give us some update lperovskaya :P
You should go back to sleep, you'll only have an unfair disadvantage, since some people have seen the problem statements.
At least you're not in a bus with laptop battery charged barely enough for the contest in the original time frame (okay, even less than that).
I thought previously that Bayan did really bad...but here you go...
Codechef is more stable than Yandex, what a time to be alive!
I wonder if somebody is working on that or they just sleep at this late night/early morning time :)
Yet another F5-style contest :(
I think this contest should be postponed.
I just get off from the bed to participate in this contest while my girlfriend is waiting for me and doubting of my motive in the midnight. Now, I don't understand should I wait for the contest or go back to my girlfriend.
I would prefer a girlfriend to this contest.
what is the problem???
I have exam an hour later and can't submit anything!!
PS: now I can not see problems either!
I have exam in 3 minutes(
I wonder why they don't use Codeforces as the contest platform when Yandex 2012 went well on Codeforces. Now it's like a joke.
I believe its "Not Invented Here" problem.
I guess Codeforces doesn't yet support whatever minor unimportant modifications they want (like the blind/open thing). Make Codeforces more versatile and you avoid these problems.
They should have canceled the contest after 20 minutes of this, tops. Very unprofessional. Not canceling it at all is even more disastrous (whoever f5s the hardest qualifies for onsite).
Maybe they tried to cancel it but got internal server error.
EDIT: After 1 hour, they finally got sane. Good night.
They said in QR such a problem won't happen in future rounds... hmmm
All problems: https://dl.dropboxusercontent.com/u/48283862/AYandex.pdf https://dl.dropboxusercontent.com/u/48283862/BYandex.pdf https://dl.dropboxusercontent.com/u/48283862/CYandex.pdf https://dl.dropboxusercontent.com/u/48283862/DYandex.pdf https://dl.dropboxusercontent.com/u/48283862/EYandex.pdf https://dl.dropboxusercontent.com/u/48283862/FYandex.pdf
what's the use of seeing the questions when the status of submission is waiting for like forever!
Technical issues
Due to technical issues with Yandex.Contest platform results of this round will not be taken into account in elimination stage results. We will inform you about new scheduled time for second round additionally. Sorry for the inconvenience
Due to technical issues with Yandex.Contest platform results of this round will not be taken into account in elimination stage results. We will inform you about new scheduled time for second round additionally. Sorry for the inconvenience
Wow! How lucky am I! I have to be in class during the contest, and can't participate. Now I have chance to join it again :D Hope the additional round won't be held on this time again :(
Idea of different times for contests was so that everybody could take at least one with convenient timing. So replacement round should be at the same time.
But we already wake up at 5AM. It's so scary :(
And I am just going to sleep — 23:00 here, tomorrow morning is GCJ Round 2. So nice timing for me ;) I will have to wake up early for one of the rounds too.
Please do not schedule it at 4 AM..... x_0
Lets be fair it's 4 AM not in all timezones and I think 3 rounds are trying to cover all timezones. =)
And the next round 2 is going to be scheduled on the same time?(
I want to have some words of support for contest staff here. Bad things happens on all platforms. Some people here asked "Why not Codeforces?", but aren't they very same people who would gladly complain about Codeforces server being down only if Codeforces would be available. TopCoder rounds got cancelled once in a while, etc. I think people would be much more forgiving if it would not happen in this particular round that scheduled at early morning/night for Europe
How to solve D?!
If d = 2^p2 * 5^p5 then answer is max(p2, p5) Else impossible
Can you prove this solution?
Take a worst case like a number = VeryBigPrimeNumber * 10^k + b, where b = h * d, where h = const. VeryBigPrimeNumber >>>> d, so you need that d = 5^p1 * 2^p2, beacuse 10^k have only two prime divisors(2 and 5) and you need that 10^k mod d == 0. So, if(d != 5^p1 * 2^p2) then ans := -1, else ans := max(p1, p2)! You can found p1 and p2 in O(logN). (My Internet is SlowPoke :) )
Let's assume that the answer for some d is k. It means that we can decompose any integer n into a sum n = a × 10k + b and all we need to check divisibility of n by d is to look at b, i. e. a doesn't affect divisibility by d. Thus, 10k is divisible by d. If d = 2i * 5j the answer is max(i, j). Otherwise there is no such k, the answer is "impossible".
How to solve E? I used such dp — f[len_prefix][wasC1][wasC2][wasC3][ost][flag] I fixed the three biggest numbers and then calculate dp. But it gets TLE. Who can help me? Code Link Here
I had even one more field in dp [did we have only zeroes before] but wasC1..C3 were compressed to one bitmask 0..7 and I got AC in 2.8s.
i had a dp with state[len][0..7][mod][flag][zero][C1][C2][C3]. It worked nearly in 198ms.
Before the round starts, this blog was +53. Now it's +16, and still decreasing. What a sad story :(( I think all contests should be encouraged, as all managers have tried their best.
I'm interested how to solve C without coding brute force for small numbers and looking for a pattern?
Read Wikipedia.
Cannot see anything about giveaway nim there (:
It is called misère in there
Excuse my necroposting. Can anyone help me find the error (http://pastebin.com/SmScmC1B) or share their C++ solution? Thanks!
How to solve A ? I am getting a WA on test 5. Submission.
You need to compute the answer modulo 109 + 7.
Wouldn't it get TLE anyway? It's O(n2). What's a better solution?
two pointers maybe? (Lol i was typing "two painters" by mistake)
May not be the best solution, but you can solve using seg-tree with lazy propagation. For a height 'X' the number of ways is sum of number of ways of reaching height 'X-i' where 1<=i<=MaxJump . You can view this in a slightly different way that ways[X] will be added to ways[X+i] for i in the same range. Consider this as a range update (you can find the range indices using binary search) . Finally find the value of the last leaf of segtree, which is the answer.
If there is a solution better than O(n*logn), please do post your solution.
Code : http://ideone.com/gnBviP
two pointers :| http://paste.ubuntu.com/11446865/
I didn't understand solition, please explain in simple words. I know about two pointer
we know that dp[i] gets updated from dp[j] and dp[j+1] and ... dp[i-1] let's name this j az up[i] we know that if i < k -> up[i] <= up[k] so up[i-1] <= up[i] so we just need to move forward from up[i-1] to find the place that has less than m distance from i and that's that
Another linear solution:
Suppose dp[i] stores the number of ways to reach the ith step, and sum[i] stores sum of dp[0] to dp[i]. Also, you can store the cumulative sum of all the stairs uptil ith position in, say y[i]. now, you just need to search for lower_bound(y[i]-m) in the array y, and dp[i]=sum[i-1]-dp[lower_bound-1].
http://ideone.com/jnj6zv
Note: instead of calling lower_bound each time, you can preprocess the lower_bound indices in O(n) and calculate the dp and sum arrays in O(n).
Your solution is actually the same with Reyna's.
i only realized that after posting my comment. I hadn't refreshed my page since a few minutes :)
any updates on the new time of rescheduled round??
OK, so I will try to elaborate a bit more why organizing event at this hour is wrong and how it could be improved.
Firstly, we will use quantity argument. Look at the standings table. Keep in mind that this was middle of the night for Europe/West Asia. Scheduling hour of contest as such does good only for people from America (Northern and Southern). I just counted and there were about 14 people competing from those countries (USA, Argentina, Canada, Brazil, Dominicana and Cuba counted :P). And best of them was on 41st place. Does this really has any sense scheduling contest on that hour, making favor for that incredibly small amount of people and forcing about 200-300 not to sleep before 6/7AM? Moreover many people won't compete, so this competition kinda changes from "who is better programmer?" to "who can stay woken up longer?" and make results not reliable. Btw people competing at that hour have much smaller abilities, normally I would treat being unable to solve D as serious mental disability, but I managed to fail this either way :P (it was 5 AM >_>).
Considering people from America — isn't hour as one first contest was held at comfortable for them? If I'm not mistaken it's 1PM, so it superfine. 8PM in Poland/9PM in Moscow seems to be very good hour for people all around the world. Maybe for East Easia it is not that comfortable, so we can shift it 3 hours earlier. It is 9 AM in San Francisco and 1AM in Tokyo, so I think it's really fine. Given this — choosing hours 3 PM, 6PM, 9PM in Moscow would be the best option, because in that form everyone in whole world has at least 2 chances to compete in fine hours and amount of competitors such that they cannot compete 3 times not in the middle of night is much smaller than it is now.
winger lives in USA, and he is on the third place.