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

### Berezin's blog

By Berezin, 6 years ago, translation, ,

Good day! The event named Codeforces Round #214 (Div. 2) will take place soon. My name is Dmytro Berezin and i am the author. This is my second round and Sereja hopes that this is the last one :)

Private life — is such thing, which can't contains too much happiness, so you should help Dima and Inna again. In addition, Sereja is not a negative character! He is rather some kind of circumstances you should fight with... Sometimes.

I want to thank Gerald Agapov (Gerald) for his help in round preparation, Maria Belova (Delinur) for statements translations, and Sergii Nagin (Sereja) for the fact he kindly (leaves the room sometimes) agreed to help in testing.

Sergii sends greetings and strongly recomend to read ALL tasks.

Point distributions will be announced. Honestly. And the distribution is: 500-1000-1500-2000-2500

Thank you for your time, have a nice round!

• +140

 » 6 years ago, # |   +8 Hope, there will be nice problem statements for English version ... :)
•  » » 6 years ago, # ^ |   0 Most probably, I hoped a wrong thing... :/
 » 6 years ago, # |   +38 Study for exams or do CF round? Hmm. Screw exams. :D
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 same here :(
•  » » 6 years ago, # ^ |   +2 classical situation.
•  » » 6 years ago, # ^ | ← Rev. 2 →   -14 Go to sleep or do CF round? Hmm. Stay aside please, sleeping. :D
 » 6 years ago, # |   0 Waiting on fire this Round to take my rank up to the SKY :D and i hope that problems come with good English and obvious statements
 » 6 years ago, # |   +30 This is my first round with "Java" and I hope not the last
•  » » 6 years ago, # ^ |   +3 If it will help you, author solved his own tasks in java also :) I can recomend you to use "fastReader" you can find it in any code of any participant in java with high reiting. Have a nice round!
•  » » 6 years ago, # ^ |   +4 Good choice, my friend :)
 » 6 years ago, # | ← Rev. 2 →   -24 http://apps.topcoder.com/forums/?module=Thread&threadID=804294&start=0&mc=2Can someone help me with above problem ? It is related to LRUcache. I use STL map and set but i get WA. Does anyone know of any test case where it fails ?
•  » » 6 years ago, # ^ |   +1 If you ask for help, make a new blog post for it. Don't do it in the comment's section of something completely unrelated. This way, you won't get an answer, but just low contribution.
 » 6 years ago, # |   +3 I was studying and hope to do well in this contest.
 » 6 years ago, # |   +4 The terrible English problem statements ....
•  » » 6 years ago, # ^ |   +5 seems I'm not alone...
 » 6 years ago, # |   0 What is the approach for C? I tried subset sum type memoization with a variation but got wa on 6th pretest ....
•  » » 6 years ago, # ^ |   0 me too, i got TLE on 6th pretest
•  » » 6 years ago, # ^ |   +4 It is subset sum, or knapsack. For each fruit i, assign an object with volume a[i] — kb[i] and value a[i], and the answer is the set with maximum value and zero volume.
•  » » » 6 years ago, # ^ |   0 why does the solution considering the subset with max(total taste/ total calories) won't work ? it gives wrong answer on pretest 6
•  » » » » 6 years ago, # ^ |   0 The problem is get k = (total taste/total calories) where total taste is as big as possible.
 » 6 years ago, # |   +6 I'm unable to tell in words about problem description !!!! :/
 » 6 years ago, # | ← Rev. 3 →   0 solution or ediorial ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Got AC?(you edited your comment and made mine look silly :P)
 » 6 years ago, # |   +8 I just want to know... if an user registers 3 hours before the contest for Div2, and then gets the first place... Isn't quite obvious that he is an Div1 user...?
•  » » 6 years ago, # ^ |   0 I don't think so. A lot of people register 10 minutes before the contest even .
•  » » » 6 years ago, # ^ |   +7 I mean, register in the website, not in the contest itself.
•  » » » » 6 years ago, # ^ |   -6 hmm then it may be but anyways its not that important to discuss here .
•  » » 6 years ago, # ^ |   0 For sure. This happens every round. Just relax and enjoy problems and process of solving them.
 » 6 years ago, # |   0 The statement was as terrible and lengthy as last Round Codeforces Round #208 (Div. 2). So time-consuming to read them...
•  » » 6 years ago, # ^ |   0 True story :)
 » 6 years ago, # |   0 The statements was very funny =), Problem D was my favorite (although I got WA), I get confused with a simple dijkstra but when I realized about that it need to be careful with segments, the contest was finishing.
 » 6 years ago, # |   0 Although some people are complaining about the English, I had no problems with the statements (some were lengthy indeed, but hey, that's part of a contest :P).For me, the problem selection was very nice (although I was not able to perform well :P). Some dp and graph problems with some easier ad hocs, that's more ICPC style than many other rounds (and for me, who wants to practice for next year's ICPC, it was good :)Nice job!
 » 6 years ago, # |   0 can any body explain what "Denial of judgement" is ?i got one on problem 'C' this round .
 » 6 years ago, # |   0 Anyone got WA on test 9 at problem D? I don't know what this test case has in particular
•  » » 6 years ago, # ^ |   0 it has something to do with multiple edges between the same pair of vertices
•  » » » 6 years ago, # ^ |   0 Can you give an example, please?
•  » » » » 6 years ago, # ^ |   0 2 2 1 2 1 2 1 2 1 3 or 2 2 1 2 1 3 1 2 1 2 The answer is 3 for both tests, but your solution might fail on one of them
•  » » » » » 6 years ago, # ^ |   0 My solution works for both :S
•  » » » » » » 6 years ago, # ^ |   0 Well, my first attempt failed on 9th test and fails on one of these. After I made it work on these tests, got AC. Sorry I wasn't able to help you :)
•  » » » » » 6 years ago, # ^ |   0 Thanks, but it passed both the tests.
 » 6 years ago, # |   0 servers seem to be responding well to the loads now . There was much less glitches than previous times .
 » 6 years ago, # |   0 Good Problems :D
 » 6 years ago, # |   0 I am wondering why the time limit of E is 3s ? Please see the solution http://codeforces.com/contest/366/submission/5228621
•  » » 6 years ago, # ^ |   0 It's so that slower solutions that don't use a certain mighty trick could pass, too :D
•  » » 6 years ago, # ^ |   0 how much of that code is part of your template? :D
 » 6 years ago, # |   +3 Rating?
 » 6 years ago, # |   +13 In the first page of the rank list there is only 6 regular blue coders in top 20. Rest 14 contestants are new participant(holding top 5 in today's rank list). I was wondering what is the secret behind it??? If after a codeforces round, the change of rating depends on the position in the rank list then it is a very annoying and heartbreaking for div-2 coders if div-1 coders participate with a new handle in each div2-only contest. I have one more question. Will my handle be banned if my contribution underflows 32 bit signed integer for any of my post???
 » 6 years ago, # |   +4 Why is rating updation so slow? zzzzzz
•  » » 6 years ago, # ^ |   +6 maybe because Berezin didn't thank MikeMirzayanov for faster judging system .
•  » » » 6 years ago, # ^ |   0 It's that :)
 » 6 years ago, # |   +1 I just miss the clarification about problem C and can't solve it in contest time. Bad luck for me. :(
•  » » 6 years ago, # ^ |   0 bad luck ...
 » 6 years ago, # |   +5 rating:1696 TvT
 » 6 years ago, # |   0 missed the contest, coz of semester exams ... diverse set of questions # :)
 » 6 years ago, # |   0 It is hard to understand Pro D. Can anybody tell me what's the result about these tests: test1: 4 4 1 2 4 8 1 3 1 3 2 3 4 8 3 4 4 8test2: 4 4 1 2 4 8 1 3 1 4 2 3 4 8 3 4 4 85 and 1?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 In the last sentences It show "return to his room as quickly as possible!"...
 » 6 years ago, # | ← Rev. 2 →   0 can anyone please give link to a similar problem or tutorial to problem C : Dima and Salad
•  » » 6 years ago, # ^ |   0 You can first try simple subset sum problem and knapsack problem and then try to relate this problem with those two concepts .
•  » » 6 years ago, # ^ |   0 It is a tricky variant of classical subset sum problem(at least i felt so). The observation I made during the contest was something like this:we have three conditions : 1.a/b should be exactly K; 2.We have to maximize a; 3.we have to pick at least one;condition one: a/b= k => a=b*k =>a-bk = 0 since k is only 10 a,b<=100 , a-bk should fit in 2*10^4 , I kept abs(a-bk) and a flag(say signflag) that distinguishes state a<=bk or a>b in previous choices.then from each position we have two choices, whether we select the current one or not.I also kept another flag(say takenflag) to keep track of whether i have taken at least one salad or not. When i have decided to take some ai,bi, I have updated my current difference according to the status of my signflag that tells me whether in previous choices a<=bk or a>bk.and then updating the takenflag into 1. Therefore, Our next call would be a[pos]+rec(pos+1,newdiff,newsignflag,1); see taken flag is 1, we have choose at least one.And if we don't choose current position, our another possible option is: rec(pos+1,olddiff,oldsignflag,takenflag); just an increment in position keeping other values unchanged.now we must have to take maximum between these two options: therefore we return dp[pos][olddiff][oldsignflag][takenflag]=max(a[pos]+rec(pos+1,newdiff,newsignflag,1),rec(pos+1,olddiff,oldsignflag,takenflag)); why do we keep max??? because we have to maximize a in a/b=k;base case:if(pos==N) we have no choices left, its time to decide by observing what happened in past. Form the states we can say what happened in past. If oldiff==0 then we can say the way we came to pos==N maintains a-bk=0 => a=bk => a/b=k. Also we have to check the takenflag whether we took any salad or not. SO, if(pos==N and olddiff==0 and takenflag==1)return 0; else return -inf;//inf=any large integerNow we are sure that if there is such path to choose from the given sets such that a/b=k, we shall definitely reach at if(pos==N and olddiff==0 and takenflag==1)return 0; and get a positive answer. Otherwise, whenever we have no option to choose we are returning -inf which is a very large negative number. That means our maximization process returns a negative number when there is no way to satisfy a/b=k for given set.It was a very naive formulation by me. But there are plenty of excellent source codes that will reduce the state and your coding complexity but the idea is almost same. For example if you start from a very large number and in the base case you reach at that same number then you can say that there is a way, because you are actually shifting all integers by a large value(20000 should be enough) and thus you don't need the signflag.Sorry for poor English.
•  » » » 6 years ago, # ^ |   0 thanks :)
 » 6 years ago, # |   0 can't appreciate language used in problem description, had to go through test cases first and then tried to understand.. btw where can i find editorials?
 » 6 years ago, # |   0 won't there be any discussion post on the problems of this round?? i'm trying to find out in which pattern i should save the results in problem C Div 2
•  » » 6 years ago, # ^ |   0 editorials to the problems have been posted here