### hogloid's blog

By hogloid, 5 years ago, ,

Hello Codeforces!

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:

Div.1:

1.ilyakor

2.kcm1700

3.LayCurse

Div.2:

1.HYEA

2.cpcpc

5.sha384

Also, special congrats on Petr, who solved problem E in Div.1, which anyone else could not solve.

Here are the editorials

• +289

 » 5 years ago, # | ← Rev. 2 →   +36 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.
•  » » 5 years ago, # ^ |   +46 oh, excuse me. I try to hold another contest and show you Appleman again :)
•  » » 5 years ago, # ^ |   +60 You love appleman? But..but..Tanya...
•  » » » 5 years ago, # ^ |   +38 He is I_love_Tanya_Romanova, not I_dont_love_anyone_but_Tanya_Romanova .
 » 5 years ago, # |   +57 Oh, great! The 'unusual time' is suitable for Chinese coders ;-)
•  » » 5 years ago, # ^ |   +34 Same here, for Japanese :) that's why the time is unusual.
•  » » » 5 years ago, # ^ |   +22 And for Indians as well :).
•  » » » 5 years ago, # ^ |   +19 I see. It's nice.
 » 5 years ago, # |   +38 This is the 3rd time(following #162 and #263) for meHope round #364 will be yours, too. :D
 » 5 years ago, # |   +35 "this round starts on unusual time" = start time is 5:00 am here. :(Seems I can't participate Chinese and Japanese contests anymore..
•  » » 5 years ago, # ^ |   +8 En.. If it is the 'usual time', it will be 00:00 ~ 02:00 in China ..
•  » » » 5 years ago, # ^ |   +17 I think it will be 00:30 ~ 02:30 in China
•  » » » » 5 years ago, # ^ |   +3 You're right ...
•  » » » 5 years ago, # ^ |   0 It will be 23:00-01:00 in China...
•  » » 5 years ago, # ^ |   0 It's good time for me.
•  » » 5 years ago, # ^ |   +49 Maybe all competitive programmers should live in the same longitude :| Where is reasonable?
•  » » » 5 years ago, # ^ |   +24 Maybe Arctic Pole / Antarctic Pole? It don't have a longitude (or say, have any longitude).
 » 5 years ago, # |   -64 hello dis like me pls
•  » » 5 years ago, # ^ |   -47 the "dislike me" loop will start as usual -_-
 » 5 years ago, # |   +6 Score distribution already published. Thanks!
 » 5 years ago, # |   +32 Mr. Kitayuta has registered to the contest.
•  » » 5 years ago, # ^ |   +24 :)
 » 5 years ago, # |   0 Facebook HackerCup is running right now... I thought this would be delayed to after Hackercup or something...
•  » » 5 years ago, # ^ |   0 No more delays
•  » » 5 years ago, # ^ |   +5 That was a 24 hour contest you could have given it anytime :P
 » 5 years ago, # |   -34 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...
•  » » 5 years ago, # ^ |   +5 Maybe someone else would have an English class at another time :DBut it's clear that this is for the problemsetters' convenience.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +3 I think this round has unusual timing because the usual would have clashed with codechef cook off, too less space between them
•  » » » » 5 years ago, # ^ |   +3 Maybe it's both.
 » 5 years ago, # |   -6 Lets just hope this contest goes fine and rated. :)
 » 5 years ago, # | ← Rev. 2 →   -9 Codeforces just changed it's logo to default. Codeforces changed it's logo to christmas.
 » 5 years ago, # |   +4 I think It was so hard; no right submissions for E. 1 right submissions for D. 33 right submissions for C. Wasn't it?
 » 5 years ago, # |   +5 I'm solved Div1 D, but I'm too scared to submit it :D
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 It would've passed :P
 » 5 years ago, # |   -6 Tried to hack 10^8 complexity solution, but unsuccessful attempt, code runs in 540 ms, is that possible??
•  » » 5 years ago, # ^ |   0 Yes, of course
•  » » 5 years ago, # ^ |   +1 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.
•  » » » 5 years ago, # ^ |   -8 I had one solution in my room which does 10^8 calculations, here is the code.
•  » » 5 years ago, # ^ |   0 in second cf server can do more than 10^8 operations i think
•  » » 5 years ago, # ^ |   +14 10^8 is very fast. Sometimes even fast 10^9 works
 » 5 years ago, # |   +28 What was the solution of A? :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +47 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
•  » » » 5 years ago, # ^ |   0 How do you know that j won't vary?
•  » » » » 5 years ago, # ^ |   0 If it changes more then 300 there has to be more then 30000 positions :)
•  » » » » 5 years ago, # ^ |   +9 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.
•  » » » » 5 years ago, # ^ |   0 Can somebody tell me why this code got TLE? I used the same approach but recursive :)http://codeforces.com/contest/505/submission/9462104
•  » » » » » 5 years ago, # ^ |   0 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.
•  » » » » » » 5 years ago, # ^ |   0 Thanks for going through my code :) Will try to correct it tomorrow.
•  » » » 5 years ago, # ^ |   0 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)...
•  » » 5 years ago, # ^ | ← Rev. 4 →   +35 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.
•  » » » 5 years ago, # ^ |   +8 Probably instead of ?
 » 5 years ago, # |   +36 Tasks beautiful, but very difficult, IMHO.
 » 5 years ago, # |   +8 i couldn't even solve A. Shame on me :(
•  » » 5 years ago, # ^ |   +26 Don't worry, 1364 registered for DIV1 and only 362 solved problem A :-DWe all will be kicked out of the division :-D
 » 5 years ago, # |   0 Can anyone explain to me how to solve DIV2 C ?
 » 5 years ago, # |   0 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.
 » 5 years ago, # | ← Rev. 2 →   0 Can anybody here tell me why this code gets MLE? #include using namespace std; const int N = 1e2 + 5; int parent[N][N]; int find(int c, int v) { if (parent[c][v] == -1) return v; return parent[c][v] = find(c, parent[c][v]); } void unite(int c, int u, int v) { parent[c][find(c, u)] = find(c, v); } int main() { memset(parent, -1, sizeof parent); int n, m; cin >> n >> m; for (int i = 0; i < m; ++i) { int a, b, c; cin >> a >> b >> c; unite(c, a, b); } int q; cin >> q; while (q--) { int u, v, ans = 0; cin >> u >> v; for (int i = 1; i <= 100; ++i) if (find(i, u) == find(i, v)) ++ans; cout << ans << '\n'; } } 
•  » » 5 years ago, # ^ |   0 Infinite reccursion. You don't initialize values of parent with parent[c][i] = i And in find: if(parent[c][v] =  = v)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 I implement it using this approach:init:parent[c][i] = 1and in find:if(parent[c][v]==-1)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!
•  » » 5 years ago, # ^ |   0 It will fail with this testcase:4 4 1 2 1 1 3 1 2 3 1 2 4 1 0You do not check if they are already in same component and the recursion never ends.
•  » » » 5 years ago, # ^ |   0 Thx. I thought not ending of recursion causes Runtime Error instead of Memory Limit Exceeded.
 » 5 years ago, # |   +268 My thoughts while trying to solve Div1.A and Div1.C (it's 2 MB gif).
 » 5 years ago, # |   0 A good contest.I only submit div A & B... Maybe My rating will decrease!
 » 5 years ago, # |   +8 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!
 » 5 years ago, # |   +42 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +17 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.
•  » » 5 years ago, # ^ |   0 I think that B was much easier.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +8 B was still hard, took me something like 15-30 minutes (just coming up with solution) and D was straightforward for me :P.
•  » » 5 years ago, # ^ |   +5
 » 5 years ago, # |   0 Why Petr try so hard to solve E instead of other problems? It lands him in 117th :/
•  » » 5 years ago, # ^ |   +67 Maybe other 4 problems were just too easy, obvious and uninteresting for him...I think we'll see his explanation in weekly digest :)
•  » » » 5 years ago, # ^ |   -8 How about rng_58
 » 5 years ago, # |   +77 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..
•  » » 5 years ago, # ^ |   -19 D was easy :>. Only one in that contest :D
•  » » 5 years ago, # ^ |   -24 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.
•  » » 5 years ago, # ^ |   +18 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...
 » 5 years ago, # |   0 Nice problems! Has someone any idea for Div2-C instead of TLE naive recursion + memoization?
•  » » 5 years ago, # ^ |   0
•  » » 5 years ago, # ^ |   0 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?
•  » » » 5 years ago, # ^ |   0 Yes, but D can be only [d-250,d+250], dp[30000][500] is enought.
 » 5 years ago, # | ← Rev. 2 →   0 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?
•  » » 5 years ago, # ^ |   0 I solved it with Union Disjoint sets in 2D. I think it can pass for m as large as 10^5
•  » » » 5 years ago, # ^ |   0 2D ??? Doesn't it get Memory Limit ???
•  » » » » 5 years ago, # ^ |   +5 Oh, it will :(I didn't thought of it.
 » 5 years ago, # |   0 Could someone explain the idea of div1C solution?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +21 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.
•  » » » 5 years ago, # ^ |   0 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?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 5 years ago, # ^ |   +8 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...
 » 5 years ago, # |   +57 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.
•  » » 5 years ago, # ^ |   +7 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)
•  » » 5 years ago, # ^ |   +16 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 :)!
•  » » » 5 years ago, # ^ |   +3 I think we're all waiting for Editorial :)
•  » » 5 years ago, # ^ |   +4 Hard problem's have benefits . Solve hard problem to learn a new something :)
 » 5 years ago, # |   +3 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!!
 » 5 years ago, # |   +76 1500-1500-2500-1000-2500
•  » » 5 years ago, # ^ |   0 I think Problem B is easier than D.
»
5 years ago, # |
+97

# ENOUGH TO ENDURE!

##### I have strong disire to view code highlighting in hacks. I'm so tired to recognize 1's and l's.

 » 5 years ago, # | ← Rev. 2 →   +1 Does the following algorithm for Div1B work:find the number of connected components (assuming each edge is bidirectional); let it be afind the number of such connected components that have a cycle (with directed edges this time); let it be bOur answer is (n — a + b)I tried this, so either this algorithm is wrong or I'm bad at implementation :P
•  » » 5 years ago, # ^ |   +21 The same algorithm passed pretests here.
•  » » » 5 years ago, # ^ |   0 may you explain the analysis for this problem?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +39 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.
•  » » » » » 5 years ago, # ^ |   0 thanks, well explained :D
•  » » » 5 years ago, # ^ |   0 Will it work on the next testcase?: 7 8 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7 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?
•  » » » » 5 years ago, # ^ |   +13 Just consider topological sort, and connect neighboring vertices (here, 1->2, 2->3, 3->4, 4->5, 5->6, 6->7).
•  » » » » 5 years ago, # ^ |   +16 I guess correct answer is six: just connect i-th vertex to (i+1)-th: 1 → 2 → 3 → ... → 7
•  » » » » 5 years ago, # ^ |   +8 Wouldn't the answer to that be 6? 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
•  » » » » » 5 years ago, # ^ |   0 Wow, triple snipe :P
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +8 answer is 6: 1 2 2 3 3 4 4 5 5 6 6 7
•  » » » » 5 years ago, # ^ |   -8 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
•  » » 5 years ago, # ^ |   0 The algorithm is right
•  » » 5 years ago, # ^ |   0 Consider this case4 4 1 3 1 4 2 3 2 4a = 1 b = 0 Answer = 4 — 1 + 0 = 3If my understanding of the problems I right, answer should be 4.
•  » » » 5 years ago, # ^ |   +5 No, the answer is 3; you make the edges 1 → 2, 2 → 3, 3 → 4.
•  » » » » 5 years ago, # ^ |   +15 Right, thanks. From the start i was thinking of given m edges, remove as many as possible without disturbing connectivity. Screwed it!
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # | ← Rev. 3 →   +20 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+.
•  » » 5 years ago, # ^ |   +1 This often happens, especially in Topcoder SRM.
•  » » » 5 years ago, # ^ |   0 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...
•  » » 5 years ago, # ^ |   0 Hacks are decisive here.
•  » » » 5 years ago, # ^ |   0 Just if the pretests are weak... :D
 » 5 years ago, # | ← Rev. 2 →   +40 Next competition is only div 2,maybe I solve something :)
 » 5 years ago, # |   +30 What's wrong with system testing?
 » 5 years ago, # | ← Rev. 2 →   0 I opened results before system testing and saw this
 » 5 years ago, # |   +11 Pending system testing...................?
 » 5 years ago, # |   0 Hey, let's start system testing! I want to see these red->purple and green->gray xD
 » 5 years ago, # |   0 Thanks you! Nice contest :D
•  » » 5 years ago, # ^ |   +1 As nice as I couldn't imagine. :|
•  » » » 5 years ago, # ^ |   0 good luck :v
 » 5 years ago, # |   +5 I think system testing is deterioration
 » 5 years ago, # |   +28 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!
•  » » 5 years ago, # ^ |   0 Who knows maybe they are precalculating the results and ratings :D
•  » » » 5 years ago, # ^ |   +4 You are so naive...
 » 5 years ago, # | ← Rev. 2 →   0 I think Codeforces is broken. Take a look at "Pay attention" area...UPD: Already fixed.
•  » » 5 years ago, # ^ |   0 It often happens when contest ends.
 » 5 years ago, # |   +8 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
 » 5 years ago, # |   +11 How to solve problem D of Div. 1? Why many people say that it's easy? Thanks a lot.
 » 5 years ago, # |   +2 Second hour just began...
 » 5 years ago, # |   +25 Anybody else read Problem B statement wrongly? I thought only "edges" on input are allowed to make teleportation graph...
•  » » 5 years ago, # ^ |   0 me too :(
•  » » 5 years ago, # ^ |   0 Isn't it?
 » 5 years ago, # |   -8
 » 5 years ago, # |   -8 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.
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   +18
 » 5 years ago, # |   +6 I resubmitted D a couple of times because I saw I went over the memory limit (259900KB, but still Pretests Passed). 9463550But it looks like my fears were unfounded, because the same submission, using even more memory on system tests, still got Accepted. 9465410Oops.
 » 5 years ago, # |   +62 rng_58 , It doesn't matter what is your rating (or rank)! we will always be your fan!!
•  » » 5 years ago, # ^ |   +42 I guess he had a bet against Petr, which he lost!
•  » » 5 years ago, # ^ |   +70 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.
•  » » » 5 years ago, # ^ |   +5 "I decided to change my strategy" : so what is your previous strategy? Solving in random order? :PI'm sure it is not solving in the order of A to E.
•  » » » » 5 years ago, # ^ |   +10 Solve the problems in the decreasing order of (point value) / (required time).
•  » » » » » 5 years ago, # ^ |   +5 That may not be optimal if you can't solve all tasks. :)
•  » » » » » » 5 years ago, # ^ |   +8 Actually I tried to describe my strategy here: http://community.topcoder.com/stat?c=problem_statement&pm=11357
 » 5 years ago, # |   +21 I will start crying now... Test: #12 ... verdict: WRONG_ANSWER Input 1 30000 30000 Output 0 Answer 1 
 » 5 years ago, # |   +2 The ratings are back to the last ones???
•  » » 5 years ago, # ^ |   0 yeap!
•  » » 5 years ago, # ^ | ← Rev. 2 →   +13 That's because of my prayers :DUPD: I'm going to pray again.
 » 5 years ago, # |   +1 Mmm, guys, what has happened to ratings?
 » 5 years ago, # |   +16 WTF , I had +55 but now it is +50 , why ???
•  » » 5 years ago, # ^ | ← Rev. 3 →   +8 It seems that everybody's rating has decreased by 5 or less..
•  » » » 5 years ago, # ^ |   0 My rating has decreased by 4 pts.
•  » » 5 years ago, # ^ |   0 I had +86, now +84.
•  » » 5 years ago, # ^ |   0 I had +181, but now it is +176(-5). hmm..
•  » » 5 years ago, # ^ |   0 Also decreased by 5 ...
 » 5 years ago, # |   +237 It seems that i've just set a new record for shortest period of being IGM (~20 minutes, i guess :) )
 » 5 years ago, # |   0 Can anyone tell what's wrong with my DFS for Div.2 B? Each node has a vector of pairs 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
•  » » 5 years ago, # ^ |   0 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).
•  » » » 5 years ago, # ^ |   0 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.
•  » » » » 5 years ago, # ^ |   0 I checked all possible colors, as saadtaame said. I added couple of //9467243
 » 5 years ago, # | ← Rev. 2 →   0 I just can't understand how the rating works.. rng_58, whose rating was 2782, got -107. But Antoniuk (whose rating was 2244), and dragonic (whose rating was 2256) both got -102. All of them got 0 points in this round. How could this be possible?
•  » » 5 years ago, # ^ |   +2 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.
•  » » » 5 years ago, # ^ |   0 You may be right. Thanks for your comment, I'll read about the ratings :D
•  » » 5 years ago, # ^ | ← Rev. 3 →   +13 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 was getting -110..-120 for placing last :)
•  » » » 5 years ago, # ^ |   0 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..
 » 5 years ago, # |   0 Will this algorithm work for div 2 D? Find strongly connected components, Turn each SCC to a cycle and keep the remaining edges.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 No. The correct algorithm is above somewhere. (look for Div1-B instead of Div2-D)
 » 5 years ago, # | ← Rev. 7 →   +2 Many Accepted codes of Div-1 A/Div-2 C crushes for this input:1 1 30000Is the input invalid? Or, judge data is weak?This Accepted Code Crashes for the above input.
•  » » 5 years ago, # ^ |   +5 It's invalid, because there are 30'000 islands in total, not 300'000.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 My prog return 1.I guess this is correct answer.UPD: Sorry, didn't notice 3*10^5, not 3*10^4
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 5 years ago, # ^ |   +8 Test case #18 is exactly yours.
•  » » » 5 years ago, # ^ |   0 i don't get it... why this code would crush in my system while it works fine on Codeforces??
•  » » » » 5 years ago, # ^ |   +3 Just a guess: undefined behaviour.
•  » » » » 5 years ago, # ^ |   0 f ends up recursing roughly 30,000 times; my guess is you got a stack overflow.
•  » » » » » 5 years ago, # ^ |   0 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!! :(
•  » » » » » » 5 years ago, # ^ |   +3
•  » » » » » » 5 years ago, # ^ |   +3 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.
•  » » » » » » » 5 years ago, # ^ |   0 that helps a lot.... didn't know that compiler allocates this little space :)
 » 5 years ago, # |   0 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 ?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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).
•  » » » 5 years ago, # ^ |   0 I know that a map has O(logn) but that should still make within the time limit, right ?
•  » » » » 5 years ago, # ^ |   0 As we can see, it shouldn't :(
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 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..
•  » » 5 years ago, # ^ |   0 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).
•  » » 5 years ago, # ^ |   0 So do I. Even I changed map to unordered_map, still got TLE. A tough lesson, QAQ~
 » 5 years ago, # |   +25 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-108611What to say today about Petr and rng_58 :)?
•  » » 5 years ago, # ^ |   +7 Imagine both of them only solving A and B in div2 and placing 800th
•  » » » 5 years ago, # ^ |   +10 Don't be so fast. At most A and B :).
 » 5 years ago, # |   +10 Meh. It's good to have basic knowledge about STL... This got TLE and used 198MB: 9459485And this easily passes all tests using 23MB: 9469360The only difference is changing res += (pars[c][u] == pars[c][v]); to if (pars[c].find(v) != pars[c].end() && pars[c][u] == pars[c][v]) { res++; } 
 » 5 years ago, # |   +42 Finally, after 93 contest I'm in div1 I'm so happy!
•  » » 5 years ago, # ^ |   0 Congratulation to you. What a fighting way.
 » 5 years ago, # |   0 I pass Div1 A and D both through brute force. So lucky and maybe the test cases must be more careful.
 » 5 years ago, # |   +9 Where is the editioral?
•  » » 5 years ago, # ^ | ← Rev. 5 →   +7 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.
•  » » » 5 years ago, # ^ |   +15 But those are the best problems ... :(
 » 5 years ago, # |   -7 When will the editorial be out?
 » 5 years ago, # |   +5 problemset was tough but very nice , problems required more thinking instead of coding that means quality contest.Congratz to authors !!!
 » 5 years ago, # |   +12 I can't open editorials
•  » » 5 years ago, # ^ |   +3 I see no problems for now. Is it fixed?
•  » » » 5 years ago, # ^ |   0 Yes, thanks)
 » 5 years ago, # | ← Rev. 4 →   0 Why my solution get WA on test 10? I can't see anything wrong in my solution...My solutionPlease help me!
•  » » 5 years ago, # ^ |   +3 That URL displays my submissions for me, not yours. Please specify the submission ID.
•  » » » 5 years ago, # ^ |   0 Sorry. I fixed that.
•  » » » 5 years ago, # ^ |   0 He did already ;-)
 » 5 years ago, # |   0 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 ?
 » 5 years ago, # |   0 Can anyone help me and explain why my solution is failing for Div1 Problem A. My Solution id is : 9666602