Berezin's blog

By Berezin, 11 years ago, translation, In English

Hi everybody!

When you've seen my nickname you probably thought: "Finally! At least this round is not made by Sereja! And you are right! I, Dmytro Berezin(Berezin) give this round... and my neighbour Sergii Nagin(Sereja)

The action will take place in Friday, 25th october, 19:30.

Thanks to Gerald Agapov(Gerald) and Maria Belova(Delinur) for help in preperation and translation of problems respectively.

Thanks to Yaroslav Tverdokhlib(KADR) for help in testing.

You have to help Dima equip his personal life :)

The point values for this cause is 500 1000 1500 2000 3000.

Sergii strongly recommends you to read all the tasks.

I highly recommend you also to try to solve them.

Thank you for your attention, and have a successful round!

Tutorial: http://codeforces.me/blog/entry/9334

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

| Write comment?
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I hope that it will be a good contest for every point of view as Sereja's contests.

»
11 years ago, # |
  Vote: I like it +48 Vote: I do not like it

the law of conservation of Sereja : Sereja can be neither created nor destroyed, but he always go from a contest to another contest!

»
11 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I hope you guys have managed to solve the problem with the servers from last time.

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

I hope that the English problem set is not the same level of English as this post!

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

    I am really sorry for the level of my English, if you read my bad-english post attentively, you will find, that english problems are not translated by me.

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

      What?? You have advanced level Enlish in university and bad English at codeforces))

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

    problem set is level of English? do you knoving engrish?

»
11 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Sereja is a hard-working and good problem setter :)

»
11 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

good luck all :)

»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I hope it will be a interesting contest and everyone will enjoy and learn more knowledge from this contest .

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I don't know if I'm the only one but I'm having tough time understanding the statements.

This is the first time it has happened to me since I've joined CF. :(

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

Why so hard-thinking & tough understanding problems in this round... Dying for none solved problem...

»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

a very awful only DIV 2 contest

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

Could someone explain solution of Problem D?

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

    DP problem: DP[i][j] 1<=i<=n 0<=j<=1

    DP[i][0]=the answer of the first i hares when before i,feed i-1;

    DP[i][1]=the answer of the first i hares when before i-1,feed i;

    final answer will be max(DP[n][0],DP[n][1]); sorry for bad english.

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

    I'm still not sure if this solution will be accepted, but here's a simple one:

    State is the current hare and a flag whether the last hare that was processed was fed before the current one: 1 if it was fed before, 0 if not. So if the last hare was fed before the current one the value for this state is max(b[current]+state(current+1, 1), c[current]+state(current+1, 0)). Otherwise it's max(a[current]+state(current+1, 1), b[current]+state(current+1, 0)). The reason why this works (I hope) is because the only thing you care is whether the current hare was fed before the current-1 and whether it was fed before the current+1.

»
11 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Problem C

Tell all extracted numbers to Inna and then empty all containers.

I guess lots of people who got WA#10 didn't see then empty all containers.

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

    Also I found a bit tricky that the sequence of operations doesn't necessarily end in 0, so you can do whatever you want with the last numbers.

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

      yes my very first submission failed on this test case (pretest 3).

      but there was another tricky case is when there are more than 3 elements before a 0 with the same maximum value (pretest 5). example 5 5 5 5 0 this failed my second submission 4886056 :P

      my third 4887916 passed all the pretests, and, thankfully, the system tests! :)

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

    I am one of the victim :( .

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

    oh my god...i missed that... so sad......

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

    I missed the exact same point!

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

What a great problem for C! One of the trickiest problem i've ever seen. Fully apprecieted, thanks @Sereja!

Although, i spent too much time on it. After i solved it [as i think now, before system test :D], this problem idea made my day! Nice~!

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

please explain problem c for me I dont understant that

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

I'm quite astonished. After finishing C, I wrote a DP solution for D, but that runs in O(N^3). After getting TLE in pretest 12, I just had one minute left so I just limited the internal loop to 100 iterations, so the DP would not be computed correctly in some cases. But still, my solution passed the final tests. So lucky :D

4890679

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

here is my problem C, wrong answer on pretest 3 http://codeforces.me/contest/358/submission/4890344 pretest 3, give 0 as n, which is totaly against what it says in the problem: The first line contains integer n (1 ≤ n ≤ 10^5) — the number of Inna's commands.

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

    The input of pretest 3 is clearly seen:

    2 0 1

    So, I advice you to check it again more carefully.

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

    yeah i figured it out, nothings wrong

»
11 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

very quick system testing for 3500+ users. problem A gets severely affected.

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

In problem B it was mentioned that message size will not exceed 10^5 but test 24 was. 100000 i . . i For which message size will be atleast 3*10^5 . It cost me WA . Its cheating. :'( :'( . Someone must look into this.

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

    Not really, it would have to be at least 3*10^5 if the answer was yes, but it's no.

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

    no, the problem only guaranteed total length of all words doesn't exceed 10^5 which is valid for that test, and that doesn't mean it also guaranteed all words + '<3' also will not exceed 10^5

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

    Not really. It does not say that the text message will contain all the read words.

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

how did so many users fail the system tests of problem A?? o.O

was there a tricky case? there must have been one, because it's impossible that so many users were incorrect with their ideas!

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

Can someone explain how Prob A is to be solved? I started off wrongly and got entangled, realizing mistakes after every wrong attempt.

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

    the only way there is a self-intersection is, when there are 4 points of the form i j i j, meaning that a semicircle goes from point 1 to point 3, and also another goes from point 2 to point 4.

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

      a.k.a you have two segments, given by coordinates x1a,x2a(left,right) and x1b,x2b(left,right) and the first should start before(strictly) the second and should end before(strictly) the second

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

    There are four cases, handle them and you get AC:

    let A,B be the last two points entered, and C,D be each pair entered before. These patterns are the only one producing entanglement:

    ACBD BCAD CADB CBDA

    (Note that if you have XYZ entered before, you handle the pair (x,y), then (y,z), etc)

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      actually the cases can be reduced if A = min(x1,x2) and B = max(x1,x2)

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

    it is easy to check when they do not intersect, so you have [a1,b1] and [a2,b2].

    they do not intesect if b1<a2 or b2<a1- the case when EXAMPLE: E1:([1,4] and [5,10]) and
    E2:([5,10] and [1,4]) and when one interval is subinterval of the other so: (a1>=a2 && b1<=b2) || (a2>=a1 && b2<=b1) example:
    E1:([4,7] AND [1, 8] ) E2: [1,8] and [4,7]) so you check every connected pair of points.

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

    Thank you, everyone! :) I got it! Consider x1, x2, x3, ... , xn. Make pairs (A,B) for all x(i),x(i+1) such that:

    A=min[x(i) and x(i+1)] and B=max[x(i),x(i+1)]

    Now, consider 2 segments (P,Q) and (R,S).

    P ---------------------- Q

    'R' can lie either within PQ or outside it.

    1. If R lies outside,

    R---P--------------Q

    S can either lie outside or inside. If S lies inside PQ, then there is an intersection, else there is not.

    R---P------S-------Q (intersection) R-S-P--------------Q or R---P--------------Q---S (no intersection)

    1. If R lies inside PQ,

    P -------------R-----Q

    If S lies Outside PQ, then there is an intersection, else there is not.

    P -------------R-----Q---------S (intersection) P -------------R--S--Q ( no intersection)

    So, it is just 2 cases we have to check, if we make a min/max pair.

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

      Actually you can get past the problem with brute force( O(n^2) ) by treating only one case.

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

Awful translation, made me unable to solve problem D. If hares 1 and n only have one neighbour they should be unable to be in the state where they have both neighbours full or empty but in the first test case it is clearly visible that the answer is 4+3+2+4 or 4+2+3+4, both cases leading to the last hare getting its happiness from BOTH his neighbours being empty (what an evil hare!!!)

Can someone explain that?

By the way, Sory for mi bad englando!

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

    What's the problem, then? The sample clearly explains that question. That's what the samples are for — clarifying the problem statement (and testing the program, of course).

    And it kind of makes sense, if you imagine the happiness values given per number of full adjacent hares, which is at most 1 for the border hares.

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      "Inna knows how much joy a hare radiates if it eats when either both of his adjacent hares are hungry ... or both of the adjacent hares are full".

      Last time I checked both was considered as being two.

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

        Yeah, the translation isn't precise, I give it that. But I'm saying it shouldn't pose a problem in the contest, as long as you look at the samples and try to understand them carefully.

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

          Being less than precise, it's contradictory.

          I understand that nobody is perfect and I do not mind grammar and other translation mistakes but the fact that annoyed me was that at the question :

          " In the first test case, to get to 13 happiness the last rabbit should be fed before both his adjacent hares ("Number ai in the first line shows the joy that hare number i gets if his adjacent hares are both hungry") but this would be imposible because the last hare does not have two adjacent hares. What should be done? "

          I received: "Read the problem statement."

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

            I'd have replied something along the lines of "That's allowed" instead, since the inclarity really comes from the problem statement being what it was.

            But the way I see it, you're nitpicking about formal correctness too much during a contest, and that might have cost you points. You really could've just decided based on the samples, instead of asking. (I try to understand the samples instead of the statement quite often :D)

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

              I understand that I might be too strict about these things but I learnt from life( pointing at programming contests ) that If you don't make sure of every last detail you will most certainly regret it later.

              And along the lines of understanding the problem from the sample cases, why not go as far as to give the contestants only the sample input and output: "Let them figure out the problem statement!" ?

              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                Rev. 2   Vote: I like it +3 Vote: I do not like it

                Trust me, there are much worse statements. Here, the basic idea of the problem was clear, yours was just a minor question. For example, I didn't even think about it (but I would, if there was an answer "Impossible" mentioned in the statement) when I read the problem. (Apart from it being formally incorrect, ) it's not nearly as bad as you make it seem.

                I guess it just takes experience with reading problem statements.

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

                  "Just because other kids do drugs at his age we should go easy on our own for skipping school."(or something along those lines)

                  Besides, not everyone has the same mentality:

                  While you and probably the majority of the "red community" could make out a poorly formulated problem from the available test cases, I and maybe others below the "purple grade" will have difficulties in understanding it. To be fair for everyone, why not make it correct?

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

                  Lol, it says my comment can't be nested anymore. We need to go deeper :D (Maybe it's best to consider this the end of discussion, since we don't really have more to add.)

                  On topic: yeah, I'm that kind of guy. I simply accept small imperfection (and bash at large one that much more :D).

                  Of course, all is a matter of opinion. I just want to say what I think about it. But it may be precisely because of mentality that I got this far — to be precise, it's "if you aren't doing well enough, just try to improve as much as possible". Things like this, I take as a challenge. I still have ways to go, though. Red is just the "can solve easy/medium problems in time" level.

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

Very nice round — congrats to writers — , but I think that you sould put more pretests if you make statements that request answers "yes"/"no".

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

Does E involve eulerian/hamiltonian paths?

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Yes, it involves Euler tours on an undirected graph.

    First, vertices: for each possible K you can extract a graph of which points were directly visited: Assuming the upper-leftmost point is at (sx,sy) then exactly all points of the form (sx+i*k, sy+j*k) are intermediate positions for the victim.

    The remaining '1's indicate moves from one intermediate point to another, so if there is an unbroken line of points between (x,y) and (x+k,y) or (k,y+k) then an undirected edge should be added between them.

    A valid sequence of kicks corresponds to an Eulerian path through this graph, so you just need to apply the standard algorithm for verifying that one exists.

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. We'll have to consider àll unit squares as starting points right?
      2. What exactly is a semi-Eulerian path?
      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        I was taught that a fully-Eulerian path starts and ends at the same vertex, but a semi-Eulerian path begins and ends at distinct vertices. (upd.: above definition is wrong.)

        In the former case, any vertex will do as a start point because the tour is closed and cyclic.

        In the latter case, the two endpoints will be the only ones with edges.length()%2 == 1 and either will do as a start point.

        In practice you don't need to explicitly identify start and end points -- you can just check that the graph is connected and has either 0 or 2 vertices with an odd number of edges.

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

          Ok, thanks!

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

          Interesting, I was taught that a Eulerian circuit starts and ends at the same vertex, while a Eulerian path in distinct vertices.

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

            Yes, after a quick check it turns out that "fully-Eulerian" and "semi-Eulerian" are supposed to describe graphs, not paths.

            Maybe my teacher was a little confused. Alternatively, maybe it's time to invest in a hearing aid and/or start paying more attention in lessons.

            Revised the wording -- thanks!

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

Sorry but for B, why this case is a "yes" ? 3 i love you <3i<3love<23you<3ww I thought he can only insert "digit", "<" and ">"

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

    Then Dima inserts a random number of small English characters, digits, signs "more" and "less" into any places of the message.

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

      oh I missed that, so sad :( small characters mean "lower case" right?

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

        yep

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

          by the way the accepted solutions output is "yes" for 3 i love you <3i<3dont<3love<3you<3

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

            as "dont" can be counted as " a random number of small English characters, digits, signs "more" and "less" into any places of the message. " it is within the bounds of the statement

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

              The contest is over, so now we can see the truth: Dime will never send such sms, so the answer is "no" :) P.s. but the comment above is correct when speaking about contest rules.

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

              as a matter of fact it's not an encoding, decoding system, the better way was not using the terms encoding and decoding, the translation is one way it should be noted finally I should thank the writers there is a little mistake doing a great work

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

            haha :D

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

    costed me 3 WAs, but finally ACed

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

Tired of being victim of overkill :( Solution of B was doable in 10 lines, instead I choose the long way..

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

Could anyone help me why my submission 4899840 can't pass Test 12?

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

    For: 3 i love you <<<<3333iloveyou

    Your code outputs yes while it should output no. The problem with you code is that it does not check if the characters are in the right order i.e (<3word1<3word2...), it just checks if they are there.

    It's something similar to this: If your program would check if two words are the same, the words "love" and "elov" would be the same.

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Thank you so much for answering. I found where the problem of my code is with your help. I changed pos=sts.find_first_of(s[i]); in my code to pos=sts.find_first_of(s[i],pos); and it was accepted successfully. :)

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

Loved the contest. Just depicts where a contestant's reading and interpretation skills stand.

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

I wrote the code for Dima and the Text Messages in CodeForces Round 208 division-2 in Java. Every time I submit the code it says TLE. But don't know why it says so even if I am using BufferedReader and PrintWriter for reading and printing the values. My solution code in 4901148.

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

    In Java a + b is slow for strings (copies both a and b), you have to use StringBuilder.append() instead.