By adamant, 4 years ago, translation, ,

Hi everyone!

Yeah, you guessed it right, after a long four month break after the latest div. 1 round which was not dedicated to any official competition, you will once again have the unique opportunity to participate in usual codeforces round. No t-shirts for top-x competitors! No multi-level selection system for the opportunity to compete in final! No esoteric languages or marathon-like problems! We even will not tell you the scoring untill the very end of the round! That's it, like the good old days.

So this round was prepared for you by Ivan Smirnov (ifsmirnov) and me (adamant). We want to thank Max Akhmedov (Zlobober), Alex Frolov (fcspartakm), Edvard Davtyan (Edvard) and Mike Mirzayanov (MikeMirzayanov) for the help in round preparing, and useful advice. Special thank to Edvard for taking the role of coordinator this time and traditionally MikeMirzayanov for polygon and codeforces systems.

Good luck to everyone! We really hope that you will have a lot of fun participating in this round :)

UPD. Score distribution:

Div. 2: 500-1000-1500-2000-3000

Div. 1: 500-1000-2000-2000-3000

UPD. 2. Also thanks a lot to Alex Fetisov (AlexFetisov). Forgive me, please, I have totally forgotten about you :)

UPD. 3. If you missed the editorial, you can find it here.

• +694

 » 4 years ago, # |   0 My nerves are thin after previous contests, I hope one amazing and interesting round ! Good luck and without frustrating bugs :)
 » 4 years ago, # |   +26 Hahaha.. This blog has been written so well.. Waiting for tomorrow...
•  » » 4 years ago, # ^ |   -82 প্রিয় গ্রাহক বায়োমেট্রিক সিম নিবন্ধনের শেষ দিন কাল। আর অপেক্ষা না করে ১ কপি ছবি, ভোটার আইডির কপি ও সচল সিমসহ এয়ারটেল বায়মেট্রিক পয়েন্টে আজ-ই চলে আসুন।
•  » » » 4 years ago, # ^ |   +95
•  » » » 4 years ago, # ^ |   +12 MR Airtel,Nice to see you here. I am pretty damn sure you are not here to code but this is totally disgusting. We already know that you have a big business to work with but do leave others doing their work. Don't just pop out everywhere and say things like this. If you are here to code, then great. Other than that, Here is a bit of tutorial for you. char c='F'; char c2='*'; cout<
•  » » » 4 years ago, # ^ |   0 I think some regular contestant has created a fake ID to make fun.
•  » » » » 4 years ago, # ^ |   0 i agree with u bro....
•  » » » 4 years ago, # ^ |   +21 I am too lazy to translate, what was written there?
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 It says tomorrow is the last day of 'Sim Registration'. So hurry up.... :3
 » 4 years ago, # | ← Rev. 4 →   +52 When i first see adamant is the author of the contest, my first impression is.. i have to read about policy based DS(if you know what i mean :D )
•  » » 4 years ago, # ^ |   +27 I don't know... What do you mean?
•  » » » 4 years ago, # ^ | ← Rev. 6 →   +32 You are the only source i found explaining the (policy based DS) in your blogs here here and here, and in the last round when i saw your submission 17490448 ( less than 20 lines on E div1 :D ) using (policy based DS). so i think you might prepare problems which is solvable with this (policy based DS). that's it.
•  » » » 4 years ago, # ^ |   0 Sorry,but where is the solution?QAQ
•  » » 4 years ago, # ^ |   +49 So that's who is responsible for all these pbds-clang-incompatible solutions. Every time I need to compile them (with clang) in education round I have to delete this stuff.
 » 4 years ago, # |   +44 "We even will not tell you the scoring untill the very end of the round!" — didn't you mean very beginning of the round :P?Btw, I will keep some suffix array prepared for tomorrow :D.
•  » » 4 years ago, # ^ |   +30 No, I meant very end of the round.
•  » » » 4 years ago, # ^ |   +10 So, are you simply not counting making it public at the start of the contest as telling?Btw, is it rated?
•  » » » » 4 years ago, # ^ |   +51 All I can say is that we don't yet know the opposite.P.S. You should definitely have asked this question right after the post appeared to get more upvotes!
•  » » » » 4 years ago, # ^ |   +43 How about dynamic scoring? :) You don't really get to know the scores until the end of the round.
•  » » » » » 4 years ago, # ^ |   +86 We will consider this, thanks for brilliant idea!
•  » » » » » » 4 years ago, # ^ |   +35 It can be concluded from announcement that you really like usual rounds, so better keep it static :PBtw sometimes it is hard to get the irony in the Internet, but I hope that your post was pure irony :P.
 » 4 years ago, # |   +37 I have missed so many contests in 2016 because the power and the internet are always cut off at 23:30 UTC+8 in my school. But this contest is next to the holiday so that I can fight again! I wish I won't forget the feeling of algorithm competitions.
 » 4 years ago, # | ← Rev. 3 →   +3 666 is the sum of the first 36 natural numbers and thus it is a triangulal number.Notice that 36 = 15 + 21; 15 and 21 are also triangular numbers; and 15^2 + 21^2 = 225 + 441 = 666.What we see here? Triangles in the perspective. We must go deeper! Do not you think it's like this?The largest pyramid in Egypt is the Pyramid of Cheops (IV Dynasty), the Pyramid of Khafre (IV Dynasty), Red Pyramid, Sneferu (IV Dynasty).(IV + IV + IV) : 3 = 4In the perspective appearance of divisions 4 officially confirmed.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +26 666 is also a special and popular number in China. When we Chinese see something is so cool or so amazing, we will say it is "666" or "66666666666"(very 666). This special meaning of this simple number begins just in these years. Similar with 666, 233 is another special and popular number in China, which means "LOL" -- Lots Of Laugh. If we Chinese see something is funny or ridiculous, we may say "233" or "2333333333333333333333" (very 233).
•  » » » 4 years ago, # ^ |   +31 Ah, that's why his handle was 2333333333333. :D Source.
 » 4 years ago, # |   -181 No t-shirts for top-x competitors
•  » » 4 years ago, # ^ |   +101
 » 4 years ago, # |   -99 প্রিয় গ্রাহক আপনার সিমটি এখনো বায়োমেট্রিক পদ্ধতিতে নিবন্ধন না করে থাকলে ১ কপি ছবি, ভোটার আইডির কপি ও সচল সিমসহ এয়ারটেল বায়মেট্রিক পয়েন্টে আজ-ই চলে আসুন। মনে রাখবেন, অনিবন্ধিত সিম ব্যবহার করলে সংযোগটি যেকোনো সময় বিচ্ছিন্ন হতে পারে।
•  » » 4 years ago, # ^ |   -50 আরো ডাউনভোট দিলে কিন্তু আমি তারানা আপাকে বলে দিবো !!!
•  » » 4 years ago, # ^ |   -13 MR Airtel, Nice to see you here. I am pretty damn sure you are not here to code but this is totally disgusting. We already know that you have a big business to work with but do leave others doing their work. Don't just pop out everywhere and say things like this. If you are here to code, then great. Other than that, Here is a bit of tutorial for you. char c='F'; char c2='*'; cout<
 » 4 years ago, # |   +9 yesterday my team ended first in our university ACM qualifications, so I hope to carry that achivement in today's round :D
•  » » 4 years ago, # ^ |   -6 Congratulations, was Qwerty your team's name???
•  » » » 4 years ago, # ^ |   0 (1)The team that ended first was named Qwerty. (2)He was in the team that ended first. From (1) and (2) we can see that his team was named Qwerty.
•  » » » » 4 years ago, # ^ |   +41 Such modus ponens, much wow!
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   -10 Well he didn't say what collage he is from,did he?
•  » » » 4 years ago, # ^ |   0 Thanks, yes it's Qwerty from Tishreen university :D
 » 4 years ago, # |   +7 my first contest after a long time I just hope I do this good
 » 4 years ago, # |   +5 Since everyone's sharing their thoughts about the contest I'm gonna share mine too. 3 contests ago I was thinking if I make it in top 200 I'm gonna become purple again, but I failed. So 2 contests ago I was thinking if I make it in top 100 I'm gonna become purple again, but again I failed. So before previous contest I was thinking if I make it in top 50 I'm gonna become purple again, but yet again I failed. Today I need a place in top 5. Wish me luck!
•  » » 4 years ago, # ^ |   +1 Good luck.
•  » » 4 years ago, # ^ |   +5 good luck dude :) , i need place in top 1 to be purple :3 :D
•  » » 4 years ago, # ^ |   +4 haha, I need place in top 1e-3 or better to be purple :P
•  » » » 4 years ago, # ^ |   -59 প্রিয় গ্রাহক বায়োমেট্রিক পদ্ধতিতে সিম নিবন্ধন করে ১৯ টাকা রিচার্জ করলেই আপনি হতে পারবেন purple. মেয়াদ ৩ দিন।
•  » » » » 4 years ago, # ^ |   -21 মাত্র ১৯ টাকা !!!! o.O তাতেই Purple :O :O
•  » » » » 4 years ago, # ^ |   +1 MR Airtel, Nice to see you here. I am pretty damn sure you are not here to code but this is totally disgusting. We already know that you have a big business to work with but do leave others doing their work. Don't just pop out everywhere and say things like this. If you are here to code, then great. Other than that, Here is a bit of tutorial for you. char c='F'; char c2='*'; cout<
•  » » » » » 4 years ago, # ^ |   +35 You know you are almost becoming as much as annoying as the airtel guy. Leave him be and he will lose interest. You don't need to reply on each and every one of his comment
•  » » 4 years ago, # ^ |   0 how long it will take me to be purple ??
•  » » » 4 years ago, # ^ |   +6 depends on you
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 I will be blue before August! Fingers crossed! >_<
•  » » » » 4 years ago, # ^ |   0 It doesn't feel any different ! It's just a color. P.S : I want to be purple before August XD !
•  » » » » » 4 years ago, # ^ |   0 I know that but I feel that I can solve Div2C but I am unable to solve it because I start hacking after solving Div2B which takes half hour to one hour and most of the times it's useless. I feel pathetic about this. That's why I feel I am not where I should be.
•  » » » » » » 4 years ago, # ^ |   0 Cant believe you like debugging more than problem solving!
•  » » 4 years ago, # ^ | ← Rev. 2 →   +9 just don't think about getting rating or your rating wouldn't increase ! well thats totally true for me whenever i think about rating i get my solutions failed so just code without any worries
 » 4 years ago, # |   +73 Finally a chance for me to get back in Div2 :)
•  » » 4 years ago, # ^ |   +9 Me too. Fingers crossed.
•  » » 4 years ago, # ^ |   +5 You can do it :D
•  » » » 4 years ago, # ^ |   +19 And I did it :P
•  » » » » 4 years ago, # ^ |   +8 Look on the bright side. What’s the bright side? You can be the winner of the next Div2 Round.
 » 4 years ago, # |   +44 div.2 E is div.1 D such a usual contest
•  » » 4 years ago, # ^ |   0 That's because div1 C and D share the same full point -- 2000. So it is to say, they think div1C and div1D have the same or similar difficulty.
•  » » » 4 years ago, # ^ |   +21 On my mind the difficulty of problems div1C and dic1D is different for div1 and div2 participants. It is about obvious the problem D is harder, because there tricky cases there. But for div2 participants who not familiar with combinatorics it's about impossible to solve problem div1C while they can come up with the solution for the problem div1D (it is not require some specific knowledges). So I decided and the guys are agreed to give the problem about four points to div2 round.
 » 4 years ago, # | ← Rev. 2 →   -129 CF and its overcomplicated problems are stoooopid! Who needs such hard problems in their life? They making quantum computers and soon all these precious algorithms will become useless. They make fast processors and cheaper memory, and array sizes can be as huge as anything. Any average billionaire can't solve even a div2 C yet they're billionaires. Seriously, what are we doing here? I am never coming back here. My last comment on CF ever!!!!!!I request my account to be permanently deleted.
•  » » 4 years ago, # ^ |   +8 before leaving, can you tell us who you are(your name/organization/..)? I can't realize whom to miss.
•  » » 4 years ago, # ^ |   +5 Finally. I was getting tired of your shit in every thread.
 » 4 years ago, # |   0 In Div. 1 D there is a sentence in the problem statement."Note, though, the problem can include several records in one test, you can hack other people's submissions only with the test of one plate, i.e. parameter t in a hack test should be equal to 1."Does this not go against the philosophy of hacking, which is that any hacking contributes to the best possible set of test cases, and that any incorrect solution should be hackable? There can be solutions you know are sure to fail system tests, but cannot be hacked by any test case (for example, TLE). This seems to implicitly states that the problem setters believe their test cases are best possible and do not need contribution from participants.However, an easy fix could be to change all the system testing to have t = 1 so that hacking and system testing are identical.
•  » » 4 years ago, # ^ |   0 I guess that for this particular problem testing the speed of the solution can be easily done with the tests from problemsetters. And the hacking tests are used for checking the correctness. The other reason is, perhaps, that it just takes too long to check the correctness of the answer provided by the solution, hence the limitation:)
 » 4 years ago, # | ← Rev. 2 →   +3
 » 4 years ago, # |   +4 Aaah, this C is so awesome but I couldn't finish it on time :( We can store the states through every sqrt(100000) numbers, right?
•  » » 4 years ago, # ^ |   +22 Actually we can use the fact that there are only sqrt different lengthes.
•  » » » 4 years ago, # ^ |   0 Oh, yes, mine will be slow, thank you :)
•  » » 4 years ago, # ^ |   +13 Formula for this problem: , where k is the length of s.
•  » » » 4 years ago, # ^ |   0 It seems that I'll get TLE :)
•  » » » 4 years ago, # ^ |   +5 Why does this formula work?
•  » » » » 4 years ago, # ^ |   0 It is derived from recursive formula: f[n][k] = 25 * f[n - 1][k] + f[n - 1][k - 1]. That is similar to the LCS problem.
•  » » » » » 4 years ago, # ^ |   0 It is a two-variable recursive formula, how can you solve it? I just know how to solve some simple forms with one variable such as the Master's theorem form (in Introduction to Algorithm). Can you recommend some mathematical resources for that too? I think it will be very helpful for everyone.Thank you.
 » 4 years ago, # | ← Rev. 2 →   0 why this hack failed? (Div2A)
•  » » 4 years ago, # ^ |   +6 How to solve A? >_<
•  » » » 4 years ago, # ^ | ← Rev. 5 →   +3 I had deja vu, when I was reading the problem. You can read about the idea here.I will summarize very abstractly:1. You need to convert to the same dimensions. That is, you need to convert the speed of gaining new water (because of the rain) to milliliters (because drinking speed is also in milliliters): ee = c × e.c — is some coefficient.2. The whole speed of loosing the water from a cup can be expressed as v - ee milliliters per second. You have some amount of water from the beginning W milliliters and you loose it with the speed v - ee milliliters per second, so the time you have is:t = W / (v - ee) seconds
•  » » » 4 years ago, # ^ | ← Rev. 4 →   0 let's go step wise:- step 1:-convert everything to cm or cm^3 step 2:- initially I have pi*r*r*h step 3:- each second I am giving (pi*r*r*e) cm^3 to the cup and substracting Vcm^3 step 4:- so in x seconds give the cup x((pi*r*r*e)-v)) cm^3 step 5:- formula pi*r*r*h + x((pi*r*r*e)-v)=0 step 6:- (-pi*r*r*h)/((e*pi*r*r)-v)=x substitiute and work it out. it is very pity I was not able to solve any of the problem during the contest due to powercuts if you live in india you know what I mean. more bad rating went down by -97 
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 The relative error was less than 10^-4.
•  » » » 4 years ago, # ^ |   -7 relative error is 0.131386 and its MORE than 1e-4
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +1 That's absolute error. Relative error will be abs(9993.61-9993.74139)/9993.74139 which is less than 1e-4.
•  » » » » » 4 years ago, # ^ |   +3 thanks!
•  » » » » 4 years ago, # ^ |   -10 It's absolute error. Relative error is actually0.00001314677817154782844173184042381306993321477614657486...http://www.wolframalpha.com/input/?i=(9993.61-9993.741385501099)%2F9993.741385501099
•  » » » » » 4 years ago, # ^ |   +3 thank you i didn't know that!
 » 4 years ago, # |   +3 What's wrong with Div2 D's TL? I just spend 30mins to debug. So desperate to optimize some loop and vector's push_back, AND IT PASSED PRETEST!!! It sucks.
•  » » 4 years ago, # ^ |   0 yes same thing here but i could n't correct it because there wasn't any time!very bad sence!
 » 4 years ago, # |   +63 Very hard to read problem statement. I could solve problem A if problem statements were a bit more readable...
•  » » 4 years ago, # ^ |   +9 yes i had the same the problem for A ! without the examples there was no hope for me !
•  » » 4 years ago, # ^ |   +17 My apologies for that :(
•  » » » 4 years ago, # ^ |   0 I didn't see the words "in a row" and I tried to solve it for almost the whole contest only to found it not solvable at all...Maybe I should read the next problem instead of stuck on this one.
 » 4 years ago, # |   +5 It's been so long without a contest I forgot what it feels like...it feels good. I hope everyone has done good.
 » 4 years ago, # | ← Rev. 2 →   0 Geometry kills me in contests. I gotta get better at it.
 » 4 years ago, # |   0 :3 :3
 » 4 years ago, # |   +9 How to solve Div2 D / Div1 C ?None of my ideas ended up fast enough
•  » » 4 years ago, # ^ |   +11 The way I did it was I first did N BFS's to determine the all-pairs shortest paths. Then I made two matrices and put in the first one sorted lists of all the distances (and which cities they were from, courtesy of multiplying by 10000 and adding the city) to a given city and in the second one a sorted list of all the distances (and what cities they were to) from a given city. I then looped through each pair of cities with nonzero distance (these will be the middle two cities in the path), and for each of those pairs I went through the largest three distances from the second city and to the first one. If any of the cities were the same (or the distances zero) I didn't consider that combination (hence why I needed the top three cities in each case). I printed a set of cities with the maximum distance given these conditions. Overall this runs in O(NM) time.
•  » » » 4 years ago, # ^ |   0 Oh I see, ty
•  » » » 4 years ago, # ^ |   +4 O(N^2logN) actually.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +3 del
•  » » » » » 4 years ago, # ^ |   +6 Do You mean O(N^2) ?Yes you can do that by simply instead of sorting keeping a list of the top four cities as you won't need more.
•  » » » » » » 4 years ago, # ^ |   0 Turns out you don't need more than three, since the distance to a city from itself is always zero (and thus, anything lower-ranked than that will be a zero distance as well and will be discountable as a possibility)... leaving you with only two possible conflicts for each list.
 » 4 years ago, # | ← Rev. 3 →   0 Python module "itertools" rocks in Div2E. Hope I won't get TLE or some disgusting WA case I didn't notice. Edit: Oops, actually, there is such a case: 1 0 0 0 3 3 2 3 5 My answer: 2 0 0 0 3 3 0 3 3 Right answer: 1 0 1 0 4 3 1 3 4 And it isn't covered by pretests...
 » 4 years ago, # | ← Rev. 3 →   0 What is the solution for Div2 B? I sorted and took minimum of absolute of ( Prefix_i * 2 — sum + 1) .
•  » » 4 years ago, # ^ |   0 max(maxx-sum+1,sum-maxx+1) , where maxx- maximum element, and sum is sum of all other elements
•  » » » 4 years ago, # ^ |   +4 It is always "maxx — sum +1"
•  » » » » 4 years ago, # ^ |   0 I also do not see a proof. I think it works because it is impossible to form a polygon with what is given.
•  » » » » » 4 years ago, # ^ |   0 Yes, since it is impossible to form a polygon, there must be a side such that its length >= sum of other sides. The optimal way now is to build a triangle with its base as the larger side, the rest sides combined together to a single side with a zero degree angle to this side. So third side would be (total length — sum of remaining sides). But this triangle has zero area, so we need to lift the middle vertex just so that the new side's length increases by 1.
•  » » » » 4 years ago, # ^ |   0 what is the output of div2-B for 4 3 4 4 4i have found some accepted code giving different outputs for this input......
•  » » » » » 4 years ago, # ^ |   0 This is not a valid output since it can already form a polygon of nonzero length. Think about the triangle 8 8 3.
•  » » » » » » 4 years ago, # ^ |   0 I mean input.
•  » » » 4 years ago, # ^ |   0 Fortunately my solution does that LOL.I didn't knew why my solution works but I was trying to build a triangle, I thought of taking up the maximum element only but I couldn't come up with the proof for that either so I checked whether my solution passed the pretest or not.
•  » » 4 years ago, # ^ |   0 I sorted the array, then subtract maximum with first n-1 terms and add 1. Couldn't prove it.Source
 » 4 years ago, # |   0 when will the sytests start ?
 » 4 years ago, # |   0 DIV 2 D(World Tour) involves finding strongly connected components along with topological sorting like tarjan's algorithm right? I just got there but couldn't figure out how to proceed further. Any ideas?
•  » » 4 years ago, # ^ |   +1 Use bfs on all nodes to find All Pair Shortest Paths.Basically my idea is for each pair (b, c), find (a, d) such that (a, b, c, d) are distinct and d(a, b) is maximal and d(c, d) is maximal. (use set or something similar for that)
 » 4 years ago, # |   +2 Please don't start system testing 1 hour later like the last contest!!
 » 4 years ago, # | ← Rev. 2 →   +109 Hello, my name is Alexander, and I like to write things like this (sorry for quality):
•  » » 4 years ago, # ^ |   +4 Writing if (ans > r) { ans = r; ... } saves symmetry. Symmetry saves you.
 » 4 years ago, # |   0 In Problem C Div2 ... I just want to know what is the importance of this sentence "The only restriction — it is not allowed to append the same string twice in a row."for example if I have "xxxxxabab" I cant put ab in the output as I can do like that --> "xxxxxab" — "ab"
•  » » 4 years ago, # ^ |   +4 In this case, xxxxxbcabab you can't get bc as output!
•  » » 4 years ago, # ^ |   0 Suppose you have the string "xxxxxghiabab", note that the only way to obtain the suffix ("ghi") is doing: "xxxxx"+"ghi"+"ab"+"ab". But, with the restriction, it is impossible to obtain that suffix (because you put the suffix "ab" twice in a row).
 » 4 years ago, # |   +8 How to solve div1D? I thought at brute force fixing the direction(OX or OY) and the order othe vertices in the square. After this we get a system of equations but the problem is that it's not uniquely determined. Still, I am pretty sure that we can have at most one free element(the others depend on it), and I guess that now, iterating this free elements throught the integer values that he can take, we get a convex function, so we can ternary search. Unfortunately I am not able to prove the convex function part and there is one more problem with the integer restriction because I'm not that sure that for any fixed integer value we get all the values integer, so the function won't be defined on Z so it doesn't work anymore. Can someone who thinks he solved it tell me how?
•  » » 4 years ago, # ^ |   +8 The editorial will be posted today or tomorrow.As a writer of this problem, I'm also very interested in a solution with binary search.
•  » » » 4 years ago, # ^ |   0 http://codeforces.com/contest/666/submission/17585111I used binary search here to get AC.
•  » » » 4 years ago, # ^ |   +16 The editorial hasnt been posted yet.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 If you know which vertex is, say, the top left one, the direction it will go and an upper bound on the time it has, you also know the segments of possible coordinates for top and left sides of the square. Intersect these segments using the information from all points. Now you can find out the segment of possible values for horizontal and vertical dimensions of the square. These two segments must have a common positive element.So, brute force the permutation, brute force the directions, binary search on the time (which is unnecessary but makes things easier) and intersect some segments.
•  » » » 4 years ago, # ^ |   0 It seems nice and I'm sure in this way it can be done. Still, I don't actually understand what do you intersect. After brute forcing that stuff(I also did this thing) and binary searching the maximum change, you get some segments, knowing that on the first segment the upper left vertice can be found, on the second the upper right, and so on. But How do you actully deal with the remaining problem? It seems possible, but I can't see how. Can you please explain me more thoroughly?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +8 Wrong solution was here before;)
•  » » » 4 years ago, # ^ |   0 Wow how stupid I was. In the cx=cy=2 case, I thought that it's impossible to find a solution and it was actually the easiest case. In this way, the code was much easier to write. Thanks :)
•  » » 4 years ago, # ^ | ← Rev. 4 →   +15 17578532Run the following solution once, swap coordinates, run it once again.Create sets X and Y where X denotes a set of x-coordinates from the input. Iterate over that x1 < x2. Iterate over . Assume that we already have coordinates of 3 sides and run a function check_sq(x1, x2, y, y + |x1 - x2|) and also check_sq(x1, x2, y, y - |x1 - x2|). This function should check 4! possibilities of assigning input points to 4 points (x1, y1), (x1, y2), (x2, y1), (x2, y2). Check my code for implementation details. Also, it's possible that we know only x1 and x2, without knowing any y value, e.g. for test: 5 0 10 0 5 100 10 100 We know x1, x2. Let f(y) denote a function that returns the answer for check_sq(x1, x2, y, y + |x1 - x2|. This function is maximum over 4 functions of form |y - const| so it's also strictly bitonic (it has form const1 + const2·|y - const3|). So, we can ternary search the optimal y, checking the value with already created function check_sq().
•  » » » 4 years ago, # ^ |   +15 Very nice explanation. I've just got AC and event though I wrote about 190 lines, they were very easy to write (about 20 minutes). This solution makes me like the problem. Thanks!
 » 4 years ago, # |   -7 I am not good at English so i don't understand div2 E Also, i spend too much time to understand div2 DI think i should study English Hard T.T
•  » » 4 years ago, # ^ |   +11 I'm also not good at English but I think after a year of training and reading problems, you can understand 99% of problems with simple translator.
 » 4 years ago, # | ← Rev. 3 →   +35 Waiting system test is like waiting prison break season 5.you know the end will be shit , but you still waiting -.- .
•  » » 4 years ago, # ^ |   0 I wish not to see it
•  » » 4 years ago, # ^ |   0 system testing is over , it took less than a minute
•  » » » 4 years ago, # ^ |   0 and the end is shit -_- I failed in B+C and got D accepted
 » 4 years ago, # |   0 How to solve DIV 2C : http://www.codeforces.com/contest/667/problem/C
•  » » 4 years ago, # ^ |   0 how to solve A?
•  » » 4 years ago, # ^ |   +5 It's easy. see this: 17584300
•  » » 4 years ago, # ^ |   0 Dynamic programming from right to the left, storing True or False for every suffix of length 2 or 3 (can this sequence be a suffix or not).
•  » » » 4 years ago, # ^ |   0 Can you provide a code? I was thinking about that but I didn't know how to code it
•  » » » » 4 years ago, # ^ |   0 You can see my submission here, but I suspect you don't understand Python (here is the information about slices and indexing in the string), here are some comments: Codedef main(): ans = set() line = raw_input()[5:] # cut first five symbols size = len(line) # length of remainining string if size < 2: print 0 return if size == 2: print 1 print line return if size == 3: print 2 for i in sorted([line, line[1:]]): print i return # In dp[i][j-2] (j = 2,3, i <= size) we store True if the suffix of length j, beginning with the symbol number i is possible dp = [[None, None] for _ in xrange(size)] dp[-1] = [False, False] dp[-2] = [True, False] dp[-3] = [False, True] ans.add(line[-2:]) ans.add(line[-3:]) for i in xrange(size-4, -1, -1): # i = size-4, size-5,...,0 for j in xrange(2, 4): # j=2,3 dp[i][j-2] = dp[i+j][3-j] or (dp[i+j][j-2] and line[i+j:i+2*j] != line[i:i+j]) # The main line: suffix is possible either if the next suffix of other length is possible or (if the next suffix of the same length is possible !and! it doesn't equal current suffix, because two identical suffices in a row are forbidden) if dp[i][j-2]: ans.add(line[i:i+j]) print(len(ans)) for i in sorted(list(ans)): print(i) 
•  » » » » » 4 years ago, # ^ |   0 Thanks
 » 4 years ago, # | ← Rev. 3 →   +2 Hey, My code fails in sys test 42.. but it gives the correct answer on my system. I have even handled the case it fails on, in my code. Can anyone pinpoint the issue ? Solution link: http://codeforces.com/contest/667/submission/17577331Sorry for the mix up, I took jury's o/p as participant's o/p..
 » 4 years ago, # |   0 For div1c, I derived the mathematical formula which runs in 100000 * 100000 — and used some tricks to prune the runtime for half. I was very nervous since I thought it might fail. but happily, it passed systest (in only 2.4s)!Am I the only one who used pruning?http://codeforces.com/contest/666/submission/17577445
•  » » 4 years ago, # ^ | ← Rev. 4 →   +23 This is incorrect solution. Test: 1e5 string(5e4, 'a') 2 1e5 ... 2 1e5
•  » » » 4 years ago, # ^ |   0 I'm aware of that data, and after submitting C, I tried to run that data at custom invocation — but I failed to run it (idk why, but it didn't work). so I just hoped for a fast calculation + easy testdata :)Whatever, pruning is just pruning :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +36 You are right.It is our fault that there were no such cases in testset. We are very sorry for that. Testcases are added so solutions like yours will not pass in upsolving. However, competition result will not be rejudged since it is considered to be a bad idea to cancel AC after final results are published. You should feel lucky since your solution could be hacked, but it was not. Sorry again.
•  » » 4 years ago, # ^ |   +5 There are only at most different lengths given the sum n, so you can reduce the complexity to .
 » 4 years ago, # | ← Rev. 2 →   -22 Can someone please tell me what is wrong with my answer?
•  » » 4 years ago, # ^ |   +16 you forgot to print "YES"
•  » » » 4 years ago, # ^ |   +1 Oh FML! >_<
•  » » » 4 years ago, # ^ |   0 Now I got AC. Gotta be careful while reading next time.
 » 4 years ago, # | ← Rev. 2 →   0 UDP: Sorry, I have found the ans.
 » 4 years ago, # |   +1 Hacking case for div-2 C is aaxaxabbabbb. many solution with 1D dp failed at this case.
 » 4 years ago, # |   0 Can anyone tell me what went wrong? Solution A
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 Try to change the value of PI from 3.14159 to acos(-1.0).
•  » » 4 years ago, # ^ |   0 You better not set precision.
•  » » » 4 years ago, # ^ |   +1 I tried using %.6f and it worked. setprecision was the reason I got it wrong!
 » 4 years ago, # | ← Rev. 2 →   +2 In Div.2 C, I mistakenly thought a suffix sequence "aa" -> "aaa" -> "aa" is invalid. hahaha.
 » 4 years ago, # | ← Rev. 3 →   0 I tried to hack div2.Problem B.Coat of Anticubism of some users with test case 5 8 4 3 2 1but it said invalid input, but why?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 In input statement, "It is guaranteed that it is impossible to make a polygon with n vertices and nonzero area using the rods Cicasso already has."
•  » » 4 years ago, # ^ |   0 Let's sort them first. 1 2 3 4 8.Now if we add the first 3 rods we have 4 6 8.We can construct a convex polygon with side 4 6 and 8. But the problem says that it is guaranteed that no convex polygon can be construct by the input.
 » 4 years ago, # |   0 i used to think that CF ignores case sensitivity while printing yes/no http://codeforces.com/blog/entry/20020?#comment-248537 http://codeforces.com/blog/entry/22619?#comment-271348 however today my submission for A failed 2nd pretest as i printed Yes instead of YES(-50 :( for re-submission),i guess that changes my notion
 » 4 years ago, # |   +3 I used bisection to solve Div2A. Couldn't find an easier solution -_-
•  » » 4 years ago, # ^ |   +3 me too :p no need to think hard for the right formula , just get it right
 » 4 years ago, # |   0 OK! it's now two contests in a row, getting WA on pretest 2, which is in the samples!!!! This is really getting embarrassing :(
•  » » 4 years ago, # ^ |   0 The subjective and easy to lost points :)) :)) Sometimes me too :(( :((
•  » » » 4 years ago, # ^ |   0 and lossing 226 places in the standings :(
 » 4 years ago, # |   0 Proof that in Div2B it is sufficient to make each side less than sum of others: Let the greatest side be of length d. Then split all other sides into two categories with nearly equal sum of lengths: let us add other sides in length decreasing order one by one into the category with smaller sum of lengths. Then in the end the sums will differ not by  ≤ d, with equality only in the trivial case when all sides are d. Then we can construct a triangle from d and concatenated sides from each of the categories, because all three triangle inequalities are satisfied.
 » 4 years ago, # | ← Rev. 7 →   +22 Many solutions on Div2A would fail on the hack test by user sid02hack test is: 2 5 3927 1250correct answer is: 1710.545730564287for example:17576065 output is: 1575.3817569724 output is: 1570.79600017574966 output is: 1693.1517570584 output is: 1570.817569909 output is: 1698.158217571073 output is: 1698.1581622I was wondering why it wasn‘t added to the final system tests...
•  » » 4 years ago, # ^ |   0 All the successful hacks should have been added. If it wasn't it means there was a bug and that task should be rejudged.
 » 4 years ago, # |   0 how is NrootNlogM complexity passing for E in 2 seconds. its way more than 10^9 operations.
•  » » 4 years ago, # ^ |   +8 And time isn't 1 second? :P
 » 4 years ago, # |   +1 When will the editorial be posted?BTW how to solve div2/C ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 They will be posted as soon as possible. Div. 2 C is simple DP. Assume we reversed the string. Then DPlen[i] — is it possible to split s[1..i] in suffixes in such a way that last would have length len. Then you can use following formulas: . Similarly
•  » » » 4 years ago, # ^ |   0 Thank you very much. I will try solving it.
•  » » » 4 years ago, # ^ |   0 Completely ****ed up with this problem..... thanks man!
•  » » » 4 years ago, # ^ |   0 Does this case "zzzzzpbpppb" exist an ambiguity in the meaning of DP? The first "pb" (from left to right) cannot be chosen because there is another "pb" on its right, However its DP value is true.
•  » » » » 4 years ago, # ^ |   0 But it can be chosen. zzzzz|pb|pp|pb is correct partition.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 How? pb is repeating here.Is this valid partition? zzzzzpb | pp | pb
•  » » » » » » 4 years ago, # ^ |   0 Yes, this partition is also valid. The only restriction — it is not allowed to append the same string twice in a row.
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 zzzzzpb | pp | pb is validbutzzzzzpb | pb is not validbecause pb is "twice in a row" in second case.
•  » » » » » » » » 4 years ago, # ^ |   +10 The appended strings can't be twice in a row. First "pb" is part of the root, so it is OK!
•  » » » » » » » 4 years ago, # ^ |   0 Oh I misunderstand “twice in a row”:(
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I just misunderstood the statement too... Btw,how to solve the problem if removing the condition "in a row"? Also DP?
•  » » » » » » » » 4 years ago, # ^ |   0 Hm, I don't know actually. Does anybody?
 » 4 years ago, # |   0 Can someone help me in finding out why this gives WA for Div2 D ? Thanks!
 » 4 years ago, # | ← Rev. 4 →   -29 There is one thing I would like to officially complain about. I didn't carefully read the statement of the task A and forgot to print YES before printing the result. I wouldn't mind subtracting points for an incorrect submission, but if the same thing happened to somebody who prints incorrect version of NO, like NO0there will be no punish, because that would be caught by the first test and this is not counted as incorrect submission. This way people who are lucky to get WA on the first test case, will get away with it.Hence I kindly ask to change this rule: either count each incorrect submission or don't count incorrect submissions on all the tests from the task statement. Otherwise the order of tests influences your final score, and that factor shouldn't be taken into account at all.
 » 4 years ago, # | ← Rev. 4 →   0 In my solution (Problem D), my code is giving runtime error, but, when I comment line 121 (resp[0]=a) not gives? someone understand why it happen?runtimenot runtime
 » 4 years ago, # |   +20 Editorial??
•  » » 4 years ago, # ^ |   -20 Btw, will the round be rated?
•  » » » 4 years ago, # ^ |   0 Yes. Ratings have already been updated.
•  » » » » 4 years ago, # ^ |   -12 I see. Hope for lots of math.
 » 4 years ago, # | ← Rev. 2 →   0 What is the answer for this case in Div.2B?41 2 3 4
•  » » 4 years ago, # ^ |   0 3
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Shouldn't it be 1? If we take 1 + 4 as a side and 2 + 3 as the other side, we have two sides of length 5. Then we only need a size of length 1 to build a triangle.
•  » » » » 4 years ago, # ^ |   0 It's invalid! We can make convex polygon using sides 1, 2, 3 and 4 because 1 + 2 + 3 > 4.
•  » » » » » 4 years ago, # ^ |   0 You're right. Thanks!
 » 4 years ago, # |   0 div2, problem c, "The only restriction — it is not allowed to append the same string twice in a row", is this saying that the same string can not appear again immediately after it appeared? or it is saying that when a string "ab" has been appended, even if "def" is appended, the string "ab" can never be appended again? by reading the description my understanding is the latter one, however reading others' submission it looks it's referring to the previous case?
 » 4 years ago, # |   +11 Why is there still no editorial in English? Is an English editorial going to be published at all? BTW, I think you should organize more rounds, the problems from this round that I managed to solve during and after the contest are awesome! :)
 » 4 years ago, # |   0 Hahaha.. ..... This blog has been written so well.. Waiting for next...
 » 4 years ago, # |   0 can anyone help me? I dont understand why im getting a runtime error for C? click I am using recursion to make parts of the string and see if matching with parent or not and then memoising the index where i start to reduce some time