### Endagorion's blog

By Endagorion, 6 years ago, translation,

Hi all.

On Sunday, September 7, at 19:30 MSK regular, 265-th, Codeforces round will take place. Problems are prepared by me, Mikhail Tikhomirov. Round will be for both divisions.

Standard (not dynamic) scoring will be used for this round.

Div. 1: 500-1500-1500-2000-2500

Div. 2: 500-1000-1500-2500-2500

I would like to thank Gerald Agapov (Gerald) for his help in problems preparation, Filipp Rukhovich (DPR-pavlin) and Alexander Mashrabov (map) for round testing, Maria Belova (Delinur) for English statements and Mikhail Mirzayanov (MikeMirzayanov) for creation and development of Codeforces project.

This is going to be my third round on Codeforces, and I tried to make problems as interesting and diverse as possible. Hope you will enjoy this round. Best of luck! =)

UPD: round is over. Thanks for participating, hope you liked the problems.

Grats to all the winners:

Div. 1:

Special respect goes to simonlindholm, the only participant to solve the hardest problem E!

Div. 2:

Editorial is here.

• +604

 » 6 years ago, # |   +63 Your next contest after Three years....!
 » 6 years ago, # |   -23 I wish to see more Math.:)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 I think you'll get what you want.
•  » » » 6 years ago, # ^ |   -37 :)
•  » » » » 6 years ago, # ^ |   -39 I hope for no math.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +7 Why both hope for math and not math problems got negative votes?
•  » » » » » » 6 years ago, # ^ |   +2 Because it's spammed on each contest announcement?
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Then explain positive votes in this comment Edit: it's no longer up-voted (but it was +13)
•  » » » » » » » » 6 years ago, # ^ |   +2 Oh, I hadn't downvoted that one. Fixed.
•  » » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   -17 I meant if it's really spam why people in codeforces up voted that comment ? Edit: it's no longer up-voted (but it was +13)
•  » » » » » » » » » 6 years ago, # ^ |   +2 Dunno, I provided a reason for why downvote (there are dozens of short comments like "I hope there'll X" and "GL&HF" and "thanks for X", and I stopped being interested in reading them after the first 100), not why upvote :DCF voting is really strange, I have no idea why it behaves the way it does. Sometimes I'm thinking the answer could be 42.
•  » » » » » » » » » 6 years ago, # ^ |   -15 @Xellos I will keep that in mind from next contest.:)
•  » » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Hey man, I just keep repeating that because this site is not named "mathforces", and others keep making "Hope for math!" comments. (!!)
•  » » » » » » » » » 6 years ago, # ^ |   +21 Oh yeah, I forgot that the optimal method to reduce the "Hope for math" spam is to add "Hope for no math" spam.
•  » » » » » » » » » 6 years ago, # ^ |   -26 While speaking about math, have you noticed that the absolute value of your contribution is a perfect cube? Also the absolute value of mine is a 4th power added to 1 :o. It is a very interesting topic :o.
•  » » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Here , I have made the absolute value of your contribution a 4th power added to 3 now :D
•  » » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   -9 Actually, it is the absolute value of a 4th power added to 3 :D. Also your contribution is a fourth power :o.
•  » » 6 years ago, # ^ |   -30 why? I think Math is difficult
•  » » » 6 years ago, # ^ |   -34 Why? I think math is easier than other!
•  » » » 6 years ago, # ^ |   -12 I love Math.:D
•  » » 6 years ago, # ^ |   -27 Math is beatiful guys and haters shut up xd. If it weren't for math, there won't be competitive programming xd.
 » 6 years ago, # |   -19 I hope I can do better！
 » 6 years ago, # |   -11 I m going 2 rise
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 The green knight rises (poke batman).
 » 6 years ago, # | ← Rev. 2 →   +23 I think this announcement sets the record for the shortest announcement for a contest ever. Keep It Short and Simple! :)
•  » » 6 years ago, # ^ |   +18 Keep it simple, stupid! (the KISS principle!)
•  » » 6 years ago, # ^ |   +11 I like this simple style,Keep it short so that people don't miss part of important message.
•  » » 6 years ago, # ^ |   +7 Good way to get more upvotes :D
 » 6 years ago, # |   -10 Wish to learn new concepts ,new tricks and new things :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   -8 ...
 » 6 years ago, # | ← Rev. 2 →   -11 Why is everyone in a hurry?! Contest's blog 5 days before contest?! Once they posted it a few hours before the contest :D Oh, and no thanks to Gerald or anybody else?! What an unusual contest blog...
•  » » 6 years ago, # ^ |   -16 But higher topic rating than last contest :D
•  » » 6 years ago, # ^ |   -10 Perhaps this round have something unusual :)
 » 6 years ago, # |   -30 It is my first time to compete, I hope i can solve at least once.
•  » » 6 years ago, # ^ |   -44 Welcome. I hope you can solve all.
 » 6 years ago, # |   -40 Good luck and have fun! scores up, up and up!
 » 6 years ago, # |   -10 How to register for the contest ? I can't find any link for registration
•  » » 6 years ago, # ^ | ← Rev. 2 →   +16 You will be able to register a few hours before the contest.
 » 6 years ago, # |   0 Long Waiting For this contest Good luck everyone
 » 6 years ago, # | ← Rev. 2 →   0 Best of luck everyone...! :)
 » 6 years ago, # |   0 cheer up!
 » 6 years ago, # |   0 First time above 1700 and I have a question regarding divisions. My friends take part in Div2 but I can't Register to Div2 due to 1700+ rating.Will I be able to join as virtual something when Div2 starts without ranking or I must register in Div1?
•  » » 6 years ago, # ^ |   +3 You can enter virtual Div2 only after the contest is finishednow you can only enter div1
•  » » » 6 years ago, # ^ |   0 that's bad but thanks.
 » 6 years ago, # | ← Rev. 2 →   -7 What type of scoring will be use ? Good Luck to everyone
•  » » 6 years ago, # ^ |   0 why do u combine Unable to parse markup [type=CF_TEX] with normal text?
•  » » » 6 years ago, # ^ |   -9 I don't know ? 'Cause are different topics ? My question and my wishes ?
 » 6 years ago, # |   0 how to solve Div-1 B?
•  » » 6 years ago, # ^ |   0 Bruteforce, I think. There are 6 permutations for each of 7 point (you can fix the first), so it is 6^7 ~ 300k — fast enough.
•  » » » 6 years ago, # ^ |   +17 Or generate all variants for 3 points, build all cube and check points.
•  » » » » 6 years ago, # ^ |   0 How check? Length test&?
•  » » » » 6 years ago, # ^ |   0 How check? Length test?
•  » » » 6 years ago, # ^ |   0 And how do you check if it's a cube?
•  » » » » 6 years ago, # ^ |   0 I had an idea to calculate all pairwise distances for some fixed permutation (there are 28 segments in total) and sort them. Now, if first 12 of them are equal, next 12 are equal and last 4 are equal, it's a cube. But I didn't have time to code this solution and can't prove it
•  » » » » » 6 years ago, # ^ |   0 i'm convinced this idea is correct, but i dont know why my solution 7712723 gives TLE!
•  » » » » » » 6 years ago, # ^ |   -88 Because that's incorrect idea and obviously your solution is wrong. Also, your code-style is very dirty. Learn Math and don't ask stupid questions anymore.
•  » » » » » » » 6 years ago, # ^ |   +13 Lol, that's pretty rude. I'd ask you to learn some good manners first.
•  » » » » » » » » 6 years ago, # ^ |   -44 Oh, I so ashamed...Один стою в белом пальто красивый.
•  » » » » » » 6 years ago, # ^ |   0 Map is not so fast thing:) Try to rewrite it without map, it should pass — my solution is basically same, but with vector&sort (7708825), and it works in 0.7 seconds.
•  » » » 6 years ago, # ^ |   0 my solution 7712723 with the same idea TLEd! :(
•  » » » 6 years ago, # ^ |   0 Could you please explain how we can fix one point if all of them probably were shuffled?
 » 6 years ago, # |   +3 It would be great if you could write problem A shorter! At the first, I was confused.Thanks!
 » 6 years ago, # |   0 How to Solve Div -2 C ?
•  » » 6 years ago, # ^ |   0 they key observation is that if we don't have any palindromes of length 2 and 3, then we will have no palindromes at all (other than single characters, ofcourse).
•  » » » 6 years ago, # ^ |   -6 How did you arrive at this conclusion? Have you solved a similar problem before or was it intuition or did you think of this during the contest?
•  » » » » 6 years ago, # ^ |   +1 intuition. any palindrome of length n > 2 has a sub-palindrome of length n - 2 as its substring (u can get this by removing the first and last characters).
•  » » » » 6 years ago, # ^ |   0 easy to note that we can build palindrome by add same character to begin and end of another palindrome. just consider the case of odd and even length, so we could just check every 2 and 3 consecutive letters
•  » » » 6 years ago, # ^ |   0 I made this observation during the contest but do you still have to loop over all possible strings after the input?
•  » » » 6 years ago, # ^ |   0 Can u explain ur solution !
•  » » 6 years ago, # ^ |   +4 Suppose you have a palindrome of length at least 4. Delete the start and end characters. Now you still have a palindrome. Thus you only need to consider palindromes of length 2 or 3. Find the rightmost character that you can increment to something satisfying s[i]!=s[i-2] && s[i]!=s[i-1] (within the bound of p of course), then fill the remaining letters with the "smallest" letter possible.
•  » » » 6 years ago, # ^ |   0 Damn, I gave up thinking on that because it seemed complicated to check if replacing a character would cause any of the previous strings to become a palindrome.
 » 6 years ago, # |   +8 I got my first hack on codeforces! I tried a little different strategy this round. I solved B and A quickly and then tried to solve C within the first hour. But I couldn't. Nevertheless, I spent the whole of the second hour trying to hack but was not very lucky until the last 10 minutes. About 7 minutes before the end of the contest I managed to hack a solution!
 » 6 years ago, # | ← Rev. 2 →   +12 Nice problems!How to solve D? I was struggling for quite a while, but didn't come up with anything faster than 100 FFTs (or 2 FFTs, but for vector with size 107) :(
•  » » 6 years ago, # ^ |   +26 My solution relied on the fact that we only need 1e-9 precision. Basically, with probability 1-eps we never get to very high levels.
 » 6 years ago, # |   0 I managed to find a suitable algorithm for 464C - Substitutes in Number, yet couldn't solve it because I couldn't read the input properly. I don't know yet what was causing the quite straightforward input code to fail... Here's my last failing submission : 7713194 If I add assert (c >= 0 && c <= 9); after line 43, the assertion fails...
 » 6 years ago, # |   +5 This was a great contest :) Thank you for writing! I liked many of the Div 2 problems.
 » 6 years ago, # |   0 I have a feeling that a lot of A-Div1's will fail.
 » 6 years ago, # |   0 I see some hacks on div1-C, for example Merlininice has quite a few. How can a solution to div1-C be incorrect? It looks really straightforward.
•  » » 6 years ago, # ^ |   +18 Are you now scared that yours too is incorrect?! :D
•  » » 6 years ago, # ^ |   +1 Some people did not take the length by module, some took it by module 109 + 7 instead of 109 + 6.
•  » » » 6 years ago, # ^ |   0 But why does one need the length at all?..I guess you're saying that people were computing "length of expansion of digit X" instead of "10 to the power of length of expansion of digit X"?
•  » » » » 6 years ago, # ^ |   0 Exactly.
•  » » » » 6 years ago, # ^ |   0 My solution got hacked also. It was totally a straightforward dp problem. I just couldn't figure out why it was giving incorrect ans. I thought keeping the length and exponent value would do the same thing but totally forgot that if I kept the length, I would have to do modulo 10^9+6 on the length according to FLT. If only I'd kept the exponent value instead :(
•  » » » 6 years ago, # ^ |   0 10^9+7 instead of 10^9+6 ???? problem statement say 10^9+7
•  » » » » 6 years ago, # ^ |   +13 If we store just length, we're computing 10^len at some point. Using FLT, we can just compute 10^(len mod (10^9+6)) instead, so we can just take len mod 10^9+6 instead.
•  » » » » 6 years ago, # ^ |   +12 One should use 109 + 6 in order to keep length. Because it is the period of pows (check little Fermat's theorem)
•  » » » » » 6 years ago, # ^ |   +8 New information for me, thanks :)
•  » » » 6 years ago, # ^ |   0 some took it by module 109 + 7 instead of 10^9 + 6. do you mean that if I saved the length instead of power of 10 and make it modulo 10^9+6 I will get AC?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +8 (applies only if and are coprime)
•  » » 6 years ago, # ^ |   -8 Hey Petr, didn't you make a similar mistake (taking different value for MOD) in a past contest? I remember reading about it on your blog!
•  » » » 6 years ago, # ^ |   +7 If I remember correctly he made a missprint (10^9+9 instead of 10^9+7 or sth similar), not a conceptual mistake like the one mentioned above.
•  » » 6 years ago, # ^ |   0 so do ztxz16 and Kostroma.
 » 6 years ago, # |   0 C , D div2 anyone ?
 » 6 years ago, # | ← Rev. 2 →   0 I had this algorithm (which I did not implement) for solving 465C - No to Palindromes!. Is this a good approach? Treat string as a number in base p. Let left = 0 repeated n times Let right = p repeated n times while(left < right) { int mid = (left + right) / 2; if(check(mid)) right = mid; else mid = left + 1; } The function check(x) tells you if x contains no digit > p and that it contains no palindromic substring of length > 1 (both of which can be done in linear time).
•  » » 6 years ago, # ^ |   +11 Your function check is not monotonic, so binary search won't help you here.
•  » » » 6 years ago, # ^ |   0 How did you solve it?
 » 6 years ago, # |   0 Not the contest that I expected and hoped... BTW, Palindromes are AWESOME! Why should somebody be bad with them?!
 » 6 years ago, # |   +22 Here's a Brainfuck solution to problem A (reads and outputs as ASCII). The cells are divided into groups of two. The first cell of the group is 1 if the index is in range 0 to n and 0 otherwise. The second one contains input for that index — either 1 or 0.The code: >>,- read n [[->>+<<]+>>-]+ prepare cells of the second type [<<] go to start >>[>,>] read input <<[<<]>>> go to first value cell [ <<[->>+<<]>> add values from last index >> go to next cell ] <[-<+>]< if the index cell is 1 add to the result . output result
 » 6 years ago, # | ← Rev. 2 →   +4 Weren't E div2 — C div 1 pretests very very weak?I see naive implementation solutions pass pretests!
•  » » 6 years ago, # ^ |   -17 Wow, really???
•  » » » 6 years ago, # ^ |   0 Yes, See those for example 7713065 7710477 7710991
 » 6 years ago, # | ← Rev. 2 →   0 I tried to hack this solutionby this case2 0 0but it gives me Unsuccessful hacking attemptwith this case variable pb will be used without initializationhow this solution pass my case ?
•  » » 6 years ago, # ^ |   0 pb will have junk value, but that would not contribute to answer, just that "break" will not be called.
 » 6 years ago, # |   0 How to solve div-2 D ?? I first tried to take all 6 combinations from 24 , that is 24C6 , clearly it isn't suitable !!!
 » 6 years ago, # | ← Rev. 2 →   +5 When A,B are too easy and others are hard (div2), this will happen: I can see about 1500 rank difference between 2 users while both of them have solved 2 problems. The rank of the participants which solved 2 problems, starts from 400 and ends after 2000. This is a huge difference! I think this shouldn't happen.Thanks :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 In this contest, if you can solve only A, B which is common with Specialists and low Experts, your score will depend on your time, which isn't kinda bad. If you succeeded in solving C, or even D, E, those tasks will tremendously increase your rating because they are simply made for coders who has ideas and knowledge.
 » 6 years ago, # |   +20 I misunderstood Div1-C problem statement :-( But problems are very interesting. Thank you for preparing this round :-)
 » 6 years ago, # |   0 For Div2, a and b was easy and c d e was hard. I have solved A and B but I got rank 1100... To many contestants solved just 2 problems and very big difference in same, two problem solvers.
 » 6 years ago, # |   0 Who else forgot to check if the cube side length is greater than 0? High five!! :'(
•  » » 6 years ago, # ^ |   +1 High five! :)
 » 6 years ago, # |   0 I got wrong for DIV 2 D , because I used float instead of integer while printing the cordinates , my programs prints the cordinates in exponent form in one of the test case and is judged wrong.Did someone else also failed system test in this way before ? Link : 7710844
 » 6 years ago, # |   +37 Why ratings update is delayed too much in codeforces after system test is finished? (while it's fast in topcoder)
•  » » 6 years ago, # ^ |   +11 the relation between system tests and rating update is inverse. i don't know why .
•  » » 6 years ago, # ^ |   +3 My guesses:System tests are delayed — because they need to add the newly added hacks to the final tests.Rating updates are delayed — because they are figuring out the cheaters in the contest.
 » 6 years ago, # |   +1 Good question, thanks ^_^ waiting for editorials...
 » 6 years ago, # |   0 "Editorial will be up in an hour or two." is a Infinite Loop statement.
 » 6 years ago, # |   +2 Can someone give some hints for Div1 C?
 » 6 years ago, # | ← Rev. 2 →   -12 div2 probC int n, p; cin >> n >> p; char *data = new char[n]; cin >> data; runtime error. changed to int n, p; cin >> n >> p; char *data = new char[1010]; cin >> data; accepted. life sucks :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   -11 1). new char[n] is not supported by standart, it's only gcc feature.2). You need n+1 chars because of extra '\0' character at the end.
•  » » » 6 years ago, # ^ |   +29 1) LOLWUT?
•  » » » » 6 years ago, # ^ |   +13 1). Sorry, confused it with char data[n];
•  » » 6 years ago, # ^ |   +4 if you can use cin, why don't you use string?
 » 6 years ago, # |   0 Looks like tests in Div1-B are weak — I mean overflow. I have just written an int64 solution, which use values like maxCoord^4 (euclid length of vector product). And it's full solution. Is it difficult to create test to crash this solution?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +10 I think technically you have calculated a hash of the vector's length (have calced it modulo 264) and then you are only interested if two hashed values equal or not, so it seems OK.
 » 6 years ago, # |   +26 These submissions are very much alike, aren't they? This 7704944 and that 7706248 And this 7713468 and that 7713301 too!I'm a policeman:)
 » 6 years ago, # |   0 Oh my rating :))
 » 6 years ago, # |   0 very happy to get 284 point
 » 6 years ago, # |   0 can somebody explain div-1 C it is not so clear from editorial
•  » » 6 years ago, # ^ | ← Rev. 2 →   +11 Didn't read editorial, but may be can helpFirst of all, we can notice that after all transformation behind every digit will stay some sequence. Suppose we know these sequences for every digit [0..9], and for digit d sequence has length len[d] and value val[d]. Now, to compute result for input s, go though s and result = result * (10 ^ len[s[i] — '0']) + val[s[i] — '0'].Now we need to compute len[] and val[]. Let's use DP technique. Consider len[] and val[] calculated for some suffix of transformations queries [k..m-1]. How compute them for suffix [k-1..m-1]? Use similar ideas were used to compute result. Take query d->t, go through t and value = value * (10 ^ len[t[i] — '0']) + val[t[i] — '0']; length += len[t[i] — '0'];val[d] = value; len[d] = length;All these formulas come from Horner's method.
 » 6 years ago, # |   +7 Country wise standings are updated. Sorry for the delay.
 » 6 years ago, # |   +14