ed1d1a8d's blog

By ed1d1a8d, history, 4 years ago, ,

Greetings! CodeForces Round #336 welcomes both divisions this Wednesday, December 23, 2015 at 16:35:00 UTC. The round is authored by me, Amor727, chilli, and GlebsHP. We hope you'll like the problems. Scoring and score distribution: Not Dynamic; Div1: 500 — 1250 — 1500 — 2000 — 3000; Div2: 500 — 1000 — 1500 — 2250 — 2500

Much thanks to Amor727 and chilli for writing and editing problems, GlebsHP for organizing the competition and for his very helpful attitude, Delinur for translations, winger for testing, Marina Kruglikova for statement fixes, and MikeMirzayanov for his amazing CF and Polygon platforms.

During this contest you will be assisting Genos from the series One Punch Man. His master Saitama will also make some appearances. We wish everyone good luck and high rating in assisting the two. From the contest crew and the two fellows below, happy holidays!

Congratulations to the winners:

Division 1:

Division 2:

Editorial of round: /blog/entry/22256

• +427

 » 4 years ago, # |   +2 Auto comment: topic has been updated by tonynater (previous revision, new revision, compare).
 » 4 years ago, # |   +44 I love ONEPUNCHMAN, I was waiting for this for ages!!!! GL && HF!P.S Hoping for some funny jokes.
•  » » 4 years ago, # ^ |   0 Me too, bro. This anime is awesome.
 » 4 years ago, # | ← Rev. 3 →   -28 hardest contest, hardest life.
•  » » 4 years ago, # ^ |   -19 but easiest contest , easiest life :D
•  » » » 4 years ago, # ^ |   +10 Yep, you're so smart :D
 » 4 years ago, # |   0 3 + 3 = 6 round
 » 4 years ago, # |   +86 Div 1 contest being prepared by a Specialist? I can imagine contest setting going like this:-GlebsHP: Seriously? A Div 1 contest being prepared by two purples and a specialist? Who do you think you are?-tonynater, Amor727 & chilli:
•  » » 4 years ago, # ^ |   +78 Guess I should improve my rating. :)
•  » » 4 years ago, # ^ |   +1 Round #335 also has been prepared by two purples.
•  » » 4 years ago, # ^ |   +31 It reminds me of that conversation: http://codeforces.com/blog/entry/10797?#comment-160875 :)
 » 4 years ago, # |   0 like One Punch Man very much!!!
•  » » 4 years ago, # ^ |   0 Can you take a photo of your keyboard? Just interseted about chinese keyboards:D
•  » » » 4 years ago, # ^ |   +3 emm...)))
 » 4 years ago, # |   +35 Hi again guys! Thanks for support :DGL & HF!P.S. When I firstly have seen this blog I thought that it was Aldiar's :)
 » 4 years ago, # |   0 Saitama and GenOS! The round is gonna be awesome.
 » 4 years ago, # | ← Rev. 2 →   +14 Saitama is like a reference to tourist xD. Onecodeman ;DDD
 » 4 years ago, # |   +25 Code until you go bald :P
 » 4 years ago, # |   +4 Hope to celebrate the Christmas by becoming specialist :)
 » 4 years ago, # |   +24 Accepted from one submit. (c) One Submit Man
 » 4 years ago, # | ← Rev. 2 →   +18 To train for this contest, every day for a year I did 100 pushups 100 situps and 10km running
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 It's why you are cyan.To be RED you should do every day for a year 100 div1 C problems, 100 div1 D problems, 10 div1 E problems.
•  » » » 4 years ago, # ^ |   +53
•  » » » » 4 years ago, # ^ |   +1 what if.. the reply from Baian is a joke too :Phe substituted the physical training with hard CF problems
•  » » » 4 years ago, # ^ |   +7 To be accurate actually 10km div1 E problems ;)
•  » » » 4 years ago, # ^ |   +15
•  » » » » 4 years ago, # ^ |   +4 It's a reference to Onepunch Man, an anime that this contest will be referencing. It's a pretty good show for someone just wanting to watch something for laughs and giggles. A solid 10/10 in my book.
•  » » » » » 4 years ago, # ^ |   +28 A solid 5/7 from my side too!
•  » » » » » » 4 years ago, # ^ |   +3 Haha, I saw that 9gag post also
•  » » 4 years ago, # ^ |   0 You could've done better if you didn't forget to seal your AC xD
 » 4 years ago, # |   0 I love one punch man, and saitama !
 » 4 years ago, # |   -7 OneCodingMan
 » 4 years ago, # | ← Rev. 2 →   +102 tourist vs TooSimple that would be interesting.
•  » » 4 years ago, # ^ |   -83 Please Like me... Please .
•  » » » 4 years ago, # ^ |   -67 Please disLike me... Please .
•  » » » » 4 years ago, # ^ |   -28 Poor me... T-T :( ... What was I think about my comment and the Liks that it can get.
•  » » » 4 years ago, # ^ |   0 Likes can not be beggary You must work hard and be helpful to gain them(English is not my native language)
•  » » 4 years ago, # ^ |   +167 It will be TooSimple for tourist
 » 4 years ago, # |   +2 who looks like ONE PUNCH MAN in codeforces ??
 » 4 years ago, # |   -17 this contest will be amazing ☺ !
 » 4 years ago, # | ← Rev. 2 →   +32 It would be interesting if tourist TooSimple rng_58 and Petr all participate in this contest ;)
•  » » 4 years ago, # ^ |   +5 Match of The Legends!!! WoW
 » 4 years ago, # |   +11 So addictive site ^_^
 » 4 years ago, # |   0 One Punch Man...!! Who'd be the "One Code Man" of this contest.....??
•  » » 4 years ago, # ^ |   +3 Actually it'll be interesting to know who'll be the five code man/woman.
 » 4 years ago, # |   +6 GL & HF !
 » 4 years ago, # |   +1 The problem will be like determine the minimum strength of the monsters that can beat Saitama :D
•  » » 4 years ago, # ^ |   +5 in the last line, this description make the answer obvious : print -1 if it doesnt exist.
•  » » » 4 years ago, # ^ |   0 and all of the answers will be -1 then :D
 » 4 years ago, # |   +10 My first round on codeforces . I hope that I will will enjoy :)
 » 4 years ago, # |   +5 tourist and TooSimple are online, looks like they will participate . Guys get ready for the ULTIMATE CLASH OF 2015 .
•  » » 4 years ago, # ^ |   0 I wish tourist would become active in talking to the community. So few red coders care to participate in the comments section.
 » 4 years ago, # | ← Rev. 6 →   +7 deleted (i had a mistake about times)
 » 4 years ago, # |   -19
 » 4 years ago, # |   -76 ANIME is the WORST ONE I HAVE SEEN
•  » » 4 years ago, # ^ |   0 I dont think so
•  » » 4 years ago, # ^ |   0 All of my friends who watch anime said it is at least best of the season one. On myanimelist it is placed #10 in top. So I guess you have watched only #1-9 before that one? :-P
•  » » » 4 years ago, # ^ |   +16 What are you Sir Beresta :D a sword?
 » 4 years ago, # |   +6 Nice, I've just watched first two episodes of this anime today. Guess I'm ready for this round now :D
 » 4 years ago, # | ← Rev. 2 →   +22 Standard ? really ? 500 — 1250 — 1500 — 2000 — 3000 is standard now ?
•  » » 4 years ago, # ^ |   +13 It probably means "not dynamic".
•  » » » 4 years ago, # ^ |   +22 Yeah, sorry this is what I meant.
•  » » » 4 years ago, # ^ |   +31 I thought that "Not Dynamic" means that there will be no problems on dynamic programming ><
•  » » » » 4 years ago, # ^ |   0 Spoiler alert?
 » 4 years ago, # |   0 Am I the only one here who doesn't watch this show?
•  » » 4 years ago, # ^ |   0 Me neither. I watched Death note and I loved it, but I don't watch animes in general.
•  » » » 4 years ago, # ^ |   +1
•  » » » » 4 years ago, # ^ |   -22 What are your top 3 animes Xellos? :)
 » 4 years ago, # |   -35 i think we will hope for the many math problems!
 » 4 years ago, # |   -7 On an unrelated note, what do you guys think is more important? Learning more and more concepts or mastering what you know?
•  » » 4 years ago, # ^ |   0 Well i don't have much experience but i think whenever we learn a new concept we should try to solve a few problems related to it to make it clear to us . This way, we do both the things simultaneously upto a level .
•  » » » 4 years ago, # ^ |   0 When I say mastery I mean, solving 100-150 problems of that type.
 » 4 years ago, # | ← Rev. 3 →   -10 Dota 2 version!(Not everyone will understand...)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +12 Reminds me of thisEdit: That one is even better
 » 4 years ago, # | ← Rev. 2 →   +28 In all rooms...
 » 4 years ago, # | ← Rev. 3 →   +21 Что-то пошло не так
•  » » 4 years ago, # ^ |   -37
 » 4 years ago, # |   +11 Seems to be a bug in codeforces
•  » » 4 years ago, # ^ |   0 Actually I don't think it's a bug. Maybe it's a new feature to see all the other participants with hacks. I think it's actually pretty useful.
•  » » » 4 years ago, # ^ |   +4 The thing is that these people made successful challenge without submitting a problem :) I think it's a bug in standings, though.
•  » » » » 4 years ago, # ^ |   0
 » 4 years ago, # |   0 Anyone else keep getting a runtime error for Div2C/Div1A?
 » 4 years ago, # |   0 How to solve B? Is the solution is keeping remove the largest palindrome subsequence until the string become empty?
•  » » 4 years ago, # ^ |   +3 No. B is DP problem.
•  » » » 4 years ago, # ^ |   0 How to solve it with DP?
•  » » » » 4 years ago, # ^ |   0
•  » » 4 years ago, # ^ |   0 No, see 1 4 4 2 3 2 1 for example.
•  » » » 4 years ago, # ^ |   0 Actually, the approach works for this example.Remove 1 2 3 2 1, then 4 4.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 deleted
•  » » 4 years ago, # ^ |   +6 I think it is wrong approach. I don't know what to do when you have multiple choices to remove the largest subsequence.
•  » » 4 years ago, # ^ |   +3 I don't know if my solution will pass the final test cases, but here it is:Let DP[i][j] be the minimum number of operations to remove the continuous subsegment [i..j]. Then you have DP[i][j] = min(DP[i][k] + DP[k+1][j]), with k in [i..j-1]. You should also consider the case when V[i] == V[j], there DP[i][j] can also be DP[i+1][j-1].The complexity of my algorithm is O(n^3).
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 Sometimes it's better not to choose the largest. For example in 32123433 it's better to remove 212, but not 32123.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -10 Yes. But it is only the special case. You will check that '343' is also palindrom. And decide to remove '3' + '343' + '3' in 1 sec.
•  » » 4 years ago, # ^ |   -7 I think the question is quite similar to palindrome partitioning with bit modification. http://www.geeksforgeeks.org/dynamic-programming-set-17-palindrome-partitioning/But could not get the dp relation for the actual problem. :(
 » 4 years ago, # |   +4 B seemed much harder than C...
•  » » 4 years ago, # ^ |   0 Yeah. Worst case complexity is 10^10 (a=10^5,b=2*10^5). How did people do it in time ?
•  » » » 4 years ago, # ^ |   0 Seems obvious that solution with such complexity won't work :)I suspect that correct one would be like O(len(b)), however I didn't find the correct one.
•  » » » » 4 years ago, # ^ |   0 I know. I didn't even bother coding something with this bad complexity.
•  » » » 4 years ago, # ^ |   +11 Look at each character in A and count how many opposite characters in B it will have to pass as you shift A across B.
•  » » » » 4 years ago, # ^ |   +3 Now I feel dumb
•  » » » » 4 years ago, # ^ |   +3 Damn. So easy :(
•  » » » 4 years ago, # ^ |   +3 because you shouldn't solve it 10^10The correct solution is like that:Take a note, that you asked about the sum of "differences", not to count all differences. This leads to following approach. Fix some position in second string, and the first string will be shifting relatively to second one. Actually the positions, which are opposites to our fixed position, are making a subsegment in first string. And you just need to count how much exist chars different to fixed one in this subsegment.When you step from currently fixed position to next one, the subsegment is moving to the right. So just maintain the count of chars of each type in current segment and advance it carefully.
•  » » » » 4 years ago, # ^ |   0 Even better. Make a segment tree to count 1 and 0, and call for each index in a.
•  » » » » » 4 years ago, # ^ |   +3 Even better. Make an array with prefix sums to count 1 and 0, and call for each index in a. :P
•  » » » » » » 4 years ago, # ^ |   +3 Agreed
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Even better :). You need an array only for counting 0s because the 1s for some segments are equal to = length of segment — number of 0s for this segment.
•  » » » » » » » 4 years ago, # ^ |   0 That was what I meant, one array is enough, our statements are the same :)
•  » » » » 4 years ago, # ^ |   0 "Fix some position in second string, and the first string will be shifting relatively to second one."How the first string is shifting relatively to the second string if the position in the second string is fixed?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I mean imagine the process of taking differences of A and substrings in B as imposing A to some place in B. You can shift such a place and the imposing part is shifting too, consider all shifts, which overlay fixed position.
•  » » 4 years ago, # ^ |   0 The same for me.
 » 4 years ago, # | ← Rev. 3 →   -18 How to solve Div2D? I think it is dp[from][to] but I kept getting WA #14 :)PS: I realized where my mistake was :)
•  » » 4 years ago, # ^ |   +6 I know that feeling very well.
 » 4 years ago, # |   +14 Well, no need to wait for systests, it's back to Div 2 for me.I'll try to boost my self-esteem with a virtual contest...
 » 4 years ago, # |   +5 Lagged at the last 10 sec and couldn't submit B. I think the solution is correct. I hate when something like this happens :/
 » 4 years ago, # |   +8
•  » » 4 years ago, # ^ |   0 It will be fixed soon.
 » 4 years ago, # |   0 Merry Christmas ONEPUNCHMAN! We hope you will make happy us in 2nd season!
 » 4 years ago, # |   +13 when will the system test start?
•  » » 4 years ago, # ^ |   0 Soon!
 » 4 years ago, # |   +1 I solved B Div2 with prefix sums
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Your code looks sharp and understandable to me.Could you, please, explain how did you come up with the solution?Do you have some napkin drawings left? :)
 » 4 years ago, # | ← Rev. 2 →   -10 Can someone help me figure out where my code fails for 2C? https://code.hackerearth.com/a0bb04m?key=71b2fc5852347cfd361c5a3802736190
•  » » 4 years ago, # ^ |   +1 You need to sort pairs before doing binary search and dynamics.
•  » » » 4 years ago, # ^ |   0 damn... rookie mistake.
•  » » » » 4 years ago, # ^ |   0 Ugggh got me too. I spent forever trying to figure out what went wrong they were all presented in order until pretest #9.
 » 4 years ago, # |   0 I solved problem C(div2) by binary search? How do you think will it pass?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 It should, if it is the highest complexity in your solution (would be like O(N logN)).
•  » » » 4 years ago, # ^ |   0 Made binary search but got TL on 38 test... http://codeforces.com/contest/608/submission/14955285
 » 4 years ago, # |   +3 Could someone tell me what's wrong with my code for div2 C? http://codeforces.com/contest/608/submission/14957339
 » 4 years ago, # |   0 Thanks every one...
 » 4 years ago, # |   0 I wanna be the best hero!
 » 4 years ago, # |   -6 tourist come back............? tourist.........3374 TooSimple...... 3112
 » 4 years ago, # |   +1 Rating changes please.
•  » » 4 years ago, # ^ |   +5 +40
•  » » » 4 years ago, # ^ | ← Rev. 3 →   -11 -100
•  » » » » 4 years ago, # ^ |   +3 In the previous contest I had a -118 rating change.
 » 4 years ago, # |   0 thanks for completed quickly system testing and also will be so happY if rating update quickly.
 » 4 years ago, # |   +254 Bruteforce get AC on DIV1 D? http://codeforces.com/contest/607/submission/14951821
•  » » 4 years ago, # ^ |   +84 -_-.....How poor testing must have been so that such solution passes :|??
•  » » 4 years ago, # ^ | ← Rev. 2 →   +41 LOL. The test setter probably thought that div 1 guys know complexities well and would not attempt to write such a solution :)Even funnier is that these ineffective solutions have the best running time :D Don't waste your time preprocessing, mr. coder.
•  » » 4 years ago, # ^ |   +6 The slowest it gets is 171 ms with a TL of 3.5s. That's messed up.
•  » » 4 years ago, # ^ |   +15 I was in charge of tests for this problem and made the mistake of generating queries randomly, which gives them on average a very low complexity. We failed to catch this during our internal testing due to the fact that our sample brute force had O(N) updates and O(1) queries (instead of the O(1), O(N) like here). My deepest apologies, I'll definitely be more careful in the future.
•  » » 4 years ago, # ^ |   -31 Blue -> purple -> yellow :) Just in 3 contests
•  » » » 4 years ago, # ^ |   +5 It seems that there is a new test now, a rejudge, and you're 166th. Adding tests for the archive is commendable, but I do not approve of messing with the scoreboard :>
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 :< Wow another mistake. Apologies Meirambek, I'll return you to the scoreboard.
•  » » » 4 years ago, # ^ |   0 Try to resubmit your solution!
•  » » » 4 years ago, # ^ |   +8 От души братан :)
 » 4 years ago, # | ← Rev. 2 →   0 Can anyone tell me how to solve div2 C?I think it is at least not bad to boom ith beacon if activate it will destroy k beacons(k>1),so I do it by something like Prefix sum ,but keep WAing on test#11 QAQ.Is my thought totally wrong for this problem?
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Don't get your solution, but my AC was like that:For each beacon from 0 to n calc how much beacons would be destroyed if i-th beacon is starting one, using dynamic programming (we have calced all lower ones before i-th, so could be reused) and binary search (to find how many beacons destroyed by i-th). Complexity here is O(n * logN).After that try to disable from 1 to n beacons and calc best sum using data from the previous step. Complexity here is O(n).
•  » » 4 years ago, # ^ |   0 my AC was : http://ideone.com/z8dqVj ( No Binary Search ) consider this dp state , dp[present_pos] = total_beacons_affected_by_present_beacon + dp[previous_unaffected_beacon] here, previous unaffected beacon means the beacon which is unaffected by the present beacon After that try to disable beacons from present pos to n and calc best using the previous data i.e., min of total_beacons-total_beacons_until_this_beacon+dp[present_beacon] all positions .
 » 4 years ago, # |   0 matthew99 first. LOL:))
•  » » 4 years ago, # ^ |   +19 really is he/she a middle school user? O_o
•  » » » 4 years ago, # ^ |   +6 Yes he is.
•  » » » 4 years ago, # ^ |   +4 Probably from his handle, he is born in 1999 ;).
•  » » 4 years ago, # ^ |   0 Yes,He is
 » 4 years ago, # |   -8 Hi everyone, this is my first contest on codeforces. Someone could tell me when the editorial will be posted? And when the ranks are updated?
•  » » 4 years ago, # ^ |   +1 Editorial already posted http://codeforces.com/blog/entry/22256About rating, nobody knows)))
•  » » » 4 years ago, # ^ |   +2 Thanks!!
 » 4 years ago, # |   +7 Rating is a precalculated result.But why every time it should be given so late. Above 2 hours..but it should not be updated.
 » 4 years ago, # |   +18 And after every contest there is a dilemma: go to sleep or wait until raitings are updated...
 » 4 years ago, # |   -6 Ratings updated.
 » 4 years ago, # |   +72 Why DemiGuo's rating did not change being in TOP 5?
•  » » 4 years ago, # ^ |   +14 It seems that her submits are skipped... so strange! it's impossible! She was 1st for a while in contest! MikeMirzayanov , what's going on?
•  » » 4 years ago, # ^ |   +151 I'll be happy to read explanations about the submissions:
•  » » » 4 years ago, # ^ | ← Rev. 4 →   -26 I'd wager coincidence! The programs are small, and it seems highly unlikely for someone in Demi's position to consider cheating. Sadly I also can't offer much towards improving cheat detection.Edit: a friend of mine thinks the similarity is "clearly not a coincidence". Sigh... how does one reason about the probabilities involved here? Could be a scientific research question. Perhaps the users involved will make a statement, unclear what good that would do. I thought it better to give the benefit of the doubt, but hey at least we're not banning users.
•  » » » » 4 years ago, # ^ |   +35 Have you taken a closer look?These parts:  p = 0; for (int i = 2; i <= n; i++) { for (; p && A[p + 1] != A[i]; p = Next[p]); if (A[p + 1] == A[i]) p += 1; Next[i] = p; } p = 0; for (int i = 1; i <= n; i++) { for (; p && A[p + 1] != B[i]; p = Next[p]); if (A[p + 1] == B[i]) p += 1; } if (p) printf("NO\n"); else printf("YES\n"); differ only by replacing a with A, b with B and nxt with Next. This is NOT a coincidence.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +26 Also, they both have unused variables named now1 and now2. As much as I want to believe this is a coincidence, this is really hard to explain away.
•  » » » » » 4 years ago, # ^ | ← Rev. 9 →   0 It's possible you're right; it just seems weird from a psychology angle. Keep in mind there are a lot of pairwise comparisons to be made on Codeforces, so unlikely events can happen. A lot of the similarities are very natural simplifying choices to make (i.e. low entropy). We should check for stylistic consistency with her other submissions; that might "explain away" some of the coincidences.I'm just having trouble imagining someone with legit skills wanting to do this (especially when you're female so the whole world is watching you as sort of an example); even if it were, the code could have been disguised a lot better.Edit: I didn't notice that now1 and now2 are unused :/ Damn whyyyyyIf we assume that cheating did take place, what happens next? It looks like you can get away with cheating if you have the skills and take effort to obfuscate the source. Will Demi and others just get better at it? Do many orange/red members already do it??? Deterrence is hard if people with actual skills cheat.
•  » » » » » » 4 years ago, # ^ |   0 When someone doesn't try to hide the fact that they're cheating, they really don't care about consequences.
•  » » » » 4 years ago, # ^ |   +3 AC submissions are not only ones should be looking at.Consider submissions: They both WA9 and use such algorithm simulate first string, simulate second string, simulate first string again (the first submission contains original reference to now1 and now2). The second submission simulates second, first, second (probably because the first got WA9).
•  » » » 4 years ago, # ^ |   +3 i didn't want to say this just because i didn't want to attract attention but you guys made me say it ;D, from what i see from the coding style of both accounts the owner is the same person!
•  » » 4 years ago, # ^ | ← Rev. 2 →   -53 Nvm
 » 4 years ago, # |   0 Why do I have TL with O(n*log n) solution on div2c? http://codeforces.com/contest/608/submission/14955285
•  » » 4 years ago, # ^ | ← Rev. 2 →   -11 could be an anti-quicksort test case. (quick sort has worst case n*n)
 » 4 years ago, # |   +36 Div1C was a very elegant problem, I really liked it.
•  » » 4 years ago, # ^ |   +42 Thanks! I worked quite a bit on that one.
 » 4 years ago, # |   0 Div1C http://codeforces.com/contest/608/submission/14965956 Who tell me what is the wrong? I try to get the 30th data,the last 10 letters of the first string and the second,using this method if(n==999999&&a[0]=='W'&&a[1]=='N'&&a[2]=='W'&&a[3]=='W'){ puts(a+n-10); puts(b+n-10); } but I failed,because I find the 20th data is same with the 30th I also have try to run other's program to compare with mine using random data,but never find the difference. Who can help me ?