evima, yosupo and I would like you to participate in Codeforces Round #286. It will be held on Sunday, January 18th at 16:00 MSK. Please note that this round starts on unusual time.
Great thanks to Zlobober who helped us prepare this round, Delinur who translated statements into Russian and MikeMirzayanov who created Codeforces and polygon.
This is the 3rd time(following #162 and #263) for me, and the 1st time for evima and yosupo to prepare a Codeforces Round.
Scores of the problems will be
500-1000-1750-1750-2500 for Div.1, and
500-1000-1500-2000-2750 for Div.2.
In this round, you'll help a man named Mr. kitayuta. I hope he will participate :)
The system tests are now over! The top-5 are as follows:
Also, special congrats on Petr, who solved problem E in Div.1, which anyone else could not solve.
Here are the editorials
Will there be Appleman again in this problemset? We all really loved this hero last time... Especially guys from Russia:)
Upd. Oh, i see now... So sad, we all miss Appleman. Hope to see him in your next round.
oh, excuse me.
I try to hold another contest and show you Appleman again :)
You love appleman? But..but..Tanya...
He is I_love_Tanya_Romanova, not I_dont_love_anyone_but_Tanya_Romanova .
Oh, great! The 'unusual time' is suitable for Chinese coders ;-)
Same here, for Japanese :) that's why the time is unusual.
And for Indians as well :).
I see. It's nice.
This is the 3rd time(following #162 and #263) for me
Hope round #364 will be yours, too. :D
"this round starts on unusual time" = start time is 5:00 am here. :(
Seems I can't participate Chinese and Japanese contests anymore..
En.. If it is the 'usual time', it will be 00:00 ~ 02:00 in China ..
I think it will be 00:30 ~ 02:30 in China
You're right ...
It will be 23:00-01:00 in China...
Maybe all competitive programmers should live in the same longitude :| Where is reasonable?
Maybe Arctic Pole / Antarctic Pole? It don't have a longitude (or say, have any longitude).
hello dis like me pls
the "dislike me" loop will start as usual -_-
Score distribution already published. Thanks!
Mr. Kitayuta has registered to the contest.
Facebook HackerCup is running right now... I thought this would be delayed to after Hackercup or something...
That was a 24 hour contest you could have given it anytime :P
I can't join this round cause i have English class...
Why you don't define a specified time for contests? So we can planning for them...
Maybe someone else would have an English class at another time :D
But it's clear that this is for the problemsetters' convenience.
I think this round has unusual timing because the usual would have clashed with codechef cook off, too less space between them
Maybe it's both.
Lets just hope this contest goes fine and rated. :)
Codeforces just changed it's logo to default. Codeforces changed it's logo to christmas.
I think It was so hard; no right submissions for E. 1 right submissions for D. 33 right submissions for C. Wasn't it?
I'm solved Div1 D, but I'm too scared to submit it :D
It would've passed :P
Tried to hack 10^8 complexity solution, but unsuccessful attempt, code runs in 540 ms, is that possible??
Yes, of course
Codeforces is very fast you can use about 5*10^8 operations in 1sec.You probably talk about problem B (dfs-O(n^2)).You can't find tescase where you use 10^8 operations beacuse m(number of edges) is so small.
I had one solution in my room which does 10^8 calculations, here is the code.
in second cf server can do more than 10^8 operations i think
10^8 is very fast. Sometimes even fast 10^9 works
What was the solution of A? :)
Normal DP with F(i, j), where i is current position and j current jump length, but notice that j won't vary that much (~250).
Edit: I came up with this in the last minutes. T_T
How do you know that j won't vary?
If it changes more then 300 there has to be more then 30000 positions :)
Not a formal proof, but this was my thought: Assume you have i = 0, and j = 1 and you increase the length after every jump. At approximately j = 250, you will jump over the 30000 mark.
Can somebody tell me why this code got TLE? I used the same approach but recursive :)
AFAIU from your solution, you are caching only answers when jump length < 400. So if initial jump length was big (like 1000) you are calculating answers (for same input values) many times.
Thanks for going through my code :) Will try to correct it tomorrow.
I had to do something wrong, probably everyone in DIV1 tried this, but for last test case the cache had almost 5M states...
My code on ideone (but RE, because stack size is small)...
Imagine the game is finished, and your final jump length equal to j. It can be proven, that |j - d| is . That's why you can write dynamic programming dp[position][|j-d|].
UPD. The simple thought that can help you prove the fact. Imagine you start from the very start, and you have d=1. You cannot finish with large d, because almost equal to n.
UPD2. Fix a mistake, thanks Svyat.
Probably instead of ?
Tasks beautiful, but very difficult, IMHO.
i couldn't even solve A. Shame on me :(
Don't worry, 1364 registered for DIV1 and only 362 solved problem A :-D
We all will be kicked out of the division :-D
Can anyone explain to me how to solve DIV2 C ?
Argh, you could have been a little more generous with the time limit of div2c, a n^2 solution with unordered_map didn't pass, but could do any input on my machine in < 3s.
Can anybody here tell me why this code gets MLE?
Infinite reccursion. You don't initialize values of parent with parent[c][i] = i
And in find:
if(parent[c][v] = = v)
I implement it using this approach:
parent[c][i] = 1
and in find:
initially parent of all vertices is -1 then in find (parent of a vertex with parent -1), is itself.
sorry for typos, I'm writing with auto-correction using a phone!
It will fail with this testcase:
4 4 1 2 1 1 3 1 2 3 1 2 4 1 0
You do not check if they are already in same component and the recursion never ends.
Thx. I thought not ending of recursion causes
Runtime Errorinstead of
Memory Limit Exceeded.
My thoughts while trying to solve Div1.A and Div1.C (it's 2 MB gif).
A good contest.I only submit div A & B... Maybe My rating will decrease!
Why is it that during each and every Codeforces contest, you can't access the site when you need it the most? In the first 30 minutes, I could view other's solutions. But after that whenever I tried opening someone's solution, it just gave me a blank screen. It didn't work even after refreshing the page multiple times. So I couldn't even TRY to hack a solution!
Heh. I never expected that there will be a time when someone with rating 2484 will ask about it, but — how to solve A :D? D was the easiest one on this contest xD.
Imagine easy dp with [coordinate][lastJumpLen] state. Replace second argument with difference between the first jump's length and last jump's length. You know that it won't exceed 300.
I think that B was much easier.
B was still hard, took me something like 15-30 minutes (just coming up with solution) and D was straightforward for me :P.
Solution of A
Why Petr try so hard to solve E instead of other problems? It lands him in 117th :/
Maybe other 4 problems were just too easy, obvious and uninteresting for him...
I think we'll see his explanation in weekly digest :)
How about rng_58
Codeforces needs to at least have one approachable problem in Div1.. otherwise the majority of participants will not submit, meaning those who eventually do solve a problem will have a low ranking..
D was easy :>. Only one in that contest :D
Hmmm... you're totally right. After 0,5h of contest when I haven't got any idea how to solve any of those problems I considered not submitting anything : p.
I though, that once I'm registered, I'm competing — I expected my rating to be changed, even when I had no submition... On TC once I open the problem, my rating would be changed... But in fact the one who solved problem and ended at the end, his rating change is worse then mine, I think this is unfair...
Nice problems! Has someone any idea for Div2-C instead of TLE naive recursion + memoization?
See above: http://codeforces.com/blog/entry/15842#comment-207412
I think it is dynamic programming problem(but I couldn't implement it). It is because d can be only in segment (d-700,d+700) otherwise sum of jumpings at least d^2/2>30000. So dp[30000,1500] kills it. Am I right?
Yes, but D can be only [d-250,d+250], dp is enought.
How to approach Div1 D, it is an extension of Div2 B with larger constraints..
Div2 B could be solved by making m graphs, but how to approach the same problem if m is as large as 10^5?
I solved it with Union Disjoint sets in 2D. I think it can pass for m as large as 10^5
2D ??? Doesn't it get Memory Limit ???
Oh, it will :(
I didn't thought of it.
Could someone explain the idea of div1C solution?
Didn't submit (edit: Accepted ), but here's what I thought during the contest:
You want to simulate to see if a certain max_height is possible, then you can use binary search to get final answer. Hit the bamboos from the last day to the first day. Every bamboo i has to be hit before you get to a certain day hit_by[i] on the reverse simulation -- this means that even if you use all hammers possible on bamboo i before hit_by[i] you will not decrease height of bamboo enough, so you need to hit it at least once on a day after hit_by[i].
I haven't proven it formally, but I think greedily hitting the bamboo with the largest hit_by works.
Hm, I didn't get your idea. Can you explain the meaning of hit_by[i]? Why can you go from the end to the beginning? I mean, when you decide to do something in the very end, and then cut some bamboos before that moment, your final decision now possibly becomes wrong. Have I missed something?
hit_by[i] means: I have simulated some hits at the end so far. If I hit only bamboo i for the first hit_by[i] days and then hit at the end according to the simulation, I will be able to get bamboo i to a height smaller than max_height. But if I only hit bamboo i for the first hit_by[i]-1 days (other than simulated hits), I won't be able to get bamboo i low enough. This means I definitely have to hit bamboo i at hit_by[i] or after.
I don't understand why going from the end to the beginning would change the answer. When you do a cut the only thing that changes is the new target (I wanted less than max_height height by day m, now I want less than P height by day Q). If you go in the forward direction, then it's complicated because it's true that a cut affects a lot of other things.
My solution is based on the idea that it's optimal to hit a tree when its height is less than P at most once per tree. If this is true, then that hit should be at the first moment when (tree's height) ≥ (tree's final height if left unchecked — target height) % P.
I don't have a proof for that, though, so we'll see what happens in systests...
Well, we feel sorry that the problems were too difficult. Actually, we felt all of the tasks were a bit more difficult in comparison with other problems of the same scores, but I hadn't expected that there were such a few submissions&accepts.
I think such difficulty is good, AS LONG AS there is at least one problem that 75% of participants can solve (and it is the first problem :P)
Median of times I need to came up with solutions to B problems is probably less than a minute and here I didn't have any idea how to solve A and B took me something like 30 mins xD. Though I like hard problems, so this contest was really fun for me, because problems were interesting and that's what really counts :)!
I think we're all waiting for Editorial :)
Hard problem's have benefits . Solve hard problem to learn a new something :)
just to know ... why it gives me time excess (something like that) when i open a solution to hack and then i can open it another time!!
I think Problem B is easier than D.
ENOUGH TO ENDURE!
I have strong disire to view code highlighting in hacks. I'm so tired to recognize 1's and l's.
Does the following algorithm for Div1B work:
find the number of connected components (assuming each edge is bidirectional); let it be a
find the number of such connected components that have a cycle (with directed edges this time); let it be b
Our answer is (n — a + b)
I tried this, so either this algorithm is wrong or I'm bad at implementation :P
The same algorithm passed pretests here.
may you explain the analysis for this problem?
For a connected component with n vertices (if we consider the edge is undirected), the answer maybe n-1 or n. If the component doesn't contain any circle, then we can have a "line" that go through all the vertices making a graph that satisfy our condition (the order of vertices the line go through is in the toposort array) And if the component has a circle, what happen now? We can not make a toposort, then the answer can not be n-1, in this situation we just simply make a big "circle" that go through all the vertices (or we add an extra edge that go from the last element to the first element in the toposort array), then we will need n edges.
thanks, well explained :D
Will it work on the next testcase?:
The testcase looks like: <><>
We still need here 8 edges, but we don't have directed loops here. Or it's possible somehow to come up with only 7 edges here?
Just consider topological sort, and connect neighboring vertices (here, 1->2, 2->3, 3->4, 4->5, 5->6, 6->7).
I guess correct answer is six: just connect i-th vertex to (i+1)-th: 1 → 2 → 3 → ... → 7
Wouldn't the answer to that be 6? 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
Wow, triple snipe :P
answer is 6:
Right answer can't be more than N, because we can make one loop with N edges, where from each vertex you can reach any other
The algorithm is right
Consider this case
4 4 1 3 1 4 2 3 2 4
a = 1 b = 0 Answer = 4 — 1 + 0 = 3
If my understanding of the problems I right, answer should be 4.
No, the answer is 3; you make the edges 1 → 2, 2 → 3, 3 → 4.
Right, thanks. From the start i was thinking of given m edges, remove as many as possible without disturbing connectivity. Screwed it!
It should work.
If you have a component that contains a cycle, you need to make at least one resulting cycle, so you need at least as many edges as the number of vertices in that component. It's clearly optimal to put all vertices on one cycle.
If there's no cycle, you need at least (number of vertices)-1 edges; a DAG can be transformed into a path without failing any rules, and a path has the required number of edges.
Can someone tell me one thing, please? What is the point of having one extremely easy problem and one easy problem and 3 almost unsolvable problems for Div2 participants. Then you have list where 60th participant solved A and B, as same as someone who is 800+.
This often happens, especially in Topcoder SRM.
I think, that you both are talking about different divisions, so I have to disagree, in TC DIV2 easy and medium are not so difficult and also hard is soleable...
Hacks are decisive here.
Just if the pretests are weak... :D
Next competition is only div 2,maybe I solve something :)
What's wrong with system testing?
I opened results before system testing and saw this
Pending system testing...................?
Hey, let's start system testing! I want to see these red->purple and green->gray xD
Thanks you! Nice contest :D
As nice as I couldn't imagine. :|
good luck :v
I think system testing is deterioration
What's going on? 45 minutes has passed since the contest has finished!
I guess the rating updates will be fast as (because) the system testing is slow!
Who knows maybe they are precalculating the results and ratings :D
You are so naive...
I think Codeforces is broken. Take a look at "Pay attention" area...
UPD: Already fixed.
It often happens when contest ends.
The unusually long wait for the programs to pass the system tests is adding to the anxiety, especially for those expecting a rise in ratings after the contest
How to solve problem D of Div. 1? Why many people say that it's easy? Thanks a lot.
Second hour just began...
Anybody else read Problem B statement wrongly? I thought only "edges" on input are allowed to make teleportation graph...
me too :(
So it has begun.
The system testing is delayed due to verifying test cases(not a technical reason or trouble in the judge server). We feel really sorry about this.
The problems are so hard, even round author can't solve them.
The round author should have thought about it when he decided to be the round author. :) They have to be sorry anyway, it's a long delay.
I resubmitted D a couple of times because I saw I went over the memory limit (259900KB, but still Pretests Passed). 9463550
But it looks like my fears were unfounded, because the same submission, using even more memory on system tests, still got Accepted. 9465410
rng_58 , It doesn't matter what is your rating (or rank)! we will always be your fan!!
I guess he had a bet against Petr, which he lost!
I decided to change my strategy and chose a problem that looked the most interesting for me. I enjoyed this round even though I solved no problems (but if you try to solve boring problems and fail a round it's quite frustrating). Maybe I will keep this strategy for a while.
"I decided to change my strategy" : so what is your previous strategy? Solving in random order? :P
I'm sure it is not solving in the order of A to E.
Solve the problems in the decreasing order of (point value) / (required time).
That may not be optimal if you can't solve all tasks. :)
Actually I tried to describe my strategy here: http://community.topcoder.com/stat?c=problem_statement&pm=11357
I will start crying now...
The ratings are back to the last ones???
That's because of my prayers :D
UPD: I'm going to pray again.
Mmm, guys, what has happened to ratings?
WTF , I had +55 but now it is +50 , why ???
It seems that everybody's rating has decreased by 5 or less..
My rating has decreased by 4 pts.
I had +86, now +84.
I had +181, but now it is +176(-5). hmm..
Also decreased by 5 ...
It seems that i've just set a new record for shortest period of being IGM (~20 minutes, i guess :) )
Can anyone tell what's wrong with my DFS for Div.2 B? Each node has a vector of pairs <color, endnode> and then it just tries to DFS through all the colors, but I can't figure out why it doesnt work. :/ http://codeforces.com/contest/505/submission/9461069
I don't know what your algorithm does but here is a simpler way:
for every possible color see if there is an x-to-y path with that color only (x and y are query vertices).
Yeah I tried to figure out a path from the start vertex to the end vertex by just recursively checking the neighbour nodes of the following vertex and if the edge color was the same then continue searching until the end. However for some reason my implementation is not correct.
I checked all possible colors, as __builtin__wolfy said. I added couple of //
I just can't understand how the rating works.. rng_58, whose rating was 2782, got -107. But Antoniuk (whose rating was 2244), and -imc- (whose rating was 2256) both got -102. All of them got 0 points in this round. How could this be possible?
It is ovious even for me=). rng_58 have higher rating then Antoniuk and dragonic, so his rating dropped down most. Antoniuk and dragonic have same decreasing, beacause of rounding, rating calculates in double then rounds to int. Read about Elo rating. Sorry for my bad english.
You may be right. Thanks for your comment, I'll read about the ratings :D
There exist some threshold — you can't lose more than X points, no matter how bad you perform. I don't know how value of X for given user in given contest is calculated, but usually it is around 100 points (or a bit more).
When you are violet — it is really hard to hit this limit; for red users it is much easier (placing somewhere in the middle of the standings is enough), and for top-users it is even easier — tourist once got -135 for 21st place.
And also — look how dreamoon_love_AA was getting -110..-120 for placing last :)
I was just suspicious because I got -111 last round, for only solving B. (my rank was 366/610) I think the reason is that the problems of this round were really hard than the last round's problems..
Will this algorithm work for div 2 D?
No. The correct algorithm is above somewhere. (look for Div1-B instead of Div2-D)
Many Accepted codes of Div-1 A/Div-2 C crushes for this input:
1 1 30000
Is the input invalid? Or, judge data is weak?
This Accepted Code Crashes for the above input.
It's invalid, because there are 30'000 islands in total, not 300'000.
Sorry for my mistake, it was actually 3*10^4. I have updated the input now and have added a link of a acctepted code that fails this test case.
My prog return 1.
I guess this is correct answer.
UPD: Sorry, didn't notice 3*10^5, not 3*10^4
i actually meant 3*10^4. but, somehow miss-typed 3*10^5. Sorry for my mistake... i have updated the input now. :) and, i have also added a link that fails this test-case.
Test case #18 is exactly yours.
i don't get it... why this code would crush in my system while it works fine on Codeforces??
Just a guess: undefined behaviour.
f ends up recursing roughly 30,000 times; my guess is you got a stack overflow.
i guess too that it is caused by stack overflow. But, don't you think, PC got more space than virtual judge for stack memory? although, i am not sure which one got more space for running a program!! :(
Codeforces sets a huge stack size.
Stack size != total RAM size, at least in Windows (not sure about *nix). Actual stack size defined during program compilation. And, for example VS compiler by default sets it to some not-that-big value (1 Mb, I assume). And on Codeforces it is set to 128 Mb at least.
that helps a lot.... didn't know that compiler allocates this little space :)
For Div1-A/Div2-C, Could someone help me figure out why does 9462290 TLE at test 5 but 9467397 gets AC? The only difference is I change the memoization from a map to an array keeping the difference with d.
Shouldn't the two essentially be the same ?
std::map has O(log n) access time, not O(1). AFAIU std::unordered_map has sort-of-O(1) access time, but with bad constant. I also failed to solve this problem with unordered_map, but got AC with plain array.
BTW, my array solution works 5x times faster than yours, probably because I also use array for gems variable (and you use map).
I know that a map has O(logn) but that should still make within the time limit, right ?
As we can see, it shouldn't :(
I guess map is actually slow and I should be more cautious using it then. It seems to have a very large constant factor and does allocations for each object hence its slowness.
I found this:
std::map has similar characteristics to std::set: it uses a single allocation per pair inserted into the map, it offers log(n) lookup with an extremely large constant factor, imposes a space penalty of 3 pointers per pair in the map, etc. __ std::map is most useful when your keys or values are very large, if you need to iterate over the collection in sorted order, or if you need stable iterators into the map (i.e. they don’t get invalidated if an insertion or deletion of another element takes place)
EDIT: Hmm I just tried changing my code in Java to use a HashMap which has O(1) 9467938 but it also gets TLE at test 5..
Thanks for posting this, I'm practically in the exact same situation. My solution is here: http://codeforces.com/contest/505/submission/9467923 and theoretically its complexity is at most around 30000*500 operations, which should be acceptable. However, since these operations are on maps, it appears the very large constant factor does its tricks. I expected my solution to either barely pass or just barely get TLE, but it turns out it takes ages to produce a solution, tens of seconds on my machine. Honestly, I'm pretty shocked at how slow the operations on maps are in this case. I guess this is a good lesson for me on how well modern processors can handle contiguous data (vector) vs. not-so-contiguous (map).
So do I. Even I changed
unordered_map, still got TLE.
A tough lesson, QAQ~
2 years ago Coder noticed that Petr and tourist couldn't solve C which was also E for div2 and made this comment: http://codeforces.com/blog/entry/5586#comment-108611
What to say today about Petr and rng_58 :)?
Imagine both of them only solving A and B in div2 and placing 800th
Don't be so fast. At most A and B :).
Meh. It's good to have basic knowledge about STL...
This got TLE and used 198MB: 9459485
And this easily passes all tests using 23MB: 9469360
The only difference is changing
Finally, after 93 contest I'm in div1 I'm so happy!
Congratulation to you. What a fighting way.
I pass Div1 A and D both through brute force. So lucky and maybe the test cases must be more careful.
Where is the editioral?
It is currently being written. The first part (all problems except Div1C(2E) and Div1E) will be ready within approximately 4 hours. Thank you for your patience.
Edit: sorry, I had to insert one word into the sentence above.
Edit2: The first part has been published here. It actually took 8 hours after I posted this, sorry for being late.
Edit3: Added Div1C(2E) and the problem setters' codes.
Edit4: Added Div1E. I am sorry to have kept you waiting.
But those are the best problems ... :(
When will the editorial be out?
problemset was tough but very nice , problems required more thinking instead of coding that means quality contest.
Congratz to authors !!!
I can't open editorials
I see no problems for now. Is it fixed?
Why my solution get WA on test 10? I can't see anything wrong in my solution...
Please help me!
That URL displays my submissions for me, not yours. Please specify the submission ID.
Sorry. I fixed that.
He did already ;-)
excuse me, for this easy sample : 6 7 1 2 2 3 3 1 3 4 4 5 5 6 6 4 the output is 6, it is not 7, why ?
Can anyone help me and explain why my solution is failing for Div1 Problem A. My Solution id is : 9666602