Berezin's blog

Codeforces Round #214 (Div. 2)
By Berezin, 11 years ago, translation, In English

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!

  • Vote: I like it
  • +140
  • Vote: I do not like it

Comments Comments (61)
| Write comment?
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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!

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Good choice, my friend :)

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it -24 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The terrible English problem statements ....

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me too, i got TLE on 6th pretest

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

solution or ediorial ?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Got AC?

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

    → Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

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

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

i got one on problem 'C' this round .

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you give an example, please?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        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

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          My solution works for both :S

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks, but it passed both the tests.

          → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Problems :D

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Rating?

→ Reply
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Why is rating updation so slow? zzzzzz

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

rating:1696 TvT

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply