albertg's blog

By albertg, 3 years ago, translation, ,

Hi Codeforces community! I am glad to announce that at 27 November 16:35 (GMT time) will take place Codeforces Round #382 for participants of both divisions.

Author of this round is me (albertg). I am from Armenia and the only Armenian author of any Codeforces round yet. (Sorry Edvard). This round is my second round and I hope this is not the last one! :) it is the last one. As usual, I'm thankful to the coordinator of Codeforces Gleb Evstropov (GlebsHP) for helping to prepare this round and Mike Mirzayanov (MikeMirzayanov) for wonderful platforms Codeforces and Polygon. Also special thanks to Super_azbuka for an idea of a problem.

As usual, contestants will have 5 problems and 2 hours to solve the problems. In this round you should help Ostap Ibrahim Bender to reach Rio-de-Janeiro. Good luck and have fun!

UPD1: Scoring: div1 750-750-1500-2000-2500, div2 500-1000-1750-1750-2500.

UPD2: Editorial is posted.

UPD3: If somebody has question(s) about solutions of problems, please write me a personal message.

UPD5: Editorial of problem div2E/div1C is posted.

• +111

 » 3 years ago, # | ← Rev. 2 →   -95 Clashing with another contest One of them (HR preferably), please reschedule, so we can participate in both.
•  » » 3 years ago, # ^ |   +97 If you want HR to reschedule why are you posting it here?
 » 3 years ago, # |   +14 Who is Ostap Ibrahim Bender ?
•  » » 3 years ago, # ^ |   +122 He is a famous rapper from Odessa.
 » 3 years ago, # | ← Rev. 2 →   0 normal time again
 » 3 years ago, # |   -171 Is it rated?
•  » » 3 years ago, # ^ |   -13 yes.
•  » » 3 years ago, # ^ | ← Rev. 3 →   -62 .
 » 3 years ago, # |   -26 Its fu*king rated..! Dont ask is it rated or not !
•  » » 3 years ago, # ^ |   -32 see this
 » 3 years ago, # |   +2 5 problems round again! Wish it to be an interesting round~: )
 » 3 years ago, # |   +16 Hey, I'm new to codeforces. Can you please explain me what is Division 1 and division 2? Thanks.
•  » » 3 years ago, # ^ |   +16
•  » » » 3 years ago, # ^ |   0 Thanks! Just one more query. Do we have to register separately for the contests (for instance, this one) or if we are on codeforces, we can directly give them? If we have to register separately, how to do so? Thanks again.
•  » » » » 3 years ago, # ^ |   -11 Yes, you have. Registration opens about 24 hours prior the contest.
•  » » 3 years ago, # ^ |   +7 waiting to see your performance in your first round good luck
•  » » » 3 years ago, # ^ |   +4 Thank you :)
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +10 I'm just a rookie. I hope to improve my coding on codeforces.
 » 3 years ago, # |   +10 Again....5 problems!!!
 » 3 years ago, # |   -9 18:35
 » 3 years ago, # |   0 Perfect time for me
 » 3 years ago, # |   +24 Codeforces always helped me to improve my thinking capability , thank you codeforces :)
 » 3 years ago, # | ← Rev. 2 →   -44
 » 3 years ago, # |   -149 The comment is hidden because of too negative feedback, click here to view it
•  » » 3 years ago, # ^ |   +127 Lol, let's make it real!)
 » 3 years ago, # |   +21 Petr has register for DIV 1. He must be aiming to get his second spot. Wish it to be exciting round!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +23 TooDifficuIt has registered too. He will try to prevent this.
•  » » 3 years ago, # ^ |   +68 Actually he can get his second spot without participating :D
•  » » » 3 years ago, # ^ |   +29 Tourist used that trick before, remember?
•  » » » 3 years ago, # ^ |   -25 Is it all? Just a comment? Aren't you gonna write a blog?
•  » » » 3 years ago, # ^ |   -13 Actually you also got second spot without participating :D Seems like its too difficult to get positive rating change when you are among top rated contestants.
 » 3 years ago, # | ← Rev. 2 →   -20 how can i help Ostap Ibrahim Bender to reach Rio-de-Janeiro?
 » 3 years ago, # |   +52 I hope I can help Ostap Ibrahim Bender to not reach Rio de Janeiro.Life is not the best right now here :P
•  » » 3 years ago, # ^ |   +8 You don't have to help, by the way, but I warn you, we have a long reach
 » 3 years ago, # | ← Rev. 3 →   +58 Ostap Bender is a fictional con man who appeared in the novels The Twelve Chairs and The Little Golden Calf written by Soviet authors Ilya Ilf and Yevgeni Petrov.
 » 3 years ago, # |   +12 So we should expect graph theory problems in this contest.
 » 3 years ago, # |   +2 After a long time :D Back to home , codeforces ! The love! <3
 » 3 years ago, # |   -73 Is it rated ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   -22 Man, why? ;D
•  » » » 3 years ago, # ^ | ← Rev. 4 →   -28 Nope)But it's rlly rated .
•  » » 3 years ago, # ^ |   0 Yes, it is rated !!!
•  » » » 3 years ago, # ^ |   -13 Ohhh....TY man!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Question of the day)
 » 3 years ago, # | ← Rev. 2 →   -47 Hello. This is my first contest. Wish me good luck. Also every Punjabi add me. Jai babe di
•  » » 3 years ago, # ^ |   +4 Good Luck!
•  » » » 3 years ago, # ^ |   -16 Thank you for your wishes.I was solved with 4 problems . I do coding and get a job and a girl friend and a happy life with some naughty time . Also I am trying to get girlfriends on CodeForces.Add me.
»
3 years ago, # |
0

Stay strong guys! Good luck and happy coding.

NeverSayNever

 » 3 years ago, # |   +17 Score Distribution?? Not declared yet, 17 minutes left
•  » » 3 years ago, # ^ |   +11 "scoring will be posted just before the contest" might mean 30 seconds before the contest :)
•  » » » 3 years ago, # ^ |   0 30 secs left, still nothing)
 » 3 years ago, # |   +8 Where is scoring?
 » 3 years ago, # | ← Rev. 2 →   0 This scoring will be posted just before the contest! So the contest is gonna be delayed again?
 » 3 years ago, # |   +214 At least I don't have to worry about system test (and can sleep early)
 » 3 years ago, # |   +36 A=B=C=D
 » 3 years ago, # |   +23 That sad moment when you're certain of your solution but it won't pass and you can't find where is the errorrip rating :/
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 Same as you, WA test 5 C and WA test 6 DRIP rating :(Plese someone tell me what where those tests so I can go cry myself to sleep
•  » » » 3 years ago, # ^ |   +1 WA 5 C, hacked D ;_;
•  » » » 3 years ago, # ^ |   0 on D instead of searching for highest prime I searched for any prime P with n - P <  = 500 and it passed test 6, the pure greedy solution isnt correct it seems
•  » » » » 3 years ago, # ^ |   +14 Check out Goldbach Conjecture
•  » » » » 3 years ago, # ^ |   0 I repeat this 1000 times: while (n > 0) { x = calc(n) // calc(n) = the biggest prime number which is <= n; repeat x = calc(x — 1) 0 -> 3 times if n — x = 1 then x = calc(x — 1); res++; }
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +8 No need of searching.If prime, print 1.else if even, print 2else if n-2 is prime, print 2else print 3
•  » » » » » 3 years ago, # ^ |   0 You know, before the contest I knew nothing about Goldbach Conjecture and never used logN prime test. I learnt all of this just during the contest and implemented this: if prime ans = 1, if even ans = 2, if odd ans = 3. But why if n-2 is prime then ans = 2? I understand that this is true, but why namely n-2? Why not n-4? Maybe I just dont know math good enough :(
•  » » » » » » 3 years ago, # ^ |   0 Because 2 is the only even prime number.
•  » » » » » » » 3 years ago, # ^ |   0 Yeah, thanks. I should have thought about that...
•  » » » » » » 3 years ago, # ^ |   +6 because 4 is not prime. You check for n-2 because 2 is also prime, and then that odd number would be written as a sum of 2 primes. if you checked for n-4, then you would decompose the number in one prime plus 4, which would give 3 instead. The only case that an odd number is a sum of two primes, is when one of them is 2.
•  » » » » » » » 3 years ago, # ^ |   0 Sorry, n-4 is my mistake. Then why not n-3? I see that 2 is somehow more unique in this case, but why namely 2? Is there a theorem or you just logically deduced this?
•  » » » » » » » » 3 years ago, # ^ |   -29 man, seriously!! are you even thinking? (no offence) this is too trivial.
•  » » » » » » » » » 3 years ago, # ^ |   +21 The comment below explained it good and I really couldnt understand it. What is trivial for you may not always be trivial for every one. P.S. If you say "no offence" it is still an offence.
•  » » » » » » » » 3 years ago, # ^ |   +5 If an odd number can be split in 2 primes, one of them must be a 2, because in order for 2 numbers to add an odd number, one must be odd and the other one must be even. Then, the only posible split is 2 and n-2, if n-2 is prime.
•  » » » » » » » » » 3 years ago, # ^ |   0 Damn, how could I not get it before. :( Thanks, man!
•  » » » » » » » » 3 years ago, # ^ |   0 Because 2 is the only even prime.
•  » » 3 years ago, # ^ |   +1 Are you talking about D? Cause I'm pretty sure mine is right too lol (unless I just entirely misunderstood the problem).
•  » » » 3 years ago, # ^ |   0 yeah, just found out it gives WA for 2e9 as input :/ fml
•  » » » » 3 years ago, # ^ |   +1 Lol that was my wrong answer too. Guess I should've googled a bit harder to find out about the Goldbach Conjecture.
•  » » » » » 3 years ago, # ^ |   0 Lol exactly same happens for me
•  » » 3 years ago, # ^ |   +3 rank dropped from 11 to 600 , just because of a stupid blunder :/
•  » » » 3 years ago, # ^ |   0 Overflow?
•  » » » » 3 years ago, # ^ |   0 corner case in D . Dont know why i locked D so early :(
•  » » » » » 3 years ago, # ^ |   0 same with me
•  » » 3 years ago, # ^ |   0 same here D- WA on 6 C- WA on 5
 » 3 years ago, # |   +14 How to solve Div1 C and D?
•  » » 3 years ago, # ^ |   +43 Div 1 C:DP(u, dist, nearest_one) is number of ways to color: subtree rooted at u. Amongst the vertices that does not satisfy condition "at least one black vertex v at distance no more than k", the maximum distance to u is dist The black vertex nearest to u has distance nearest_one.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Edit: I am mistaken :P
 » 3 years ago, # |   +9 How to solve Div2 C? Every time I see a problem about any kind of paired tournament I become sad.
•  » » 3 years ago, # ^ |   +10 It should be a Fibonacci Sequence...
•  » » 3 years ago, # ^ |   +111 Contest quality is going down nowadays :/
•  » » » 3 years ago, # ^ |   +19 Wow, it even has tennis statement as well. I wonder how many people googled this.
•  » » » » 3 years ago, # ^ |   +18 Yes they didnt even bother to change the statement :P
•  » » » 3 years ago, # ^ |   +53 and author of this problem is albertg and it is posted in 2014?
•  » » » 3 years ago, # ^ |   +3 Well , even though this problem was googleable. I reduced this problem to taking out the maximum possible height of an AVL tree for given number of nodes.Then you can solve it using Cheating
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Fibonacci Number relation.Analyze that minimum number of players required for x number of games at top:1 — 2 players2 — 3 players3 — 5 players (One having played 2 matches and other 1)4 — 8 players (One having played 3 matches and other 2)....The answer is maximum index where fib[i] <= n
•  » » 3 years ago, # ^ |   0 Think of it this way. To have a 1-game tournament, you must have 2 players. You can consider 1 player to be a 0-game tournament since there already is a winner. In order to have an n-game tournament, the winner of an n-1 game tournament must play the winner of an n-2 game tournament. This is simply a Fibonacci sequence and can be calculated using dynamic programming. (Extra players beyond the target Fibonacci number cannot make a difference because they cannot reach a high enough game depth to challenge the current champion).
•  » » 3 years ago, # ^ |   +6 Think recursively. Let the winner has to play x games. Then he has to play at-least x-1 games and the other player has to play at-least x-2 games. Now you can see the pattern. It's Fibonacci. Hope it's help.
•  » » » 3 years ago, # ^ |   0 I understand what you are saying but i do not get how does this recurrence relation F(n) = F(n-1) + F(n-2) give optimal answer(maximum possible played matches)...Even if it came on my mind during the contest there is no way i would be able to prove that it works..I used ceil(log2(n)) logic which turned out to be a complete mistake...Cheers
 » 3 years ago, # |   0 Can anyone explain how to Div 2 D? I did it greedily where I took the largest prime less than n where n-x >= 2 and then continued to take the smallest prime under that number until I got to 0.But it seems that way is wrong. Did I miss the correct way entirely?
•  » » 3 years ago, # ^ |   +17 Two words: Goldbach Conjecture
•  » » » 3 years ago, # ^ |   0 Yeah I figured that and that's what I was doing so I guess I just had a bug in implementation.
•  » » » » 3 years ago, # ^ |   0 If even (and not 2) the answer should be 2. If odd, then the answer is 3 unless N-2 is prime, in which case the answer is 2. Of course if prime, answer should be 1.
•  » » » » » 3 years ago, # ^ |   +3 Yeah the one that breaks my code is 2,000,000,000 (it prints 4). Thanks for the help!
•  » » 3 years ago, # ^ |   0 I used Goldbach's conjecture, though my solution was hacked.
•  » » » 3 years ago, # ^ |   0 Did you take care of case where n-2 is prime? Because in this case you can split in numbers: 2, n-2 and the answer would be 2. I was "lucky" to get hacked by this case and could correct in time!
•  » » » » 3 years ago, # ^ |   0 No, that is the reason. Unfortunately I was hacked a bit late so I didn't manage to fix the solution in time
•  » » 3 years ago, # ^ |   0 why less than n? If n itself is a prime number then the answer would be just 1. I didnt get the solution but this might be your mistake.
•  » » » 3 years ago, # ^ |   0 I checked for that initially (I should've mentioned that I guess) so I don't think that was it.
•  » » » 3 years ago, # ^ |   0 I included this case too, but still WA
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I used this. I hope this passes system tests.
•  » » 3 years ago, # ^ |   +4 Hint: Every number can be written as sum of 3 or less primes. So check if it is possible to write as 1 or 2 primes, if not it must be 3.
•  » » » 3 years ago, # ^ |   +1 So that's what it was. When I input 2,000,000,000 I got 4 but I couldn't find a set of primes that made it sum in 3. Could I ask how you came up with that? Did you already know that you could express the numbers that way or did you just think about it?
•  » » » » 3 years ago, # ^ |   +23 That is not true, 2000000000 can be written as a sum of 2 prime numbers. Following is a list (all of them are primes): 8388739 + 1991611261 = 2000000000 37749343 + 1962250657 = 2000000000 33554977 + 1966445023 = 2000000000 4194403 + 1995805597 = 2000000000 41943721 + 1958056279 = 2000000000 73 + 1999999927 = 2000000000 8388811 + 1991611189 = 2000000000 20971789 + 1979028211 = 2000000000 29360533 + 1970639467 = 2000000000 20971807 + 1979028193 = 2000000000 12583099 + 1987416901 = 2000000000 127 + 1999999873 = 2000000000 29360449 + 1970639551 = 2000000000 139 + 1999999861 = 2000000000 4194511 + 1995805489 = 2000000000 4194439 + 1995805561 = 2000000000 223 + 1999999777 = 2000000000 37749421 + 1962250579 = 2000000000 16777711 + 1983222289 = 2000000000 20971957 + 1979028043 = 2000000000 4194637 + 1995805363 = 2000000000 33555217 + 1966444783 = 2000000000 12583297 + 1987416703 = 2000000000 29360257 + 1970639743 = 2000000000 8389063 + 1991610937 = 2000000000 25166023 + 1974833977 = 2000000000 4194583 + 1995805417 = 2000000000 8389111 + 1991610889 = 2000000000 379 + 1999999621 = 2000000000 12583237 + 1987416763 = 2000000000 25165843 + 1974834157 = 2000000000 20971651 + 1979028349 = 2000000000 41943883 + 1958056117 = 2000000000 12583183 + 1987416817 = 2000000000 25165909 + 1974834091 = 2000000000 16777441 + 1983222559 = 2000000000 41943919 + 1958056081 = 2000000000 4194739 + 1995805261 = 2000000000 8389261 + 1991610739 = 2000000000 577 + 1999999423 = 2000000000 33554503 + 1966445497 = 2000000000 12583561 + 1987416439 = 2000000000 20972311 + 1979027689 = 2000000000 16778077 + 1983221923 = 2000000000 29361067 + 1970638933 = 2000000000 4194871 + 1995805129 = 2000000000 37748791 + 1962251209 = 2000000000 12583609 + 1987416391 = 2000000000 33554593 + 1966445407 = 2000000000 20972437 + 1979027563 = 2000000000 20972449 + 1979027551 = 2000000000 20972473 + 1979027527 = 2000000000 25166719 + 1974833281 = 2000000000 16777729 + 1983222271 = 2000000000 41943439 + 1958056561 = 2000000000 4194217 + 1995805783 = 2000000000 8388571 + 1991611429 = 2000000000 
•  » » 3 years ago, # ^ |   +1 My solution (apparently correct) was based on Goldbach's conjecture. The answer was always going to be 1, 2 or 3.
•  » » » 3 years ago, # ^ |   0 Yeah that turned out to be what was wrong (my code prints 4 for some numbers).
•  » » 3 years ago, # ^ |   +1 Yeah it's wrong. There is Goldbach's conjecture which says that every even integer can be expressed as the sum of 2 primes and every odd integer can be expressed as the sum of 3 primes. But in some cases we can use less primes, take it as an simple exercise.
•  » » » 3 years ago, # ^ |   0 Alright good to know. Thanks for the help!
•  » » 3 years ago, # ^ |   +1 If the number is prime, return 1 (all prime numbers obviously have a tax value of 1, and this is key to the following algorithm). Otherwise, if it's even, then the Goldbach conjecture follows (every even number >2 is the sum of two primes) and you can return 2. If that is not the case, then check if n-2 is prime. If so, then the number is the sum of two primes (2 and another prime) and you can return 2. Otherwise, it is the sum of a prime and an even number (which itself is the sum of two primes), and you can return 3.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Could you please explain why to check namely n-2? Upd.: Got it, 2 is the only even prime.
•  » » 3 years ago, # ^ |   0 Greedy is flawed here. I initially thought it can be solved with greedy. Later, found that it fails if n == p+1, when p is a prime, greedy algo will try to split it as {p,1} but in the description it was given each of split elements should be greater than 1.
 » 3 years ago, # |   0 Div2 B hack?
•  » » 3 years ago, # ^ |   0 Int overflows
•  » » » 3 years ago, # ^ |   0 Yeah that's what I thought, Thank you.
 » 3 years ago, # |   0 Any idea of prestest 5 of C ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Suppose, it is "n = 13", answer is 5.
•  » » » 3 years ago, # ^ |   0 Can you please draw tournament tree for n=13 ?
•  » » » » 3 years ago, # ^ |   0 You can get it from comment below about n = 8 by adding subtree of 5 leftmost participants to the right.
•  » » » » » 3 years ago, # ^ |   0 Sorry, that tree for 8 contradicts main rule of tournament. Please provide tree where that rule holds independent of outcome of each game.
•  » » » » » » 3 years ago, # ^ |   +11
•  » » » » » » » 3 years ago, # ^ |   0 Thanks. It turned out that grid is not known before tournament starts.
•  » » 3 years ago, # ^ |   0 I think pretest 5 would have been 8.Answer for 8 is 4 and not 3 as the Maximum number of matches increases when the total number of participants is a Fibonacci number.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Can someone actually draw a tournament grid (tree) for n=8 ?
•  » » » » 3 years ago, # ^ |   +3 1 2 1 3 4 5 1 4 6 7 6 8 1 6 in order of games played.
•  » » » » » 3 years ago, # ^ |   0 If player 8 wins 6 in their match, then in the finals it will be second game for him, but 4th game for player 1. That is contradiction with the main condition of problem statement (difference between played games no more than 1)
•  » » » » 3 years ago, # ^ |   +20 behold the power of MS paint
•  » » » » » 3 years ago, # ^ |   0 Thanks, but this picture contradicts main rule from the problem statement. If player 8 and player 1 go to the final, they will have number of played games differ more than 1.
•  » » » » » » 3 years ago, # ^ |   +3 We are assuming the best case scenario (maximum number of games played), so we can assume that 6 will win in this case.
•  » » » » » » » 3 years ago, # ^ |   +10 Organizers cannot assume that someone will win or lose. By definition of the problem they need to construct a tournament grid to match a rule: "two players can play against each other only if the number of games one of them has already played differs by no more than one from the number of games the other one has already played"
•  » » » » » » » » 3 years ago, # ^ |   0 No, it is not the problem statement. By definition you should find a maximal possible number of games. You don't create a tournament grid, you only should take the best from all possible scenarios of grid+games.
•  » » » » » » » » » 3 years ago, # ^ |   +1 I copied this from problem statement. Problem statement says that main rule should be applied for the grid (independent of games). But grid above is not valid for the main rule. It can produce sequence of games which contradicts that rule.
•  » » » » » » » » » 3 years ago, # ^ |   0 But the grid is not fixed. At that point, it does not exists. And it is not obvious what is grid in that problem.
•  » » » » » » » » 3 years ago, # ^ |   +10 I think the grid is not completely defined at the beginning. This way it makes perfect sense. Anyway, this is not clear at all.
•  » » » » » 3 years ago, # ^ |   +10 I might be wrong, but I think the statement is a little bit unclear. This tournament grid is not valid in general, right? I mean, player 1 can't face player 8 according to the rules.I didn't realize that we could consider this kind of grid. :(
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Why player 1 need to face a player 8? It is a set of games 1 2 / 4 5 / 6 7 / 1 3 / 1 4 / 6 8 / 1 6 / and some other stuff, when games are valid only if all players won all their games before that. In case that drawn on a picture, we have answer 4.
•  » » » » » » » 3 years ago, # ^ |   0 I get the answer, but why not? The statement says the tournament is being organized. Why would someone organize a possibly invalid tournament? You're right, but it could be a little bit more elaborated.
•  » » » » » » » 3 years ago, # ^ |   0 Is tournament grid known before games are starting? Or organizers can just randomly pick players during the tournament. Problem statement is very clear about "tournament grid", so I assume it should be finalized before tournament starts.
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 It must be the second option. They can pick players along the tournament.
•  » » » » » » » » » 3 years ago, # ^ |   +5 Problem statement is very misleading than. It describes the different problem.
•  » » » » » » » » » 3 years ago, # ^ |   0 I think it's ambiguous. The expected interpretation is not invalid, so as ours.
 » 3 years ago, # |   +8 Loved the idea behind problem D div. 2 (B div. 1).
•  » » 3 years ago, # ^ |   +3 what idea? i couldn't find the idea behind it! i thought it was greedy but did n;t accept it.
•  » » » 3 years ago, # ^ |   0 Goldbach conjecture
•  » » » » 3 years ago, # ^ |   +24 Is it an idea? If you are not familiar with the conjecture, it is highly unlikely that you will solve the problem.
•  » » » » » 3 years ago, # ^ |   +15 True. This truthfully was the worst contest that I've participated.
 » 3 years ago, # | ← Rev. 3 →   +21 steps to perform well on codeforces contest , steps 3 & 4 are enough in this contest i think :/ .... UPD : you'll need step 2 also , but you should read all the old problems on spoj ..
 » 3 years ago, # | ← Rev. 11 →   0 I try hacking solution before 5 min of ending contest .why hack is ignored? someone plz answer
 » 3 years ago, # |   0 One hell of a tricky contest!
 » 3 years ago, # |   0 How do you solve C? I was so certain my solution was going to pass but it didn't :( I think many others struggled on it as well.
•  » » 3 years ago, # ^ |   0 Dp[i] = the minimum number of players needed such that the winner can take part in i games
•  » » » 3 years ago, # ^ |   0 Wow I didn't think of it as a DP problem. How would you transition between states?
•  » » » » 3 years ago, # ^ |   0 Fibonacci sequence, where dp[0] = 1 and dp[1] = 2.
 » 3 years ago, # |   0 This was a hacking contest. 1 integer input problems for C,D. "7" and "9" were hack cases for D.
 » 3 years ago, # |   0 I've attempt to hack div2 A using the following test input, on the codes that did not handle negative indices (for example, 22533346): 5 4 TG... However, they output correctly. Is there something I have mistaken?
 » 3 years ago, # | ← Rev. 2 →   +38 At first: Thank you for hacking :D.A few minutes later: Sorry for hacking :(. I don't want to lose my rating (significantly).
•  » » 3 years ago, # ^ |   +3 Hack-ers aren't cruel at all, what is? Seeing a wrong solution and ignore it! :v
 » 3 years ago, # |   0 Solved D for the first time! I hope it will pass system test. :)
 » 3 years ago, # |   0 Dooms Contest :/ GG Rating
 » 3 years ago, # |   +17 I wonder how this guy might be feeling after hacking 5 solutions for D and getting hacked back by one of those users.
•  » » 3 years ago, # ^ |   -48 awful contest!!! especially for problem div2 D , it needs to know Goldbach's conjecture. Is it related to problem solving skill?!???
•  » » » 3 years ago, # ^ |   +19 I do think that Goldbach's conjecture is a kind of common sense instead of solving skill.
•  » » 3 years ago, # ^ |   +1 I don't know about him but bvd is very relieved after getting revenge I think.
 » 3 years ago, # |   +69 I'm sorry to tell, but truth should not be concealed : Awful problems on C and D (they don't deserve their intended points) :(
•  » » 3 years ago, # ^ |   0 Couldn't agree more.
•  » » 3 years ago, # ^ |   +1 I agree. Almost no algorithmic skills were needed to solve these two.
•  » » » 3 years ago, # ^ |   0 Actually contests require problem-solving skill, not only popular algorithms and data structures :D
•  » » 3 years ago, # ^ |   +3 I think C is ok. It's something you can figure out with a piece of paper, D is just about whether you've encountered the conjecture or are googling during the contest.
•  » » 3 years ago, # ^ |   0 What's wrong with C?
 » 3 years ago, # |   +31 I got disappointed with my result in this contest. I am pretty sure I have become better in algorithms as I usually practice in TopCoder. According to the new rating in Codeforces, I got moved to Div2. Then, I decided to participate in this contest to reach div1 here, too. Generally, I have difficulty with these kinds of problems since instead of thinking about algorithms, I am forced to find corner cases. I don't really like these kinds of problems though I have the great respect for the author.
•  » » 3 years ago, # ^ |   +5 Regarding other comments, I found out that the Problem C has been available on SPOJ. I think albertg does not know anything about Self-plagiarism.
 » 3 years ago, # |   0 i used this code for problem C i got WA in pretest 7 any idea ?while(n>1){ if((n%2)==1){ans++;}; ans++; n>>=1; }
•  » » 3 years ago, # ^ |   +3 For Problem C I think it's a fibonacci problem.
•  » » » 3 years ago, # ^ |   0 Could u please explain it ?
•  » » » » 3 years ago, # ^ |   +14 Yes I can.We define f(n) to be the minimum number of players required such that the winner can play n games at most.So the ideal situation(to make the number of players minimum) is that the last game the winner played is with another player who played n — 2 games already(since the winner played n — 1 games at this point).So we have: f(n) = f(n — 1) + f(n — 2)then the final answer is just the maximum number m which satisfied f(m) <= tot_number_of_players.
 » 3 years ago, # |   +13 else A&B(div1) problems were fun.thanks.
•  » » 3 years ago, # ^ |   +17 Yes, both A and B are terrible. I wouldn't recommend them to anyone of any level. Maybe if the author used only one of them it would have been suited for Div.1 A
 » 3 years ago, # |   +20 My friend just told me that he solved C and D (Div.2) by finding other peoples' codes on ideone. This is so unfair -_-
•  » » 3 years ago, # ^ |   +4 If it is matched with some other code that submissions will be skipped :)
•  » » » 3 years ago, # ^ |   +2 If people are smart enough to find codes on ideone, they will definitely modify it as they know about this dirty trick. I was surprised to see the rising submissions for C and D.
•  » » 3 years ago, # ^ |   +8 Report him.
•  » » 3 years ago, # ^ |   +116 Since when did this start happening on codeforces? Same author, Same problem.
•  » » » 3 years ago, # ^ |   +24 How is this even possible ? is the author foolish or something ? How can he repost one of his own problems ? Lol
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +73 the contest should be made unrated . Div1 A was copied and Div 1B was google-able :(
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +19 kingofnumbers was right in his blog for which he faced so much criticism. The author of this round did not even care to change the title of the problem. -_- People cheating from ideone and authors making one problem googleable and one problem exactly same(again googleable). Bye bye albertg. Hope this second round is your last round.
•  » » 3 years ago, # ^ |   -27 this not convincing reason to make unrated this mean that they have to make all previous contests unrated
•  » » » 3 years ago, # ^ |   +15 there he is ^ lol i'm such a shitty friend
•  » » » » 3 years ago, # ^ |   -8 who are you -_- I don't even know you -_-
•  » » » » » 3 years ago, # ^ |   0 Bro, if you want people to believe you, at least don't make any more lies that I can easily prove wrong Come on, you gotta be smarter than this!
•  » » » » » » 3 years ago, # ^ |   0 LOL :v
•  » » » 3 years ago, # ^ |   0 So you want to cheat from ideone and then fight for whether the reason is convincing or not to make the round unrated?
•  » » » » 3 years ago, # ^ |   0 I didn't cheated you can confirm from my status -_-
 » 3 years ago, # |   +5 Did anyone used prime numbers to solve D?
•  » » 3 years ago, # ^ |   0 Yeah (D2 D was the same as D1 B). The key insight is the Goldbach conjecture (any even number >2 is the sum of two primes).
•  » » 3 years ago, # ^ |   0 Yes, the key is Goldbach Conjecture
•  » » 3 years ago, # ^ |   0 Yes, I am
 » 3 years ago, # |   +81 Problem D/B be like:
•  » » 3 years ago, # ^ |   +7 haha thats funny.
 » 3 years ago, # | ← Rev. 9 →   -11 problem D can anybody google it this is unfair
•  » » 3 years ago, # ^ |   +3 Yeah, no problem is fare. Or did you mean fair?
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Such a troll problem,simply not fair..
 » 3 years ago, # |   +11 in problem C:"Don't miss the unusual constraint for k."is just a lie :|
 » 3 years ago, # |   0 Hope I can jump to div1 for the second time.
 » 3 years ago, # |   +44 Div.1 A I wonder how many people could google this http://www.spoj.com/problems/TENNIS1/ during the round.... -_-
 » 3 years ago, # | ← Rev. 3 →   +78 I've actually learned something new from this contest, thanks!1) Google exactly the problem statement because apparently... you might get lucky (same author, same statement)2) After #1 is done... you know what to do next3) If everything fails, try checking other people's code on ideone.com because apparently... well, you got the ideaGo Googleforces!
 » 3 years ago, # |   +14 https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1HELLO FROM 2K15 BOYZ
 » 3 years ago, # |   +22 this contest reminds me of april fools day contest :D :D
•  » » 3 years ago, # ^ |   +33 Actually April fools day contest is more interesting than this contest.
 » 3 years ago, # |   +109 Is it fair to repeat your already existing problems? albertghttp://www.spoj.com/problems/TENNIS1/
•  » » 3 years ago, # ^ |   0 Vah beta :P
•  » » » 3 years ago, # ^ |   0 Can you please translate?
•  » » 3 years ago, # ^ |   +1 mdakeklol
 » 3 years ago, # |   +82 I don't want to sound rude or anything, but this contest was very bad and in my opinion should be unrated, and I'm not saying that just because I participated badly. The main reason is that problem C was on SPOJ — link and was posted there by the author of this contest! Anyone could just google it. Also D was an ugly problem, and the only way to solve it was to either somehow already known about Goldbach's conjecture, which is not all that well-known, to search it on google which shouldn't be a way to solve a problem, or to guess it, which would be just luck.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 For D, If someone is able to deduce that answer will equal to minimum number of primes whose sum is equal to n then google search will take you to Goldbach's conjecture. So I feel it's ok. BTW it was similar to Dima and Lisa which was blocked during contest.
•  » » » 3 years ago, # ^ |   +1 Deducing that was easy for a D level problem, the hard part of the problem was finding the number of primes, so 90% of the problem was solved through google
•  » » » 3 years ago, # ^ |   +3 Are we supposed to be using Google during contests?
•  » » 3 years ago, # ^ |   0 I didn't know about Goldbach's conjecture, so I bruteforced the first few answers and OEISed them. Still bad though
 » 3 years ago, # |   +17 Div 2 D is just the same with #324 div 2 D. (http://codeforces.com/contest/584/problem/D)
•  » » 3 years ago, # ^ |   0 In this round's problem you have to prove that you should only pick primes. Minor difference, but at least something
 » 3 years ago, # |   -21 While it's true that the author may have used one of his own problems and this was a mistake, it's important not to consider the entire contest as bad just because one or two tasks were not optimal. It takes a lot of time to prepare these contests, especially for both divisions, so at the end of the day, we are all in the author's debt, not the other way around.
•  » » 3 years ago, # ^ |   +29 Although I didn't participate but we aren't talking about optimality here. You were an author before and you know it's not an easy task to come with the problems but you also know that it's a huge responsibility, in case it's a dup problem we can excuse him assuming he didn't know it existed but here he was the author and it had been there for 2 years.There was no problem solving in Div2 D also just using a well know theorem.
•  » » 3 years ago, # ^ |   +64 Not really. Authors are paid to create problems for a contest, and if they are reusing one of their older public problems, they are basically cheating.
 » 3 years ago, # |   -52 make it unrated is the most stupid thing CF can do
 » 3 years ago, # | ← Rev. 3 →   +27 I don't participate in one contest and the freaking problem D can be done with the Goldbach Conjecture , fml.. They should make it unrated, this isn't fair!
 » 3 years ago, # |   +58 One of the problems was a straight copy, and the other one was a google search problem. Making this round rated cheapens the value of one's rating.
 » 3 years ago, # |   +3 In Div1-D, is it enough to check for each relation if it is contained in exactly one valid permutation?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +66 I solved using the following:Let A be such matrix that Ai, j = 1 if permutationi can equal j, and 0 otherwise.We know that the number of all valid permutation is a permanent of A, and in . So we have to check for some queries (x, y) that Mx, y = 1 (in , here Mx, y is the respective minor). It's known that Mx, y = A - 1y, x, so we just calculate A - 1 for n3 / 32 and win.UPD: and A - 1 exists since .
•  » » » 3 years ago, # ^ |   0 Nice solution!
•  » » » 3 years ago, # ^ |   0 I haven't got the only thing about Mx, y = A - 1y, x. Could you please clarify or give me a link or whatever.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +5
 » 3 years ago, # |   +45 is contest rated?
•  » » 3 years ago, # ^ |   0 now it's a good question
 » 3 years ago, # | ← Rev. 2 →   0 Actually, problem D is the direct application of Goldbach's conjecture. I think this is the 'ABC' in the world of math/number theory.I remembered that I've learned this when I was really really young, maybe the time when I was a primary student or a middle school student.Even though, I failed to come up with this quickly in the contest and tried several wrong ideas, wasting my time.From the view of problem setting, I don't think this problem (as well as C) is good. I think people don't want to train their knowledge of commen sense in problems like D in div2. These problems can be better if they engage more thoughts. As for me, I enjoy harder D, even if I can't solve it.But from the view of a problem solver, I think div2D is still good problem. It reminds us that we should not forget the most fundamental thing when we are solving hard problems. If tourist competed in this round, I think he would solve div2D easily. We as problem solver should think of how we can deal with such problems quickly under adverse condition instead of complaining about it. Life is not always fair, right?Anyway, thanks for the problem setters. It is not easy to prepare a contest. And somehow, it is not easy to come up with easy problems. Hope the next round will be better and I can become purple. :)
 » 3 years ago, # |   0 Regarding the repeated problem issue, if I were in charge I would zero out all results from 1A/2C but not unrate the entire contest. The problem lies exclusively in a single question, and yes it is a major problem, but it's not like all of the questions leaked or anything.Also, some here are saying 1B/2D was "unfair"; I have to say I personally disagree, with the caveat that maybe this wasn't the best problem to have in Div 2 because of this. Yes, 1B/2D relied on some knowledge/research -- but in the end, what harder problem doesn't to some extent? At the ICPC Mid-Central Regionals, one of the hardest problems anyone solved (and, in the end, the one that put my team over the top to go to Worlds) seemed intractable -- until, that is, I realized that the problem of deciding whether a given power level is possible reduces to 2-SAT. Without knowledge of 2-SAT and its reduction to the strongly connected components problem, this problem would be impossible to solve. In addition, most geometry problems have some innate knowledge requirement in order to reach the key insights involved. Maybe this problem was a bit irksome because its knowledge difficulty was above its algorithmic/implementation difficulty, but overall I don't think it was a bad problem (though, again, maybe it should have been replaced with something else for div 2).
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 But some people spent most of the time thinking about it, wasting the time which they could've spent searching on google D's solution
•  » » » 3 years ago, # ^ |   0 'some people' doesn't mean only you.
•  » » 3 years ago, # ^ |   +4 What about someone who had no idea about the repetition of problem C and solved it by himself giving maximum of his contest time? Will it be fair to zero out his accepted code?
 » 3 years ago, # |   0 Look at the code of winner of div2 round. Who uses DPDPDP as a variable? I wish there was no find and replace option built.
•  » » 3 years ago, # ^ |   0 I guess it turns out that KSL who was previously first place cheated. Maybe people downvoted you a little too early, because there definitely was something fishy about that guy.
 » 3 years ago, # |   +4 blokes ya just have butthurt cuz you didnt solve these problems. great contest, well done.
•  » » 3 years ago, # ^ |   0 And it doesn't look like you solved anything at all ;)
 » 3 years ago, # | ← Rev. 2 →   0 Hi. Can anyone help me with div.2 B? My code works fine on my computer, including the first test case. But on codeforces the output is -2 on first test. http://codeforces.com/contest/735/submission/22553933
•  » » 3 years ago, # ^ |   +8 I think you algorithm is incorrect to begin with. The correct answer is taking the first min(n1,n2) to the smaller set and the next max(n1,n2) to the larger set.
•  » » » 3 years ago, # ^ |   +8 Thank you, but I swap the values if n1 > n2: "if(n1 > n2) n1^=n2^=n1^=n2;"
•  » » 3 years ago, # ^ |   +1 change long double to double
•  » » » 3 years ago, # ^ |   0 Thank you very much! But why is it so?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 You shouldn't have used long double. Make the sums with long long and then cast to double when printing... Got AC here with it: http://codeforces.com/contest/735/submission/22558151 :/
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Could you also tell me why long double didn't work? edit: I googled it.
•  » » » » 3 years ago, # ^ |   0 I think there is a problem with codeforces and long doubles. I also submitted with long doubles and had WA in test 1. Better use double.
•  » » » » 3 years ago, # ^ |   +1 Well I don't know the actual size/range of long double but it seems like some kind of weird overflow (? overflow with sum 6?? lul wut??) Looked it up and on wikipedia they basically say it's unspecified so I guess it's better not to use it on contests... I recommend always using long long and cast, works well for me :s
•  » » » » » 3 years ago, # ^ |   +1 The problem is with printf and not long doubles!
 » 3 years ago, # |   0 In my opinion, tests for problem D are not enought. Some accepted solutions are checked only prime numbers to 1e5. I think there are no complete test cases.
•  » » 3 years ago, # ^ | ← Rev. 3 →   -8 I mean you are right!
 » 3 years ago, # |   +56 Why do people use Google during the contest in the first place? And if one uses the argument "everyone else is doing it" then how different is that person from all the other googlers?Correct me if I am wrong, but the purpose of these contests is to hone one's skills. Although the problem setter made a mistake posting one of his own problems, take into consideration that the author took his time to put this contest together.Without using Google, I find Div. 1 A&B very reasonable. It definitely took me more time to come up with Div. 1 A but I came up with that so why should I care that someone looked it up online. I didn't even know about Goldbach's conjecture but managed to solve B with some kind of brute force. It seems that the problems were more or less balanced if not for the googlers. But googlers are googlers, why should one compare himself or herself to them.
•  » » 3 years ago, # ^ | ← Rev. 2 →   -13 Agreed. Your non-Goldbach's conjecture version makes me feel better about that problem. There's never going to be a way to stop people from cheating anyways.
 » 3 years ago, # |   0 I spent most of time working on problem D... There seemed to be a fancy conclusion as the solution to problem D, but I hadn't got it. Umm... I should improve the level of knowledge.
 » 3 years ago, # |   0 why my code got WA in test 11 Div2Bsubmission
•  » » 3 years ago, # ^ |   +3 I think overflow in sum1 and sum2 might be the problem here. Try using long instead of int.
•  » » » 3 years ago, # ^ |   +3 yes it was the overflow i wish i did it before :(
•  » » » » 3 years ago, # ^ |   -8 Ah well, you won't do it next time :D
•  » » » » » 3 years ago, # ^ |   0 I got my rate down :(
 » 3 years ago, # | ← Rev. 2 →   0 How to solve Div 2 E / Div 1 C?
 » 3 years ago, # | ← Rev. 2 →   +15 Does anyone know why the problem C of Div.1 use unusual constraint for k?
•  » » 3 years ago, # ^ | ← Rev. 2 →   -26 There is a solution with O (2^k * n).We iterate over the vertexes, which will be painted (this vertex is removed no more than k from the root), brute over her mask and update dp.
•  » » » 3 years ago, # ^ |   +5 I cannot understand it still. Q_Q
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 Personally, I don't see why it's considered unusual?
•  » » » 3 years ago, # ^ |   0 I say it is unusual because the statement say that. And I cannot think out one solution using this constraint. My solution can be done in O(n^3). In order to use the constraint, I take some time in thinking it bug I give up in the final.
•  » » 3 years ago, # ^ |   +29 There is O(n·k4) solution. Dynamic programming with dp[2][n][k] — the number of ways to fill a subtree that either the topmost black vertex is at some height or the topmost non-satisfied white vertex is at some height.
 » 3 years ago, # |   0 Just googling round)
 » 3 years ago, # | ← Rev. 5 →   +4 thanks the author for ruining my 2 hours:/i should have participated in HR ICPC contest :(
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 All problems there were OLD HR problems :) People Googled/Searched HR archive and submitted :) So, by your logic, you would have complained about HR contest too!So the best solution for you would have been shutting down your system for the time being :DIt's better to stop complaining and learn :)
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 If you cared about improving you wouldn't say that (unless ofc you have solved all the problems on hr)
 » 3 years ago, # |   +28 waiting for Edtutorial just to give you your deserved downvote
 » 3 years ago, # |   +8 Wow, they actually made it rated.
 » 3 years ago, # |   +30 Did anyone take advantage of a problem div1A being googlable? There is no editorial or any comments under that problem. I've just tried to submit a solution there and got ERROR — so I guess it wasn't possible to test one's solution by submitting a problem there. The only possible issue I see is that someone may have already read that statement. There is a tag "hidden" though and maybe it means that a problem isn't showed in the global list of problems. Still, maybe someone managed to find it in some way before, but it doesn't look like a likely scenario.
•  » » 3 years ago, # ^ |   +13 Uh the solution is on quora.
•  » » 3 years ago, # ^ |   +24
•  » » 3 years ago, # ^ |   +131 This author should be banned permanently for giving the same problem twice. There should be no reasonable explanation for such behaviour. Giving one more problem on "Goldbach's conjecture" totally sucks as well. This round is ridiculous.
•  » » » 3 years ago, # ^ |   +11 Yeah, also take a look at his other problem on SPOJ. Not an exact copy paste as in Div1-A, but it requires Goldbach's conjecture. I wonder why he would need to copy-paste and/or re-use ideas from his own problems. This is utterly absurd.
•  » » » 3 years ago, # ^ |   +5 I can understand giving a problem which appeared before, you might not know about it, it happens from time to time. But when it's YOUR OWN problem...
•  » » 3 years ago, # ^ |   0 I didn't know that a solution is described somewhere. Ok, then it's a bad situation.
 » 3 years ago, # |   +8 Codeforces really wants me in div1 :)
 » 3 years ago, # |   +26 well, the round is rated for both division, same shity problem for the same author and with the same statement everything is fine , don't you think that at least we own you an apology ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Cmon, problem C div 2 was nice. The only mistake imo was to copy the exactly same statement.
 » 3 years ago, # |   +64 THIS IS RIDICULOUS!!Most contestants are complaining that problem A Div.1 is repeated with the same statement and the same author & problem B Div.1 can be googled easily and all we can get is IGNORANCE..I downvoted the contest, it should be UNRATED!!
 » 3 years ago, # |   +99
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Yes, the ratings have been published already mate. It is RATED.
 » 3 years ago, # |   0 This contest is just terrific!
•  » » 3 years ago, # ^ |   0 Wow, another account standing in the "Ban queue"! :D
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 you didn't do this round, why you are so emotional now? My dear "Trump"
 » 3 years ago, # |   +132 now , i think that Edvard is the only Armenian author in codeforces . :3
 » 3 years ago, # |   +8 Just for fun: problem with (a bit) similar idea to D2-D / D1-B: https://community.topcoder.com/stat?c=problem_statement&pm=11607
 » 3 years ago, # |   +79 I wonder if albertg will write an editorial for Div1/A or he'll just post the Quora link.
 » 3 years ago, # |   +20 Let's make the contest editorial post the most downvoted post on codeforces....
 » 3 years ago, # |   -6 I'm poor in math; Then I got a 75 ratings decreasing..; Horrible math....; However,This is a Nice round; Thank you! (I'm poor in ENGLISH too.TAT)
 » 3 years ago, # | ← Rev. 2 →   +3 I thought it would be unrated, maybe I will back to blue when I wake up tomorrow ...
 »