GlebsHP's blog

Codeforces Round #107
By GlebsHP, 13 years ago, translation, In English

Hello everybody!

Today's round will be held by SergeiFedorov and me. We have done our best to make it diverse (different task complexity and themes) and rated (we know it's important). Your questions, wishes and constructive criticism (destructive we already can do :-)) leave in comments.

The contestants will plunge into the cold February of Nvodske and will be to help one's friends to survive the cold. Just imagine all responsibility!)

On this occasion I would like to thank all Codeforces team for the great job, they are doing, Artem Rakhov (RAD) for his help in task preparations, Maria Belova (Delinur) for problems translation, my mom, my dad, our soundman and Tuscany winemakers, for us didn't fall ill while preparing this round.

Distribution will be something like:

div. 1: 500-500-1000-1500-3000 (yeah, it really costs 3000)

div. 2: 500-1000-1500-1500-3000

Good luck & have fun!

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

Comments Comments (104)
| Write comment?
»
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Good luck all.

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

3000 point problem In both division :O . That would be amazing (either for solving or learning) :)

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

3000!! Is the problem something like writing an OS? :)

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

For problem B div 1, substring means contiguous sub-sequence?

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

    Did you know that there is "Ask a question" function here?
    I asked the same question during the contest, and they said "NO".

    [Edit] I was wondering why I am getting negative votes, but when I read my question again,
    what I asked was 'Is "ac" a substring of "abc"?'.
    What a foolish mistake! I am sorry for the confusion.

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

      Weird. I asked this question too, and they said "yes".

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

div1, B. What if (k > n) ?

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

    mn

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

      Я час потратил, чтобы это понять. В конце от безысходности изменил так условие и прошло:(

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

      какого чёрта? "строк длины ровно n", "ПОДСТРОКА длины В ТОЧНОСТИ k". у меня у одного проблемы с пониманием того, как любая строка может подходить?

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

        Покажи мне хоть одну подстроку длины 42 в строке abacaba, которая не является палиндромом.

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

    any string is OK. So ans in mn

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

    Than any string will do as there is no restriction

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

      Why is that... when k>n there doesn't exist any string satisfying the constraint shouldn't the answer be zero...?

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

        We do not need a string, that should satisfy the constraint. We just required that ANY string must satisfy the constraint

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

          That's totally misleading statement... :( (or I was too stupid to figure out at the time :P)

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

            If you've worked with logic you come to think like that.

            The statement "If 1=0 then 2=3" is always true, because 1 isn't 0. After some time you forget that that's not the way normal people think, (They think the statement doesn't make sense), and confusion can happen.

            However, I very much recommend thinking the logic way. It just works more often :)

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

        I also thought 0. :(

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

          Me too. The problem statement is not well written.

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

            When k > n, there are 0 substrings of length k. And there are 0 substrings of length k that are palindromes.

            0 = 0, therefore all substrings of length K are palindromes. In this respect, the problem statement was written correctly.

            However, it IS a common confusion specially if not familiar with how the "For every" quantifier works on empty sets. And after all, (n > k) is a silly test case to include — its only addition to the problem is this confusion. I think at least it would have been better if (k > n) was not allowed or was an example.

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

          Five minutes or so after receiving WA #3, I raised a clarification asking that, for K > N, whether I should output N^M or 0. And the reply I got is:

          "No comment."

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

            I asked if for K > N is 0 correct answer and reply was "no".

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

    [Posted to the wrong position] I am really sorry.

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

    why the answer is not 0? I got lots of wrong answer on case 3..

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

Though my rating may increase i think this round should be unrated. CF was down for about 7-8 minutes and also got down several times last 20 minutes. I lost valuable points because of server down,it got down just when i tried to submit C,and i had to wait for 7-8 minutes to submit it.

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

    The worst part is that the problem statement for C changed. I didn't check the statement again and spent lots of time trying to produce correct output for C.

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

      Statement for D was also changed.

      Do they only happens in the English version?

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

        If D also changed then they really should have updated the problems page with that message.

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

          I mean really, there are messages for problem C/E so that if you read 'undefined' in a popup you will get to know that the problem statement was changed.

          But if dolphinigle's report that D changed is true, then there should have at least be a note in the problems page saying that it was changed...

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

            It was sort of minor I suppose (replacing "until" with "while"), though it did cost me some good time, since I turned off my common sense during programming contests.

            Maybe I should rethink that protocol :S

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

      I was the same

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

      Same here... somehow did not get the clarification broadcast, couldn't understand what's wrong before refreshing out of despair

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

        I've got a javascript alert which said "undefined". In last contest i've got same alert and than found that my solution have been hacked. But this time it was the clarification. Hope admins will fix it soon.

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

          Ahh... There WAS also that "undefined" alert box for me. Somehow I wasn't in the mood or something I didn't think much about it and simply ignored the alert. Now that you've mentioned it there was indeed the JS alert box with unknown intention... Should have thought it's trying to tell me something though :p

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

            Indeed when I got this "undefined" prompt, I had a first impression that, this may be due to some bugs in Codeforces system, or admin accidentally broadcasted a wrong message. (Meanwhile I was busy thinking for problem C sample test case #2, and I simply ignored the box.)

            Perhaps I did this because in previous codeforces testing round, there was some prompt like "Don't worry, it's just a testing."

            → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

I think it should be fair to make this round unrated. Lots of problems came up and affected vast of coders.

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

What datastructure do you need for maximum subarray part of div 1 C? I was thinking maybe use a segment-tree with several fields for combining the segments in the tree.

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 3   Vote: I like it -13 Vote: I do not like it 
        double mn = 0, sum = 0.0;
    for (int i = 0; i < n; i++) {
        sum += y[i]; mn = min(mn, y[i]);
        res = max(res, sum - mn);
    }
    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It can be done without segment tree.For each interval [a,b] its length(b-a+1) can be uniquely represented in binary number system.Let this number has m ones in binary form: length=2^k1+2^k2+....2^km..(k1>k2>...>km)..Then we can solve for intervals [a,a+(2^k1)),[a+(2^k1), a+(2^k1+2^k2) ),.... individually and also check for the subarrays which lies in several consecutive intervals.

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

Can anybody tell me what is the problem with using below code in problem B div 2?

cout << "\b." << "\n";

it was working fine on my system but was giving wrong answer on pretest and also on custom as it wasn't erasing last ",". It cost me 2 penalties :(. Solution id 1192671.

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

    Because '\b' is a char too. It doesn't have any special meaning outside terminal.

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

    '\b' only means backspace on terminal, but it cannot erase you already output in the stream.

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

    Ah, I very much like what you were trying to do. Those final ','s are so annoying :)

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

C-Div2. "Number's divisor is called non-trivial if it is different from one and from the divided number itself."

I thought it means that for number N, the divisor d should not be equal to 1 and N/d. But now my friend tells me that it meant not 1 and not the number itself.

Now, it makes sense. But why add the word "divided"? I took the long route of solving the problem because of this condition and now it is wrong.

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

    Divided != divisor. If text was "...from one and from the divisor number itself", you'd have been right.

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

Can anyone explain how the solution to the second example case of Smart Cheater is constructed?

I thought the conductor should not sell tickets for the last four segments, resulting in an expected profit of 466.32 + 973.55 + 2537.56 + 72802.56 = 76779.99, but this 80 less than the reference output. I can break down these numbers further if it helps, but I wonder what I'm missing here!

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

    Conductor should choose C and D for each passenger.

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

    For each passenger conductor may choose his own [C;D] in [A;B]. This segments [C;D] may be distinct for various passengers.

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

      I got the same output as Soultaker. (And of coz, after quite considerably long time to find that the problem C's statement is updated.) The problem statements are so ambiguous... I could only understand it right now.

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

        I think that these ambiguities are due to the English translations. The problem setters are usually programming contest veterans, so I assume they know how to write clear and unambiguous problem statements, but those qualities may be lost in translation.

        For example, for this problem, I think for this part:

        However, the conductor can choose no more than one segment NOT TO SELL a ticket for. We mean that conductor should choose C and D (С <= D) and sell a ticket for the segments [A, C] and [D, B], or not sell the ticket at all.

        The original Russian text reads:

        Однако кондуктор может не продать пассажиру билет от остановки c до остановки d (c < d), или вовсе не продавать билет. Более формально: Кондуктор выбирает не более одного отрезка с C по D (C <= D) на который он НЕ ПРОДАЕТ БИЛЕТ.

        I don't know Russian so I'm not entirely sure whether this is much more clear, but at least I spot the word "пассажиру" (meaning "passenger") in there. The English version doesn't mention the word "passenger" at all, and in fact underscores that there is a no more than one segment chosen by the conductor.

        I can't complain too much, though, as there were plenty of non-Russian competitors that were able to solve this problem, presumably using the English translation. Still, I would enjoy these contests more if for me there would be more actual problem-solving involved and less figuring-out-what-the-problem-is, especially since the problems on CodeForces (once I understand them) are often quite interesting.

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

      Thanks for the clarification! That was not at all clear from the problem statement.

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

The Problem C's description's change waste a lot time of me or someone else...I think today's round should be unrated>_<...

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

    +1 and Orz

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

    ym clj!!! I think the sample 1 is too simple, and it is hard to work out sample 2 by hand.

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

Problems were nice.

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

I think each contestant should be able to decide if their rating is updated for this round.

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

    lolwut? A round should be rated or unrated for ALL. If not our ratings would become inflated and meaningless.

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

      This has been done before. I guess that'll make everyone happy at least.

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

        Neither of them are good reasons to do such thing. I think frank44 is right about the risk of inflating ratings if a vote becomes a habit.

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

    I think it should be unrated for all.

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

Problem D of Div. 2 sucks when k > n.

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

    It really doesn't. While it's a bit of a "silly" case it makes perfect sense. The requirement is that all substrings of length k should be palindromes. Since there are no substrings of length k, all strings pass. It makes perfect logical sense.

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

Many people complained about the not working announcements before. It always says undefined whether it's a hack or announcement. It has been like that for at least 3 round. Could you please fix it.

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

This is another contest where I've run into problems with writing solutions in Python. This time I spent AN HOUR trying to figure out why my solution for C div2 gets TLE. I didn't even care to check other problems because this one was so frustrating. After the contest, when I ran my solution locally, it turned out that on one of testcases in Codeforces environment it took 2000ms, whereas on my machine it took < 700ms. I vote for adjusting the time limits to the runtime performance of languague, in a similar manner as Codechef does. Otherwise there's no sense in allowing to write solutions in Python, knowing that it might fail, even though the same algo would run within limits in C/C++.

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

    Choosing right language is a part of problem solving process.

    I use Python for almost all problems on Codeforces, because it's often much faster to code solution in it (for example, for today's "Quantity of Strings" it has built-in modular exponentiation).

    But for some problems Python is not fast enough, it's OK.

    Also you can use "custom test" functionality to test execution time on the Codeforces server.

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

If there is going to be a voting, then count me for unrated. (I cannot keep refreshing the page , sorry, I have exam tomo.)

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

    Very bad, that it is rated. X-(

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

      How can you make it rated ? Problem B (div1) :: "Any its substring of length k" should have been "**All of** its substring of length k"

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

        Could you elaborate? What's the difference in this context?

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

          "aaaab" satisfies any substring of length 4 which is Palindrome. but does not satisfies "all" substring of length 4, since aaab is not palindrome.

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

            Also, in the case of k > n. behavior is undefined, so it should have been clearly mentioned what to do.

            By behavior being undefined, i mean to say, "any substring of length k", what of you mean by a substring of length 7 in a string of length 2 ?

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

              You should count number of strings under the constraints mentioned in problem statement.

              If k is more than n , we have n^m possible strings.

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

I think contest should be rated for we Div 2 because there was a problem in only E and I dont think it affected more than a 3-4 people ( only 1 person had solved before the updation of the statement at 7:47. So all of the people were doing the other problems then and I dont think anyone starts off with E especially when its 3000 UPD: And yes it is rated

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

What should the output for the following case for problem B (div2) be?

2
2 Alex
12-12-12
99-87-76
2 Mula
22-22-22
99-87-76

My Output is:

If you want to call a taxi, you should call: Alex, Mula.
If you want to order a pizza, you should call: Alex, Mula.
If you want to go to a cafe with a wonderful girl, you should call: Alex, Mula.

System answer is:

If you want to call a taxi, you should call: Mula.
If you want to order a pizza, you should call: Alex, Mula.
If you want to go to a cafe with a wonderful girl, you should call: Alex.

Haven't both Alex and Mula got the same number of phone numbers of each type?

Taxi: Alex 1, Mula 1
Pizza: Alex 0, Mula 0
Girls Alex 1, Mula 1

Can someone please spot the issue with my output. Thanks.

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

    Ok, I figured the issue. Thanks.

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

    Taxi numbers consist of six identical digits. 12-12-12 isn't taxi number, that's your fail

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

    Why? Alex don't has a taxi number, but has "other" number. Both have one pizza number

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

      Yep, I messed up the check for taxi numbers. Thanks.

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

      No. The problem statement says, the numbers of pizza deliveries should necessarily be decreasing sequences of six different digits (for example, 98-73-21) So, 99-87-76 is a call girl number.

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

    This was my challenge. Sorry about that!

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

forever blue

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

    С возвращением =)

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

    Может, стоит сменить ник и аватар?

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

      смени

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

        Я не голубой и не синий(где же Петросян с его намеками?)

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

    Great :D I want that to be in unicode!

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

editorials from the author???

→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Could you please give specific examples of confusing phrases in English statements?

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

    Aw, if you told us when we were preparing our contest months ago with your translation of statements, I would show you some places, we had fixed. But now I even don't remember what were the corrections.

    I think it's good practise to give someone English statements before the contest, so he could fix confusing phrases with you (or with one, who translates statements).

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

      I usually have a look at the corrections applied to my translations after a contest so don't worry, the odds are I didn't miss those ones!

      Your idea is great but first, sharing problem statements before the contest might be against the Codeforces rules and second, I actually do check the phrases that seem confusing to me. What I'd like to know is what the programmers find confusing...

      Incidentally, do you know anybody who translates statements? I know only one linguist apart from me... Thanks for the sound advice!

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

Upsolving the contest after 9 years, still couldn't get what Div. 1 C is asking until I read the comments.

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

    No, I still don't understand what should I calculate.

    → Reply