Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### DarthKnight's blog

By DarthKnight, history, 4 years ago, ,

Hello ladies and gentlemen.

I'm honored to announce you that Codeforces Round #366(or should I say, IOI 2016 opening CF contest) is gonna take place on August 7th and I'm the writer. Please note that the timing is unusual.

As usual, there are 5 problems in each division and duration is 2 hours.

I want to thank LiTi for testing this round, GlebsHP for helping me prepare it and MikeMirzayanov for legendary and unique platforms of Polygon and CF.

The main characters of this round are The Avengers!

I wish you all Accepted solutions and Successful hacks.

Scoring will be posted soon.

Problems are sorted by their expected difficulty, but I strictly recommend you to read all the problems.

GL & HF!

P.S: Top IOI participant in each division (only with handle present in this list) will be rewarded with Persian souvenirs in Kazan.

UPD: Totally unrelated, but since the previous IOI group in telegram no longer exists, here's a new group!

UPD: Scoring is 500 — 1250 — 1250 — 2000 — 2500 in Div.1 and 500 — 1000 — 1500 — 2250 — 2250 in Div.2

UPD: I'm really sorry about the difficulty. System test is about to begin.

UPD: Editorial is out.

UPD: System test is over, congratulations to the winners.

Div.1 winners are:

Div.2 winners are:

Souvenir winners are lawrenceli from team USA and eXeP from team Finland (If that's not true write me in private).

• +116

 » 4 years ago, # |   -27 Cool:D
•  » » 4 years ago, # ^ |   -16 I will be back
 » 4 years ago, # |   -66 kiram to maghzet
•  » » 4 years ago, # ^ |   -61 kiram to kasi ke manfi bede... kalle kiria manfi midin vase chi
•  » » » 4 years ago, # ^ |   +14 namosn mellat nmifhmn chi migi mosbat midn :D
•  » » » » 4 years ago, # ^ |   -75 به تخم چپم که نمیفهمن کصکشا
•  » » » » » 4 years ago, # ^ |   +3 bashe fahmidim toam az in chiza baladi hala gooreto gom kon inja jaye in harfa nist.
 » 4 years ago, # |   -43 A contest for IOIers, prepared by an IOIer. Just how freaking amazing amd is.
•  » » 4 years ago, # ^ |   -32 به تخمم خوب... به نازنین کیرم
 » 4 years ago, # | ← Rev. 2 →   +51 Top IOI participant in each division will be rewarded with Persian souvenirs in Kazan.This remind me of the reflection of zhj who participate in IOI 2015 as China team's member.He said a iran team member gave lyy 300 IRR as souvenir and as return, lyy gave him back 10 RMB. After that they checked the exchange rate...(300 IRR = 0.0664 RMB)(No offense, just saying. I look foward to seeing cool souvenir from iran team too!!)
•  » » 4 years ago, # ^ |   +24 I really don't think that the value of the currency matters because it's a souvenir and I seriously doubt they would want to spend that money anyway.
•  » » » 4 years ago, # ^ |   +23 Yea I think so. It is just funny that they didn't get along with the exchange rate and didn't know how much to give as return as proper. And giving a relatively large amount of money.
•  » » » » 4 years ago, # ^ |   +89 Last year I didn't prepare any souvenir and in the last moment I heard from my brother that in IMO people exchanged their own currencies, so I picked up moneys which I got from my grandpa, those were for 30 years ago and had absolutely no value in cash! However they are really rare and antique somehow :-D I'm sorry for the inconvenience I caused.By the way, this year is different and you can expect many cool stuff :)
•  » » » » » 4 years ago, # ^ |   +31 wow! Then I think it totally worth it. Sorry for the misunderstandings.
•  » » » » 4 years ago, # ^ |   +1 "relatively large amount of money." XDDDAre we seriously creating a discussion which looks like accusing somebody of being a dirty defrauder because of <1,5 USD?
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   +44 lol I don't know how can you read my word as accusing somebody as a defrauder. How can you defraud someone by giving someone money first.I just think nobody would give 10RMB as souvenir as normal. 10RMB is a banknote(normally people would give penny as souvenir). Also 1, 5RMB is also banknote so I think giving 10RMB is abnormal.I apologize if my wordings are shown as offensive as English is not my mother language. I have no intention to say anyone as a defrauder.I agree 10RMB is not much money but I can eat many food and have breakfast using just 10RMB. I would be doubted before I give someone 10RMB as souvenir if the amount of money means nothing and can give other as alternative and the meaning is still the same. That's why I used the word relatively. Or maybe I'm just poor or stingy.
•  » » 4 years ago, # ^ |   0 300 IRR :|
 » 4 years ago, # | ← Rev. 2 →   +11 Are you really confident of using "the Avengers" character? :D
•  » » 4 years ago, # ^ |   +4 I don't think I get the references. Can someone enlighten me, please?
•  » » » 4 years ago, # ^ |   -18 It's Mickey Mouse and Minnie Mouse in front of Kazan Kremlin (IOI 2016 is gonna be held in Kazan).
•  » » » » 4 years ago, # ^ |   +5 Nope, the castle is just located in Disneyland.
 » 4 years ago, # |   +90
 » 4 years ago, # | ← Rev. 2 →   -22 Avengers related contest after Suicide Squad premiere? :D
 » 4 years ago, # |   0 Why is it unrated?
•  » » 4 years ago, # ^ |   +16 The writer never said that it was unrated.
•  » » 4 years ago, # ^ |   -26 It is rated, and I will become purple JIBANCANYANG. that is great, okay gays come on!
•  » » » 4 years ago, # ^ |   0 You would better change "gays" to "guys" because of their meanings! :D
•  » » » 4 years ago, # ^ |   0 Is it funny to say the same thing again and again :|
•  » » 4 years ago, # ^ |   +3 wrong place
•  » » 4 years ago, # ^ |   +61 Forgive me gyus, I mistaken this word as unrated.UPD: Totally unrelated, but since the previous IOI group in telegram no longer exists, here's a new group!
 » 4 years ago, # | ← Rev. 4 →   +14 BTW, there are some teams (like team Kazakhstan) who weren't on my list but are now here. Wouldn't taking handles from that list be a better idea? UPD: he changed it
•  » » 4 years ago, # ^ |   +6 You rewarded with 3rd place in the last contest :P :D anyway good luck bro ^^
 » 4 years ago, # |   +22 Go back to my blue xiaoai. Fighting!
 » 4 years ago, # |   -20 Is it rated?
•  » » 4 years ago, # ^ |   0 Sure！
•  » » 4 years ago, # ^ |   0 Why do people ask this question so many times? Usually the rounds are rated and in the case it ends up being unrated (last contest), it's usually made pretty clear (almost always in bold).Do people just want negative contribution?
•  » » » 4 years ago, # ^ |   +34 I think in this contest people have read Totally unrelated as Totally unrated it happened to me.but in other contests I don't know why maybe it's one of codeforces traditions.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I used to be voted down because of this question. From that, I always find the information in mail! =)) My contribution is negative. You should find by yourself before asking anything.
•  » » 4 years ago, # ^ |   -16 Why negatives??We should know this after the last contest became unrated...
 » 4 years ago, # |   +6 salammanam mikham emtahan konam babinam mosbat midan?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 do most words in your language ends with "en" or "em" ?
 » 4 years ago, # |   +8 Good luck guys! Wish you success!
 » 4 years ago, # |   -6 "Top IOI participant in each division will be rewarded with Persian souvenirs" Should I expect no-math problems ?
 » 4 years ago, # |   +3 I hope everyone will be better!
 » 4 years ago, # |   0 Faghting!!!!!!!!!!!
 » 4 years ago, # |   +27 I hope this round quickly judged. Better rating!
•  » » 4 years ago, # ^ |   0 And do not forget about early publishing of editorials. :)
•  » » 4 years ago, # ^ |   0 Well, this turned out to be a case of being careful what you wish for.(As in, systest will be over very quickly)
 » 4 years ago, # |   +27 Iranian contest always contains full of expected value problems... ~.~
•  » » 4 years ago, # ^ |   +18 really???
•  » » » 4 years ago, # ^ |   -11 kiramo bayad bemally
•  » » 4 years ago, # ^ |   +18 Do you know BWC?
•  » » » 4 years ago, # ^ |   -11 kiram to in website
 » 4 years ago, # |   +12 I wish high rating for everyone :D
•  » » 4 years ago, # ^ |   0 I wish me higher rating than everyone :D
•  » » » 4 years ago, # ^ |   +49 I wish everyone higher rating than you :D
•  » » » » 4 years ago, # ^ |   -16 I wish this round also unrated :D
 » 4 years ago, # |   -8 Good Luck Everyone!!!
•  » » 4 years ago, # ^ |   +2 and may be you are Mr Everyone, right? Nice to meet you! ;)
 » 4 years ago, # |   0 It would be fun with Avengers :D. Moreover so many hacks I guess. GL all :)
 » 4 years ago, # |   -11 Hi my lovely janu bekar13!Have a nice bamboo from amd. :)
 » 4 years ago, # |   -25 Is this contest rated or unrated?
•  » » 4 years ago, # ^ |   +16 Rated
 » 4 years ago, # |   +31 What is the major idea in lots of amd's problems? — Math and Probability I guess
•  » » 4 years ago, # ^ |   -10 In Iran's INOI math , graph theory & combinatorics is very important & also amd is a INOI gold medalist!
 » 4 years ago, # |   +14 I hope to be a pupile in this round , I hate my gray color XD XD motivate me please XD
•  » » 4 years ago, # ^ |   0 why my brother ?
•  » » » 4 years ago, # ^ |   0 Sorry I will be a pupil in the next round ×D
 » 4 years ago, # |   +8 hey 10 mins delay please :(( I'm coming...
 » 4 years ago, # |   0 amd problems that I solved in practice are very test case-y.
 » 4 years ago, # | ← Rev. 2 →   +13 Ignore this comment.
 » 4 years ago, # |   +229 These problems are for Div 0.
•  » » 4 years ago, # ^ |   -6 Div -inf.
 » 4 years ago, # |   0 Hello. I returned after 5 day trip without internet and occasionally found that #366 is running. I could participate during 1h 20min which remain, but why registration is closed, reason?
 » 4 years ago, # |   +5 You know the contest is hard when there are only 27 people in Div 1 who solved B and only one person to solve C when the contest is 80 minutes in....
 » 4 years ago, # |   +4 I think that today no avenger cannot solve all the problems at the time of the contest. Because it is very difficult tasks. ('_')
 » 4 years ago, # |   +11 Fill like "Hawkeye" — so useless.
 » 4 years ago, # |   -103
•  » » 4 years ago, # ^ |   +21 Jesus Christ...
 » 4 years ago, # |   +33 The Avengers take a revenge with their hard problems!!
 » 4 years ago, # |   +7 Nothing to to do when there was 1 hour left... Most difficult round I have participated in.
 » 4 years ago, # |   +14 Hardest contest ever. How to solve Div1B? I tried O(n^2) DP but failed...
•  » » 4 years ago, # ^ |   +3 How did you mask the x positions if you applied dp?
•  » » 4 years ago, # ^ |   0 Can you explain your idea?
 » 4 years ago, # |   0 Thanks for this round. But I still want to say, I feel very terrible now.
 » 4 years ago, # |   +6 After contest ends can somebody explain how they solved Div1 B (Div2 D)?
•  » » 4 years ago, # ^ | ← Rev. 2 →   -19 The solution is trivial if O(n3) dynamic programming algorithm passes 4 seconds limit.I will wait till the submission is allowed and test my solution.
•  » » » 4 years ago, # ^ |   +3 Obviously it doesn't pass
•  » » » 4 years ago, # ^ |   0 Isn't it impossible for O(n^3) to pass in 4s?
 » 4 years ago, # |   +224 Did the author prepare interesting problems? — Yes, he actually did!Did the author prepare interesting contest? — No, absolutely no!
•  » » 4 years ago, # ^ |   0 Even in div2 A and B were very very easy, and C was a little long to code.
 » 4 years ago, # |   +170 May have gone away 1 hour and 53 minutes before the end :|
 » 4 years ago, # |   +34 Anybody else thought that in A the first t notifications are the first t in the stack of notifications like any social app? :D
•  » » 4 years ago, # ^ |   +8 Really I WA many times on that..
•  » » 4 years ago, # ^ |   +11 Wasted 2 WAs because of that :(
•  » » 4 years ago, # ^ |   +5 Oh, so it wasn't translator's fault!6 WAs because of that :c
 » 4 years ago, # |   +34 I hope Codeforces can balance the difficulty next time……
 » 4 years ago, # |   -23 ravash jadid bara mosbat garaftan ina ka nafahman chi migi.
 » 4 years ago, # |   +8 So many people overflowed on 2B, but apparently overflowing is completely irrelevant when just determining whether an integer is odd or even. Sadness.
•  » » 4 years ago, # ^ |   +3 My hack for Div2B was 2 2 1
•  » » 4 years ago, # ^ |   0 Can somebody explain why this happens? , Me too, I had a lot of overflowing solutions in my room and I couldn't find a case to hack them.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 If it is int, then overflowing goes modulo 231. We only need the parity of the sum. Parity doesn't change modulo 231, so overflowing is not a problem at all. UPD: If we check whether the sum is equal to zero mod 2 — we can't hack anything. But if we check whether it is not equal to 1 mod 2 — overflowing works I believe.
•  » » 4 years ago, # ^ |   +6 Noif somebody used if(s%2==1) print 2 else print 1 then we can hack by3100000000010000000001000000000But everyone in my room checked using s%2==0.
•  » » » 4 years ago, # ^ |   0 Yes, since that was the only hackable solution, I too checked all the solutions. Lots of if(s%2), if(s&1), and if(s%2==0), but not one if(s%2==1). Guess there's no justice in this world.
•  » » » » 4 years ago, # ^ |   0 why is (s_int & 1) always equivalent to (s_LongLong & 1) in overflow?
•  » » » » » 4 years ago, # ^ |   +1 You can just think it as if the first bit in int represents -2^32, so it doesn't affect the % operation nor the & operation.Well, technically it does affect % operation, as Dushyant said.
 » 4 years ago, # | ← Rev. 2 →   +1 What is test case 3 in div 2 C?code can anyone see my mistake? please tell me
•  » » 4 years ago, # ^ |   0 n<=q? I fix that then getting AC
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 I'm thinking maybe I misunderstood the problem statement, because my code is behaving as intended on the failed test case!!
 » 4 years ago, # | ← Rev. 2 →   +7 Oh no, I just finished B :(What was everyone hacking on A?UPD: Seems like my B is too slow.
 » 4 years ago, # |   +13 Damn -O2 optimization ;(
•  » » 4 years ago, # ^ |   0 I got 2 unsuccesful hacking attempts because the optimization fixes the O(N) while loop Good to learn that the compiler optimizer does that for next time :)
•  » » » 4 years ago, # ^ |   0 I wonder if they actually knew the optimization would work or just wrote inneficient code and got lucky ...
•  » » » » 4 years ago, # ^ |   0 I have read about it many times(in CF blogs) but I thought 10^14 operations will give TLE even with -O2 optimization. I guess it's best not to hack Div2A for TLE.
 » 4 years ago, # |   +64 I like long statements but this time statements in div1-A and div1-B were so misleading. Reading the same notifications and jumping to the left only when one is small — at least strange.An approach for "Kangaroo" problem from CEOI few weeks ago gives a solution for 704B - Ant Man immediately.But kudos for providing hard problems.
•  » » 4 years ago, # ^ |   +8 Could you give a link to statements and analysis? Thanks.
•  » » » 4 years ago, # ^ |   +13 According to Xellos's comment, their online judge is down.The problem statement was:You are given three integers s, e, N (1 ≤ s ≤ e ≤ N ≤ 2000). Find modulo 109 + 7 the number of paths from s to e that: Each of n vertices is visited exactly once. You can't go twice in a row to the right (e.g. 3 -> 7 -> 9). You can't go twice in a row to the left. The solution is described by muratt's comment — in short go from left to right and keep dp[i][the number of times you move above i].My solution today: 19697314.
•  » » » » 4 years ago, # ^ |   0 Thank you. Really not obvious, that we can do this, it's the NP-problem in common case (I thought that we can create a test where |xi - xj| doens't take part much in the answer).
•  » » » » 4 years ago, # ^ |   0 I've read your solution and the muratt's comment and still cannot comprehend the solution. Could you, please, elaborate a bit more on the method you used?
•  » » » » » 4 years ago, # ^ |   0 Imagine an optimal path. For every position i imagine a vertical line cutting the path j times. The idea is to calculate dp[i][j] — the minimum cost of arranging parts of the path on the left (before i) so that it would go exactly j times through a vertical line over index i. In my implementation j is the number of times the path goes from left to right. So, it must go from right to left j or j + 1 times (the latter if we are between s and e).
•  » » » » » » 4 years ago, # ^ |   0 Is there any proof why this gives optimal solution? Why this can't be applied to generic graphs to solve TSP problem? Is your solution the same as in editorial or it uses diferent idea? If different, do you understand how is it solved in editorial?
•  » » » » » » » 4 years ago, # ^ |   +5 As in any dynamic programming — we consider all possible paths so yeah, we must find an optimal solution. A solution in editorial is slightly more complicated but the idea is the same. Two dimensions of my dp are (I think) the same as two first dimensions of dp in the intended solution. I handle s and e a bit better.
 » 4 years ago, # |   +28 Was Dinic intended in D?
•  » » 4 years ago, # ^ |   -17 Yes
•  » » » 4 years ago, # ^ |   +15 Then why are the constraints so high? I spent about 20 minutes, trying to come up with a faster solution, but in the end I just convinced myself, that it can't be done faster. Do you have any proof, why it works fast? The graph is bipartite, but the capacities are not unit, so I don't think that it works in .
•  » » » » 4 years ago, # ^ |   +26 It works in according to Karzanov's theorems.
•  » » » » » 4 years ago, # ^ |   0 In my solution I also need a binary search around Dinic so it'll be O(E1.5·logN). Does the intended solution do the binary search as well or it's just me?
•  » » » » » » 4 years ago, # ^ |   0 It's just you, though I understand where this log comes from :)
•  » » » » » » » 4 years ago, # ^ |   0 I see, thanks! In this case I can't wait to read editorial to see how to avoid that binary search :)
•  » » » » » » » » 4 years ago, # ^ |   +15 It's not something magically invented to that problem, that is just what needs to be done in typical LR flow, however I admit it is a bit tricky and I also had binary search on my mind for some time. In my implementation I firstly compute flow from s' and t' to find a saturating flow and then compute max flow from s to t on the residual network resulting from previous flow (notation as here: http://web.engr.illinois.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf)
•  » » » » » » » » » 4 years ago, # ^ |   0 Ah, right, instead of minimization we can try to maximize the flow here. In my solution I was always thinking in terms of minimization of the number of blue points (if r > b, then swap blue and red) and that's why I needed a binary search. But in this problem we can instead maximize the number of red points and thus we can solve it without binary search. Thanks!
 » 4 years ago, # |   +78 On the other hand, system testing will be shorter than usual:)
•  » » 4 years ago, # ^ |   +21 Oh! :D
•  » » 4 years ago, # ^ |   +81 So, how to cancel an upvote?
 » 4 years ago, # | ← Rev. 2 →   0 Hi, one of my problems shows as accepted after the contest even though it was rejected before, why is that? Edit: Nevermind
 » 4 years ago, # |   0 Very tough problems — thanks amd for the contest!
 » 4 years ago, # |   +48 The problems were interesting, that's for sure, and I'm eager to find out how B and C are solved, however, the contest itself was very unbalanced. There were too many contestants who were simply stuck after solving problem A. Ideally, the difference in difficulty for every two "adjacent" problems should not be so large.
 » 4 years ago, # |   +5 I think that these problems are difficult to understand
•  » » 4 years ago, # ^ |   0 You got it
 » 4 years ago, # |   +25 Div2.D/Div1.B has pretty strange storyline...
•  » » 4 years ago, # ^ |   +6 Yeah, and it makes no sense.
 » 4 years ago, # |   0 any help for DIV 2B.. I suffered there -_-
•  » » 4 years ago, # ^ |   0 Just sum all arr[i] — 1, and check parity of the sum. If it's even, print 2, if it's odd, print 1.
•  » » » 4 years ago, # ^ |   0 I thought that.. Is there any proof..??
•  » » » » 4 years ago, # ^ |   0 Kynit explained it well, the comment under me.
•  » » 4 years ago, # ^ |   +15 Yeah! A chain of size C will always take C-1 moves before it is reduced to chains of size 1. It doesn't matter what moves the players make — the total number of moves will always be the same. That means you can update the winner just by checking if the new chain has an even or odd length.
•  » » 4 years ago, # ^ |   0 No matter the way they play, they winner will be determined by the number of turns the game takes to end. So, is just a parity check!
 » 4 years ago, # |   0 http://codeforces.com/contest/705/submission/19709431 Some one please tell test case 3 ?? Why is my code wrong ?
•  » » 4 years ago, # ^ |   0 The way you handle the third operation is incorrect. Your code considers whether there are still unread messages for application X if I understood it correctly.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 I think test case like below will break your codeIn the 4th command x[1]>0 but its position is 2. So you should not remove it. 1 1 2 1 1 1 3 1 
•  » » » 4 years ago, # ^ |   0 what should be the actual output for that test case ? And can you please explain in detail what you wrote ? Thanks!
•  » » » 4 years ago, # ^ |   0 I understood the bug ! Thanks a lot !
 » 4 years ago, # |   +11 I received a compilation error with the following message:"Can't compile file:cc1plus.exe: out of memory allocating 5584 bytes"What happened? (I submitted the same code after it and the verdict was another one)
•  » » 4 years ago, # ^ |   +13 Sorry, it happens sometimes because of some memory lacks. I'm finding the way to fix it.
 » 4 years ago, # |   0 In Div2D/Div1B is simple Dijkstra-like approach incorrect? If it is(I guess it is after those results) — why?
•  » » 4 years ago, # ^ |   +4 Because with Dijkstra, how will you guarantee that you've visited every vertex exactly once in your optimal path?
•  » » » 4 years ago, # ^ |   0 Missed that sentence, thanks :) Good thing I couldn't participate
•  » » » 4 years ago, # ^ |   0 I thought that too!
•  » » 4 years ago, # ^ |   0 How you will check that the answer found by Dijkstra passes through all vertices?
•  » » 4 years ago, # ^ |   +5 I solved it with dp
 » 4 years ago, # | ← Rev. 2 →   0 problem C div2 description is very unorganized. you have to jump up and down to make any sense of those variables.
 » 4 years ago, # |   +3 Man I busted real hard after Div 2 A lol. Can anyone explain the logic behind why B was so simple? And I screwed up too many times on C.
•  » » 4 years ago, # ^ |   +1 Check out ghazanfar_iiuc's question above!
•  » » » 4 years ago, # ^ |   0 Ah! That actually makes a lot of sense lol. Dang that was pretty simple I guess. Thanks for the help!
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Generally it is easy to see that if you generate winners for first 10 values or something else...It is classical Grundy theoreme and you can see that for even numbers grundy value is equal to 1 and of odd it is equal to 0. After that in case total xor (it is same as amount of even numbers % 2) = 0 winner is second otherwise winner is first.P.S. You don't need Grundy, it is just checking parity with finding optimal strategy. Anyway I thought as above on the contest.
•  » » » 4 years ago, # ^ |   0 Hmm interesting. I'll take a look at the Grundy theorem sometime soon then. Thanks for the help!
 » 4 years ago, # | ← Rev. 2 →   +5 biggest integer number is odd and after overflow we have even negative number.it is correct for B (if you use int instate of long long int) ||(have overflow).
 » 4 years ago, # |   0 Whether someone else got TLE on d2 third with using set ? I can not understand why that solutions gives TLE and some other solutions with Seg. Tree are correct.My TLE code
•  » » 4 years ago, # ^ |   0 I got TLE on 52nd case. I used mapping to vector
•  » » 4 years ago, # ^ |   0 Dont know about your solution, but I also used set in Div2C and it got AC.19701130
•  » » 4 years ago, # ^ |   0 It should be u = max(u, x + 1) instead of u = x + 1.
 » 4 years ago, # | ← Rev. 2 →   +14 I was cheated by the javascript timer in my computer. When I was going to submit Div1C (2 minutes remaining), bump... The contest is over, :( !@#%. **** I hope my solution is bad, otherwise !@#%.
•  » » 4 years ago, # ^ |   0 It is the first time I get an AC and I felt so sad :( 19734900
 » 4 years ago, # |   +8 Didn't registered for the contest and came 45minutes late, looked at the standings and thought WTF 45 minutes in no Div2 participants solved Antman.It only took me 15minutes to understand all other participants' feelings. I wonder how the Div2D question is solved, it's pretty hard to take delta x into consideration.
 » 4 years ago, # |   +12 By the way, queues are very evil, vectors are much more kind.
•  » » 4 years ago, # ^ |   +3 12MB vs. 260MB... why? Can someone explain?
•  » » » 4 years ago, # ^ |   0 Yep, this doesn't look right; I used queues.
•  » » » 4 years ago, # ^ |   +16 This is known problem, deque allocates way too much memory to store elements in it. Queue is using deque as a container for values by default.
•  » » 4 years ago, # ^ |   0 So strange!
 » 4 years ago, # |   +68 As a chinese netizen, I devoted myself to the great Chinese network. When there are 10 seconds to the end, I submitted a solution of B(I think it is correct because I stress tested it). And then when I refreshed the page, it says the solution wasn't submitted. If the contest was 5 seconds longer I could have made it submitted. :(
•  » » 4 years ago, # ^ |   -10 Chinese network is the greatest in the world :D
•  » » 4 years ago, # ^ |   -10 +1s!
•  » » 4 years ago, # ^ |   -10 +1s!
 » 4 years ago, # |   +13 understanding the description is harder than solving the problems
 » 4 years ago, # |   +41 I think the contest is not div1 but div0...... It's too hard!!!
•  » » 4 years ago, # ^ |   0 May it unrated?
•  » » » 4 years ago, # ^ |   0 No way.And it shouldn't be turned into unrated: the problems were hard, but that's all. It should only be turned unrated if it's unfair, and it was completely fair.
•  » » » » 4 years ago, # ^ |   +16 http://codeforces.com/contest/547/problem/D -> http://codeforces.com/contest/704/problem/D (with solution fitting to both problems here: http://codeforces.com/blog/entry/18126?#comment-230210)...
•  » » » » » 4 years ago, # ^ |   +29 Hoho, stealing comments on CF, I haven't seen that one on CF :D.
•  » » » » » » 4 years ago, # ^ |   0 Maybe he didn't know how to share the link to your comment!
 » 4 years ago, # |   +3 wish you all high rating:D
 » 4 years ago, # |   +10 How to solve DIV 2-C
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Deques: deque > q — store all added notifications, deque a[N] — added notifications for each app. int ans = 0, cnt = 0; deque> q, a[N]; // ... for (int i = 0; i < q; ++i) { if (type[i] == 1) { a[x[i]].push(cnt); q.push(make_pair(cnt, x[i])); ++cnt; ++ans; } else if (type[i] == 2) { ans -= a[x[i]].size(); a[x[i]].clear(); } else { while (q.front().first < x[i]) { if (a[q.front().second].front() == q.front().first) { a[q.front().second].pop(); --ans; } q.pop(); } } } Something like this :)
•  » » » 4 years ago, # ^ |   0 Could you explain this ?
•  » » » » 4 years ago, # ^ | ← Rev. 5 →   +6 Sure, firstly, we just add notifications one by one to deques (q — all notifications, a[x[i]] — notifications of the x[i]-th application). Add means push cnt value to deques, cnt — number of current notification, in other words, the number of queries of the first type. So we could notice, that all numbers in each deque will be sorted. We want to store there only non-readen notifications.Secondly, ans — number of non-readen notifications, for 1 type: just increase by one ans, for 2 type: we decrease ans by a[x[i]].size(), because we read all non-readen notification, for 3 type: a little bit more complex.Thirdly, 3 type, we need to remove all notification from common deque, that have number less than x[i], but we should descrease answer only this number presents in the app deque. So, all deques are sorted, we have pair on top of the q (which means: first — number of notification, second — number of application), then we need to remove this notification from application. So we do this like for two-pointers problem.In conclusion, we add and remove one notification from deques one time, so complexity is O(n + q).
•  » » 4 years ago, # ^ |   +2 msg apps[n]; // app[i] stores information about all the messages of application i. int message_queue[max_messages]; // message_queue[i] stores index of app responsible for message i. int curr_unread_message; // index of the message in message_queue[] that is not currently read. int queue_end; // index of the next to last message in the message_queue int total_unread_messages; // total amount of unread messages from all the apps.  Probably, the most interesting part is msg structure: apps[i].unread_messages = 15; // 15 is total amount of unread messages by from app i. apps[i].queue_index; // The index in the message_queue[]. All the messages of app i in the message_queue before index apps[i].queue_index are read by Thor. When comes the query of the seconds type, we change that value: apps[i].queue_index = queue_end.
 » 4 years ago, # |   0 Not Happy....Problem set.
 » 4 years ago, # | ← Rev. 2 →   +107 It looks like in order to perform well in amd's contests it is profittable to get well acquainted with his previous contests :D.http://codeforces.com/contest/547/problem/D -> http://codeforces.com/contest/704/problem/D (with solution fitting to both problems here: http://codeforces.com/blog/entry/18126?#comment-230210)http://codeforces.com/contest/536/problem/E -> http://codeforces.com/contest/696/problem/E (those are not that similar, but HLD is a rarely used method)
 » 4 years ago, # |   +5 Is any solution for Div1-C with simple implementation?I solved this problem but i could n't implement cause it was so long!
•  » » 4 years ago, # ^ | ← Rev. 3 →   -17 Sorry, wanted to answer the comment above.
•  » » » 4 years ago, # ^ |   +5 He asked for Div1-C not Div2-C...
 » 4 years ago, # |   0 Can anyone tell me why this gives a compilation error? 19690653It should give a WA (or undefined behavior, I guess) because of the s[i] instead of s[1], but it compiles fine on my PC and in custom invocation, and I don't understand the compilation error: Can't compile file: cc1plus.exe: out of memory allocating 65536 bytes 
•  » » 4 years ago, # ^ |   0 Could it be because of the way the file is encoded?http://stackoverflow.com/questions/27588296/running-gcc-on-c-source-file-on-linux-gives-cc1plus-out-of-memory-allocati
 » 4 years ago, # |   0 How to solve DIV 2-D........n^2 -DP ? Maybe?
•  » » 4 years ago, # ^ |   +3 I solved it just by adding chairs one by one. Just insert them in the optimal place in current path. So you are right, it is something kind of DP.
•  » » » 4 years ago, # ^ |   0 orz! rank1!
•  » » » 4 years ago, # ^ |   0 I don't really understand why this solution can solve this problem. Could you please explain it to me or give me some proof about the correctness ^_^.p.s I think this solution is kind of a greedy solution.
•  » » » » 4 years ago, # ^ |   0 How do we know that this greedy solution works?
 » 4 years ago, # | ← Rev. 2 →   0 v
•  » » 4 years ago, # ^ |   0 I don't quite understand your code... But it seems that you are considering cycle by cycle, since you are setting x and y to 0 whenever a new cycle is added.
 » 4 years ago, # |   +4 You would better make this contest unrated -_-
 » 4 years ago, # |   0 I'm surprised E does not have any submission in Div2 and D does! E was definitely felt easier D.
 » 4 years ago, # |   0 I got TLE on third with O(n) solution. This becomes funny :D
•  » » 4 years ago, # ^ |   0 Same idea and same TLE well dunno why it doesn't work
•  » » 4 years ago, # ^ |   0 Me too, TLE with O(2*N)... :/
•  » » 4 years ago, # ^ | ← Rev. 3 →   +2 It seems that many people are getting TLE43 on Div2C with the O(n) solution where you take a vector and then keep track of the most recent deleted location.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 i used the same idea as yours ... but i am not able to figure out why it is failing in pretest 4 ... my code http://codeforces.com/contest/705/my#edit : ok a silly mistake ... i changed index = no +1 to index = max(index,no+1) and it got accepted .
•  » » 4 years ago, # ^ |   +3 u = x + 1 is causing troubles when x + 1 < u. Rather make it u = max(u, x + 1). Queries like 3 100000 -> 3 1 -> 3 100000 -> ... will break your solution...
•  » » » 4 years ago, # ^ |   0 Well that was a simple mistake haha thanks for your help ! It won't happen next time for sure
•  » » » 4 years ago, # ^ |   0 I not to miss that case, nice hack :P In last time with this queries, I am always think that queries are sorted. My bad!
 » 4 years ago, # |   0 Could somebody tell me what's the type of the problem C of div 2? I Had a really hard time solving it,and I wonder if I want to solve a problem like C of div 2 in this contest next time,what should I learn? Is there some problems like this or some tutorial I can refer to?
 » 4 years ago, # |   +29 Does anyone have an idea, what might be the purpose of the function lucky_test() in 19691627 ?
•  » » 4 years ago, # ^ |   +49 adrenaline
•  » » » 4 years ago, # ^ |   +39 considering there's no srand, I'm not sure it's for adrenaline.
•  » » » 4 years ago, # ^ |   -10 I am sorry, but I still did not understand the purpose of lucky_test().
•  » » 4 years ago, # ^ | ← Rev. 2 →   -25 To generate random input for the program and test your implementation. You can implement 2 solutions: bruteforce and clever one. Then use lucky_test() to compare results: bruteforce(a, b) == clever_solution(a, b). I read once again the usage of the function... well, probably it is really for adrenaline :)
•  » » » 4 years ago, # ^ |   0 Comparing your bruteforce() and clever_solution() has nothing to do with this lucky() function...
 » 4 years ago, # |   0 System testing is slow as hell
 » 4 years ago, # |   +1 Thanks for tough but interesting problems, amd! And for lightning-fast editorial!
•  » » 4 years ago, # ^ | ← Rev. 6 →   0 congo u were great during contest
 » 4 years ago, # |   0 Thanks for the early Editorial! I hope this continues in future contests .
 » 4 years ago, # |   0 Heck! :\ Used set instead of queue in DIV2C. Thought it won't affect much. But here i am with TLE on 43rd case. :'( Hurts!
•  » » 4 years ago, # ^ |   +9 I used set and it worked. Your solution handles incorrectly the third query. You should change "last = t" to "last = max(last,t)" or something like that!
•  » » » 4 years ago, # ^ |   +3 Woh! Crap! I was initially using a separate 'if' to handle cases greater than 'last'. Later, I wrongly assumed that loop condition was taking care of everything automatically and removed the 'if'. Didn't notice that 'last=t' wasn't handled by 'for' loop condition. Thanks for pointing that out, I really appreciate that.
•  » » 4 years ago, # ^ |   0 http://www.codeforces.com/contest/704/submission/19712670 segment tree with lazy update solution :D if segment tree can work set should definitely work
 » 4 years ago, # |   +57
 » 4 years ago, # |   +4 Why my submission for problem 705a is wrong at tests 11 19688500
•  » » 4 years ago, # ^ |   0 I have resubmitted your code again and ... it's AC!!!
 » 4 years ago, # |   +5 So Avengers have won the match :P
 » 4 years ago, # |   0 What is the greedy solution for Div2D/Div1B?
•  » » 4 years ago, # ^ |   +37 First add to the current path two chairs: s and e. Then, go through all other chairs and add them one by one to the path. For each chair, find the best position in current path where it should be placed. The best position is the one for which the total time for new path will be minimal.
•  » » » 4 years ago, # ^ |   +42 I literally have no idea why this works, but so far we were unable to find countertest.
•  » » » » 4 years ago, # ^ |   0 Me too. But I believe there is a proof.
•  » » » » 4 years ago, # ^ |   0 I was considering this solution but didn't wrote it cos I couldn't it. Still not convinced it's correct :d
•  » » » 4 years ago, # ^ |   0 Seriously? How does this work...?
•  » » » 4 years ago, # ^ | ← Rev. 8 →   0 It seems like, it can be proved (or disproved ;) ) by induction.For n = 3, it is valid to insert new vertex v1 in the middle: ( s, v1, e).For n = 4, after we've inserted v1, we can only choose between 2 configurations: ( s, v2, v1, e) and ( s, v1, v2, e). Let's say the configuration ( s, v2, v1, e) is better than ( s, v1, v2, e). Now consider the fifth vertex v3. We have two choices:1. Try adding v3 to the winning configuration.2. Try adding v3 to the loser configuration. Then we get two sets of possible configurations:  After adding v3 to the winning configuration:1. C1 = ( s, , v2, v1, e), C2 = ( s, v2, , v1, e), C3 = ( s, v2, v1, , e)  After adding v3 to the loser configuration:2. D1 = ( s, , v1, v2, e), D2 = ( s, v1, , v2, e), D3 = ( s, v1, v2, , e) Now compare the pairs of configurations: (C1, D1), (C2, D2), (C3, D3). If configurations Ci always give better result than Di, then induction worked and solution is correct. Otherwise, we can construct a counterexample to that greedy solution. Start with pair (C1, D1): C1 = ( s, , v2, v1, e) and D1 = ( s, , v1, v2, e).The configuration D1 is better than C1 only if the time of the jump T(, v2) is significantly bigger than T(, v1).For pair (C2, D2) we need to compare T(v2,  ) + T(, v1) and T(v1,  ) + T(, v2).And for the pair (C3, D3) we need to compare T(v1,  ) and T(v2,  ). If you know how to proceed with the proof, please write the comment.
•  » » » » 4 years ago, # ^ |   0 But how do you take delta x into consideration? It changes position by position so you can't only consider the best pair of a[]d[] or b[]c[] right?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I believe this case: 5 1 2 8 10 12 16 17 18 20 17 16 21 2 20 5 13 17 8 8 10 12 15 13 12 4 16 4 Fits the property that ( s, v2, v1, e) is better than ( s, v1, v2, e), but it also has Sequence C: 125 132 130 Sequence D: 130 131 138 So the greedy still holds (as 125<130), but each comparison C_i
•  » » » » » 4 years ago, # ^ | ← Rev. 4 →   0 Ok. It means that in order to disprove the algorithm we have to find an input with the property that minimum time in the winning configuration is worse than the minimum time in the loser configuration:min{T(C1), T(C2), T(C3)} > min{T(D1), T(D2), T(D3)}. I think, at first it would be easier to find the case when mini{Ci} = minj{Dj} and then tweak it to find counterexample or some restriction will show up which we will use to prove the general induction step.
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I tried generating random sample cases and the greedy still passes. I did observe two trends, one of which I know how to prove: C1+C2+C3 <= D1+D2+D3 (by simple cancellation and algebra) There exists i,j so that C_i=D_j (not sure of the specifics of a proof, just something I noticed from samples)
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 Consider this exampleConsider each edge that's not drawn as very big integer. The greedy approach will build path s->e, then s->1->e, then s->2->1->e, then s->3->2->1->e. The weight of s->3->2->1->e is 2+2+2+2, but the weight of s->3->1->2->e is 2+1+2+2 which is less. If I'm not mistaking this should be a counterexample. What do you think?
•  » » » » » 4 years ago, # ^ |   0 Ah, except this graph is not possible, as the cost from 1 to 3 can't be one. T(3,1)>T(3,2)=2 because of the ordering of x_i. That's why when you do the greedy out of order you get WA, but when you process them in order it works.
•  » » » » » » 4 years ago, # ^ |   0 Here's a proof that the greedy works for a special case of n=5. First, denote X(a1,a2,a3,a4,a5) as the total time of the past (a1,a2,a3,a4,a5). The approach is to consider an optimal length 5. We want to show that when you remove v5, you have an optimal path length 4.The special case is that: s=v1,e=v2, and (v1,v3,v4,v5,v2) is optimal.Thus, since it is optimal X(v1,v3,v4,v5,v2)<=X(v1,v4,v5,v3,v2). Writing out each T, you obtain: (x3-x1+d1+a3)+(x4-x3+d3+a4)+(x5-x4+d4+a5)+(x5-x2+c5+b2) <= (x4-x1+d1+a4)+(x5-x4+d4+a5)+(x5-x3+c5+b3)+(x3-x2+c3+b2). Which reduces to a3+d3 <= b3+c3. However this is exactly the statement that X(v1,v3,v4,v2)<=X(v1,v4,v3,v2), if you cancel variables on both sides.
•  » » » » » » » 4 years ago, # ^ |   0 I see your point. Seems like the ordering makes a lot of problems.. I considered the problems is equivalent for the problem for random graph (positive integer weights) but actually it isn't T_TI don't agree T(3,1)>T(3,2) because the a, b, c and d values can be set such that this is incorrect. (but still you convinced me that the whole graph couldn't be random). Seems like I should spend more time on proving / disproving.This special case of n=5 is too specific. Do the same arguments hold for other (all) cases of n=5?
•  » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 Yes I made a mistake, T(3,1) is not necessarily greater than T(3,2), but there is an ordering property. My specific example isn't terribly helpful, but it does motivate the idea of trying to compare path permutations to reduce to the result of the smaller inequality. Thus I wrote a program to do this. It uses the same method that Pixar started. However, as I mentioned earlier, it is not true that C_i<=D_i for each i. But if you rearrange the D_i, depending on what s and e are, you can get C<=D. Here are my results and the source code: I can explain what the output means for one example, s=1,e=2. 1 -> 2 0 0 -1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 1 3 4 5 2 vs 1 4 5 3 2 0 0 -1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 1 3 5 4 2 vs 1 5 4 3 2 0 0 -1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 1 5 3 4 2 vs 1 4 3 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 The five by five grids are the coefficients of a1,a2,a3,a4,a5,b1,b2,b3,b4,b5 etc. in each inequality (when it's all reduced and moved to the right). E.g. 1 3 5 4 2 vs 1 5 4 3 2means X(1,3,5,4,2)<=X(1,5,4,3,2) which is equivalent to 0<=-a2+b2+c2-d2, which is the known inequality at the top. At the very top is the inequality X(s,v3,v4,e)<=X(s,v4,v3,e). (If the opposite is true, all the signs below can be flipped.) Thus this shows that C_1<=D_3 (they're equal actually), C_2<=D_1 (as this reduces to the starting inequality for a path of length 4), and C_3<=D2 (similarly).Some observations that may be able to generalize: There always equals i and j so that X(C_i)=X(D_j). I believe the comparison is always a shift of D, i.e. the solution is either (C_1,C_2,C_3)<=(D_1,D_2,D_3),(D_2,D_3,D_1), or (D_3,D_1,D_2) EDIT: After more carefully reviewing my results I observed that this second observation is not true.Source code: http://pastebin.com/m4YPJK7tOutput: http://pastebin.com/W1kC7SeB
 » 4 years ago, # |   0 what do you call this!? :O
•  » » 4 years ago, # ^ |   0 that time.....
•  » » 4 years ago, # ^ |   +6 I guess you call this a fail.
•  » » » 4 years ago, # ^ |   0 fail? korla.march is 1st bro. and his D accepted just 7s before finish!
•  » » » » 4 years ago, # ^ |   +3 It only shows "Hotlink is not allowed" on my side.
 » 4 years ago, # |   +3 Now waiting for contest with DC heroes :)
 » 4 years ago, # | ← Rev. 2 →   -52 CHEAT:user "Deemo" cheated in #366. he used fakes to see if both of his solutions were right or not. and after that he submit them with his own account. Trust me. I know him and his evil plans.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +19 Well I guess he didn't solve A fast and waited to see if he can solve B or not (and if yes submit A after that)
 » 4 years ago, # |   -22 Auto comment: topic has been updated by amd (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   0 Compare 19711616 and 19711892, first one in java second c++.
 » 4 years ago, # |   +1 Please could someone explain, why this 19701013 solution got AC? İt's complexity is O(n*max(ai)).
•  » » 4 years ago, # ^ |   +5 Maybe optimized by compiler
 » 4 years ago, # | ← Rev. 2 →   +3 Thanks for interesting problems and kind of boring round )
 » 4 years ago, # |   +44 This is the only contest announcement I have seen that has negative contrib :O
•  » » 4 years ago, # ^ |   0 My oh my!
•  » » 4 years ago, # ^ |   -21 And you got positive contribution by writing about negative contribution :)
 » 4 years ago, # |   -62 It is not good at all to announce a round only in English. Minus.
 » 4 years ago, # |   0 I don't understand Div2 B as my poor English.Who can explain it?
 » 4 years ago, # | ← Rev. 2 →   0 Could anyone explain why this solution got TL? (Problem C(div2) / A(div 1))
•  » » 4 years ago, # ^ |   0 I found the reason
 » 4 years ago, # |   +93 Guys, come on, I don't understand amount of downvotes. Tasks were nice, there were no major issues with them. Nothing bad in having challenging tasks. When did solving only those problems we are able to become hotter than facing challenges :)?
 » 4 years ago, # |   0 Hello,Please help me to understand if 20th test #3 to task C "Thor" is wrong or not. I get "wrong answer 20th numbers differ — expected: '2', found: '1'"it`s only one application 17th row: 2 1 (my answer 0 is correct) 18th row: 1 1 (my answer 1 is correct) 19th row: 1 1 (my answer 2 is correct) 20th row: 3 1 (my answer 1 is INCORRECT, — expected 2)But I am sure it should be 1.
 » 4 years ago, # |   0 Can anyone help me debug my code submission for Div2 C problem-Thor
 » 4 years ago, # | ← Rev. 2 →   +11 this amount of downvots are bother me more than they bother amd the tasks were superb , they were very tricky and difficult now this is the last contest for amd , here thank you a lot AMD I will miss your contests
 » 4 years ago, # |   +20 I don't know about you, but I feel that this was one of the best contests I have ever taken part in. It was obviously much harder than a regular CF round, but the problems felt so unique and original, and the solutions were beautiful (and not that hard to comprehend, to my pleasant surprise). Great round!
•  » » 4 years ago, # ^ |   0 Did you comprehend the solution to the ant man problem?
•  » » » 4 years ago, # ^ |   0 here I explained my solution , hope it will help you
•  » » 4 years ago, # ^ |   -15 I agree with you...
 » 4 years ago, # |   -6 in soalash kojas daghighan? :|:|:|
 » 4 years ago, # | ← Rev. 2 →   0 Can anyone tell me about #366 Div1.B(Div2.D)? I can't understand this problem exactly. I thought that this problem is TSP(travel salesman problem).What is different TSP and this problem? Isn't it N! the number of cases jump to chair number e from number s?
 » 4 years ago, # |   -26 Guys, please stop complaining about this round, because there have been much worse rounds on Codeforces) Thanks)
 » 4 years ago, # |   0 Sorry ,I want to know where is Tutorial.
•  » » 4 years ago, # ^ |   +8
•  » » » 4 years ago, # ^ |   0 Thanks