HolkinPV's blog

Codeforces Round #117 (Div. 2)
By HolkinPV, 13 years ago, translation, In English

Welcome friends)

We are glad to introduce you regular Codeforces round #117 for Div.2 participants. Everyone can traditionally participate in it.

Problems are prepared by command of authors: Pavel Kholkin (HolkinPV), Ivan Fefer (Fefer_Ivan), Nikolay Kuznetsov (NALP) and Gerald Agapov (Gerald). Thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating problems.

And again score distribution will be dynamic) More information you can find here.

Note that all problems today will be given in random order.

Some Div.1 participants register for the contest before settings of registration were changed. Before the round it will be fixed and they will participate out of competition.

We hope that todays round would be succesful and everyone enjoys it. We wish you good luck and high rating!

UPD: the statement for problem 182E - Wooden Fence was formulated incorrect, correct variant of the statement will be soon, we apologize to the participants.

UPD2: the contest is declared unrated.

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

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

And are there dynamic problem max scores used?

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

    And again score distribution will be dynamic) More information you can find here.

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

      Hm, that's nice, but I asked before it was written in post. HolkinPV updated the post later (I can't delete my comment)...

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

502 Bad Gateway...Please allow me to enter

UPD:Oops...Did not realize that we have been given 10 more minutes to get ready :)

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

Problem A will be the easiest one as the first dynamic contest ?

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

    No

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

      Yes. With probability 1/5.

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

    Note that all problems today will be given in random order.

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

    No, "Note that all problems today will be given in random order." ;-)

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

07:00 PM (Moscow Time), is the ideal time for a programming contest, please to keep this schedule for the future competitions.

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

Unable to ask questions. Getting "Field should not contain more than 1,000 characters" when the question is much shorter than that.

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

    Maybe you have some copy-paste from HTML. And HTML source of your question exceeded 1000?

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

      I did not copy paste the question initially, I just typed it in the box. I also tried using the "Remove formatting" option.

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

Unsuccessful challenge on problem E:

Input: 2 4

1 3

1 3

Output: 4

Answer: 4

How the answer is 4? It should be 2.

1) #1, rev#2

2) #2, rev#1

I asked a lot of questions during contest and got answers that for example (#1, rev#2) and (rev#1, #2) are same variants. In that case the answer should be 2 for the case above.

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

    I think answer is 4,not 2. You get 2 combinations putting type 1 first, and 2 putting type 2 first.

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

      According to the problem description 2 out of those 4 variants are the same.

      P.S. I even asked a question to jury by specifying exactly such 4 variants, and got a response that 2 of them are duplicate.

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

    i think that they assumed that a rotation is considered as new type

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

In problem E.
What is the answer for the input (2 3 1 2 1 2) ?
There are 4 sequence of fences.
seq0 : fence[0] -> turn(fence[1]).
seq1 : turn(fence[0]) -> fence[1].
seq2 : fence[1] -> turn(fence[0]).
seq3 : turn(fence[1]) -> fence[0].
But seq0 and seq1 are same, And seq2 and seq3 are same too.
So I think it is 2.
But if so, the answer for sample3 is 18 not 20.

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

    Same issue for me :) Spent 1 hour on discussions with jury

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

    I'm surprising when my not-finished solution passed examples(as well as the pre-tests). That is the same question. The admin's reply is just:

    "I can only say, that rotation of the board does NOT change its type. So sequences with same boards but with different rotations are same."

    So I don't know what is wrong: the standard solution, the statement or my understanding?

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

Problem C: Many people have wrong answer with pretest #15 (include me). Good pretest :D

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

[upd: sorry for asking the same questions other people already did. I typed the question at the same time.]

I have a question about problem E. Consider this test case: 2 3 1 2 1 2 Considering that "Two fences shall be considered the same if the corresponding sequences of fence boards' types are the same", I think the answer should be 2 — a fence with board types A and B ((1,2),(2,1)) and another with types B and A (also ((1,2),(2,1))), where A and B are the two given types of fences. ((2,1),(1,2)) would be equal to one of these solutions, since only the type (and not the rotations) are considered during comparation.

However, according to an unsucefull hack attempt, the answer is 4. I asked it during the contest, and they said that a fence with types (A,B,A) and (B,A,B) is also valid, but I can't figure out how it's possible with fence lenght 3... Can somebody? Thanks!

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

    If we called the first block A (1,3) and the second block B (1,3) The 4 valid fences are : (A , rev_B) , (B , rev_A) , (rev_A , B) , (rev_B , A)

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

      (B rev_B) and (rev_B B) are not allowed:

      there are no two successive boards of the same type

      Update: the upper comment has been changed. See reiracofage's comment below.

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

      But "A, rev_B" is equal to "rev_A, B" according the statment...

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

I took a look at the last example case and “deduced” that rotation also matters in the sequence comparison… I was getting WA locally for a long time, because that was not so clear from the problem statement, but I finally got it when there were about 10-15 minutes left; otherwise, I could have gotten C I think, using BIT :(

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

Does anybody know the solution to the Problem C? I try to use the Red Black Tree, but my answer is wrong..

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

on a separate note, why isn't the system test starting?? [NOTE: I said this at the time when the blog did not contain the update; don't get this wrong :)]

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

    There is a mistake in author's solution for problem E. Now authors are trying to fix it.

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

      would that mean the problem would get invalidated? the last example case would not be reconcilable... if the statement is wrong/example case is wrong, IT SHOULD HAVE BEEN ANNOUNCED during the contest. I took it as a case where the statement is wrong AND the example case is right...

      I think trying to fix the solution retroactively won't really work.

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

        This will be another unrated round now i think.

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

          let's see what the admins say about this.

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

      I think there is no mistake, just a problem is missing something like: Two fences shall be considered the same if the corresponding sequences of fence boards' types and dimensions are the same.

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

        Too much thinking :) Your version and the initial one are different problems. Let's just wait the officials. Don't overthink.

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

        I think missing something is also a mistake. I spend some time thinking and coding another method, and found I get WA on sample 3.

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

          yea, I had to change my solution assuming something not stated within the problem statement, so as to fit the example test case (I thought something was missing in the statement but moved on, being under a time pressure) ;P

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

          I didn't have any idea to count different types of board sequence. Can you share your code ?

          you should get 18, on third sample.

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

            Got the same answer. I wrote recursive DP with some hashes, comparing them at the end of recursion.

            UPD: My Code here:

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

            Usual dynamic programming, but as it will count duplicate cases also (like the ones on which author solutions are wrong) there is a way to count the number of these duplicate sequences separately and then subtract from original answer. To calculate duplicate cases, you need to consider the quantities of equal boards with different types, for example if there are K boards with the same size A x B and if required length is divisible by (A + B), then there are K * (K-1) * (K-1) * ... * (K-1) duplicates ((K-1) is repeated (length / (A+B)) * 2 — 1 times).

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

              I`m not sure your solution be correct. there is a lot of possible paths (to build a fence), that have same sequence types with different width and length. I meant your solution doesn't count all paths.

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

                Show example in that case.

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

              I have a close idea with yours during the contest. But I think the subtract method you mention works only for A[i]!=B[i]. If A[i]==B[i], you should have a different subtract method or deal with it when dynamic programming.

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

                I have excluded A[i] == B[i] during dynamic programming, you can just check if A[i] == B[i] then don't consider the variant when the board is rotated.

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

        There is a bug in authors solution to problem E...Read the blog again...Its updated...I think this round is going to be unrated :(

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

          I respect your opinion but I think that should be rated for div 2 because several people made a big effort to solve other exercises, including me. Thanks.

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

system testing is in progress... what's admins final decision?

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

    See blog above: UPD2: the contest is declared unrated.

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

I didn't consider to types of board, just i checked rotation of square board with same type shouldn't count twice, and got Accepted! I think something is wrong yet.

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

My comment was wrong, sorry...

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

    Right, you suddenly decided that your comment became wrong the moment it got downvoted a lot :)

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

Whats case 15 in Problem C?

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

    Try this smaller test cases:

    7 6 
-4 2 -2 -4 0 3 5 
2

    out 16

    7 2 
5 1 -3 -4 -1 -5 1 
1

    out 7

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

spending my time from 22.00 — 02.00 waiting the systest while I have mid test in the next day and the contest end with unrated. . what a pitty. .

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

Comment deleted after a bit of thought, for more details read my reply 2 branches down this comment :)

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

    Oh seriously, how the hell is that anywhere near a trivial question or a "bad contribution to the community" that it gets downvoted?

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

      Is it a good contribution or a non-trivial question, really? :-)

      On a serious note, the editorial is already published here, it's just not translated into English yet. Most problem setters on Codeforces are Russian-speaking, so translating editorials takes longer than writing them, and it's a lot of work. Have patience.

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

        Yeah, thanks Nickolas. I'm not trying to justify my comment or anything; but I was frustrated about my bad performance yesterday :) To tell you the truth, I think I don't actually care about the editorial, I just wanted something to complain about. Sorry and thanks again!

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

    There is russian one

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

How did so many manage to solve E during the competition? It only passes if you make the same mistakes as the author; the answer to the first test case should be 3 since the second board lying down is a beautiful fence as well. You can see on the second test case that just having one board is okay.

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

Very old blog, but incase someone is stuck on problem C like I was, the idea is to maintain a set of K maximums using two sets.

→ Reply