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!

Hope, there will be nice problem statements for English version ... :)

Most probably, I hoped a wrong thing... :/

Study for exams or do CF round? Hmm. Screw exams. :D

same here :(

classical situation.

Go to sleep or do CF round? Hmm. Stay aside please, sleeping. :D

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

This is my first round with "Java" and I hope not the last

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!

Good choice, my friend :)

http://apps.topcoder.com/forums/?module=Thread&threadID=804294&start=0&mc=2

Can 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 ?

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.

I was studying and hope to do well in this contest.

The terrible English problem statements ....

seems I'm not alone...

What is the approach for C? I tried subset sum type memoization with a variation but got wa on 6th pretest ....

me too, i got TLE on 6th pretest

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.

why does the solution considering the subset with max(total taste/ total calories) won't work ? it gives wrong answer on pretest 6

The problem is get k = (total taste/total calories) where total taste is as big as possible.

I'm unable to tell in words about problem description !!!! :/

solution or ediorial ?

Got AC?

(you edited your comment and made mine look silly :P)

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...?

I don't think so. A lot of people register 10 minutes before the contest even .

I mean, register in the website, not in the contest itself.

hmm then it may be but anyways its not that important to discuss here .

For sure. This happens every round. Just relax and enjoy problems and process of solving them.

The statement was as terrible and lengthy as last Round Codeforces Round #208 (Div. 2). So time-consuming to read them...

True story :)

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.

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!

can any body explain what "Denial of judgement" is ?

i got one on problem 'C' this round .

Anyone got WA on test 9 at problem D? I don't know what this test case has in particular

it has something to do with multiple edges between the same pair of vertices

Can you give an example, please?

or

The answer is 3 for both tests, but your solution might fail on one of them

My solution works for both :S

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 :)

Thanks, but it passed both the tests.

servers seem to be responding well to the loads now . There was much less glitches than previous times .

Good Problems :D

I am wondering why the time limit of E is 3s ? Please see the solution http://codeforces.com/contest/366/submission/5228621

It's so that slower solutions that don't use a certain mighty trick could pass, too :D

how much of that code is part of your template? :D

Rating?

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???

Why is rating updation so slow? zzzzzz

maybe because Berezin didn't thank MikeMirzayanov for faster judging system .

It's that :)

I just miss the clarification about problem C and can't solve it in contest time. Bad luck for me. :(

bad luck ...

rating:1696 TvT

missed the contest, coz of semester exams ... diverse set of questions # :)

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 8

test2: 4 4 1 2 4 8 1 3 1 4 2 3 4 8 3 4 4 8

5 and 1?

In the last sentences It show "return to his room as quickly as possible!"...

can anyone please give link to a similar problem or tutorial to problem C : Dima and Salad

You can first try simple subset sum problem and knapsack problem and then try to relate this problem with those two concepts .

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 integer

Now 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.

thanks :)

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?

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

editorials to the problems have been posted here