HolkinPV's blog

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

Good day!

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

Problems are prepared by Kholkin Pavel (HolkinPV), Rakhov Artem (RAD) and Nikolay Kuznetsov (NALP). Also thanks to Michael Mirzayanov (MikeMirzayanov) for perfect system, Mary Belova (Delinur) for translating problems and Agapov Gerald (Gerald) and Alexander Kouprin (Alex_KPR) for their help.

We decide to tell you some secret about todays problems. To solve them, you wiil propably use sort algorithm)

Score distribution is standard: 500, 1000, 1500, 2000, 2500.

We wish you success and high rating!

UPD: The contest is over, the tutorial will be here soon.

UPD2: Thanks everyone for participation. We hope you enjoy your problems. Congratulations to the winners:

  1. Touma_Kazusa
  2. ZJUT_AA
  3. wwhd
  4. jikwao425
  5. wtiger9999
  6. Jolin
  7. anmtcel
  8. marspeople
  9. ztxz16
  10. CrazyRabbit

Special congratulation to Touma_Kazusa, who solves all problems of the round.

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

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

it's not a good idea to say how can we solve problems

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

    but it's interesting :)

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

      oh, really? is it interesting to know what is the algorithm? :D

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

        It isn't the entire algorithm, we just know that we have to use sort in the final answer. But it's better to find oneself... It's a too big hint, and all the contestants who have seen this post will be advantaged.

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

Just curious to know why the site has not gone to safe mode today ...Its only 25 mins remaining and in some recent rounds the site went to safe mode some 1 hour back

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

Someone has published problems D (id DOR17) and E (id DOR16) on SPOJ during the contest. Lame way of cheating...

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

    Someone has no respect for authors and steals your problems. This person doesn't know anything about copyrights. We try your best to do the contest. That's why we shouldn't comment this ugly behavior.

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

    I have just received an email from SPOJ. The problems were removed and the user got banned.

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

I feel very stupid right know... what was the issue with pretest 3 of problem C?

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

    4 k
    1 1 1 2

    Something like that

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

      Of course... facepalm

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

      So, what's the trick of duplicate numbers ?

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

        If there no equal numbers it's ok and work — k/n and k%n

        Let's look at

        3
        1 1 2
        (1,1)(1,1)(1,1)(1,1)(1,2)(1,2)(2,1)(2,1)(2,2)

        So k/n and k%n will print wrong answer —
        k=5
        Your answer = 1 1
        Right answer = 1 2
        P.S Sorry for my english :D

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

          Thanks a lot. I made a fool of myself :(

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

            Don't worry. If you look at the submissions you will see that a very large number of people made this mistake (including me). I think it's naturally to forget about the impact of duplicates initially.

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

              the statement seems to emphasize the duplicate situation twice, but i just ignored it... 3ks for the explanation!

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

              You're right. So many users were stuck in C. After 220th ranks in final standing, so many minus numbers are on C.

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

          I know the trick, can you tell me the right solution?

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

            Still right that first number is — a[k / n]. And second is a[(k–n·cnt) / num], where cnt – count of numbers in array that < than a[k / n] and num – count of numbers in array that = a[k / n].
            It was written in russian editorial, i just translate it ( hope right =) )

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

      what are the possible pairs for ur testcase?

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

        (1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,2)(1,2)(1,2)(2,1)(2,1)(2,1)(2,2)

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

it would be so interesting if we could see our final rank now ;)

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

Ahh

its my first time for entering the contest..

its very interesting :)

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

my submittion of problem A is kinda stuck it says accepted on final test but

where is question mark on it says waiting or judging. http://codeforces.net/contest/160/submission/1296903 what's wrong with it?

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

    it seems accept right now:)

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

      yes it says accepted but in contest rating it says waiting or judging :(

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

        just be patient , everything will be fine after the judging for whole contest:)

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

A,B,C explanations

Any idea about problem D?

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

is segment tree should be used in problem E?

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

    It is solvable by using binary-indexed tree (Fenwick Tree).

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

      i should learn it ... thanks for the important hint! :)

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

Why is the system testing stuck on 100% from the last 10 mins.I want to check my C solution ..

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

Maybe it will be better to make such rounds not only for div2 but for mixed div1 and div2, because I think D and E were good enough for div1.

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

is there failed pretest or re-submission penalty from this round ? I saw the statement about this penalty during contest, but I think I did not receive penalty at my final score.

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

Can anyone explain why this submission (1304142) for C timed out? It works in O(n) time, I simply rad the array, count the occurencies of numbers using HashMap and then iterate at most n times. I see no way to fail it on timelimit... The only possibly slow operation is adding elements to map, but on other tests with maximum n, it worked in around 100ms. Where's the problem?

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

    Well, I submited the exactly same sulution again and it failed on another test, which run in 130ms before. I don't get it, where's the pitfall? Something in HashMap?

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

      They are antiquicksort tests. Shuffle the array after reading and get AC.

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

        Well, it passed with Integer[] instead of int[]. I think this is the most stupid thing I ever saw on programming contest. I see no point in not letting pass the solution with the correct idea and implementation... Just because of testcase challenging in fact Arrays.sort method of Java authors, not my code. What will be next, tests concentrating on possible bugs in GCC compiler? I probably should start coding in Turing machine instructions in next round.

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

          tests concentrating on possible bugs in GCC compiler?

          Actually, there are a lot of cool stories of unsuccessfull hacks/TC challenges with correct output from function that returns correct value despite having no return statement inside.

          We should never believe a compiler and runtime library. C'est la vie

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

            Yes, I fully understand this, in fact, I'm glad in some way that I have learned today about a pitfall in commonly used part of standard library. But there's a difference between non-defined behaviour of C/C++ and "abusing" a weak spot by carefully chosen input. In first case, a challenger/systemtester is in disadvantage and knows his attempt can fail. If he will succeed, a code with a bug will be identified and will gain zero points. He's aware about the risk, it's a lottery. In second case, it's about choosing a very special case that timeouts in fact correct solution. A coder who got a correct idea and implemented it will gain zero points. I see a clear difference between these cases. But, however, both of them are following rules and there's no one to blame. But it's questionable if the second one is fair. But yes, there's no "guilty", just a "victim". So the victim will write slightly angry comment after the contest and life moves on :)

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

It makes absolutely no sense that I failed C with an O(n log n) algorithm just bcoz I coded in Java. This gives no chance at all for Java coders. All I did was to sort and proceed like every other AC algorithm.

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

    It seems you have the same problem that I have. The strange thing is my solution once passed test 66 in 130ms and then it didn't make it in one second. Maybe some problem with system tester?

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

    may be it was AntiQuickSort test?

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

      What does that mean ?

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

        as I understood from previous posts Java Arrays.sort uses quicksort, which can be hacked with special generated test which causes Arrays.sort to do O(N^2) operations.

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

      AFAIK, Java implements using dual pivot quick sort which is faster than normal quick sort.

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

        Any quick sort impelementation with determinate algotrithm of choosing element for partition can be failed to O(N^2) time. Java implementation too.

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

          It seems you are right. What I did now is to push all elements in a priority queue and then pop them all and it was AC. I never thought that the built in sort would time out, never met that idea in a contest.

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

            More easy is to shuffle data before sorting. But i don't think simeting like this will hapen often on codeforecs. It's not very sporting behavior.

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

              Is shuffle is determined too? If so, it's possible to antiQuickSortAfterShuffleTest

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

      AFAIK Java use mergesort not quicksort for sorting.

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

    There are many AC Java solutions. There are even Ruby AC solutions for that problem

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

    quicksort IS NOT N LOG N. it's o(n^2)

    and o(n log n) on random test

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

I have a question concerning problem statement of 160D - Ребра в MST. It says:

You are given a connected weighted undirected graph without any loops and multiple edges.

But in the first sample there is a loop: 1->2->3->1 Is the statement wrong or am I missing something?

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

can someone tell me one reason about why problem C time constrain is 1 second !!!!!!!!!! it's just totally nonsense , the wrong Algorithm will just fail the 2 sec time !!! my solution is O(n logn) and it failed in java but Acc in C++

THANKS !

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

    When I saw the non-standard time limit I thought that they probably put it there to prevent anybody from attempting to solve that by brute force (i.e. creating all possible pairs, sorting them and then selecting the k-th one).

    However I agree that Java coders had a significant disadvantage here because of the Anti-Quicksort tests (I got lucky with Ruby I suppose). I agree that coders should think about worst-case complexity which is O(n^2) for Quicksort but if so this should affect all implementations and not just the ones in a single language.

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

      you couldn't create all the pairs. they could be 10^10 in number!

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

      the O(n^2) solution will fail in both memory and time, which makes the 1 sec limit completely ridiculous.

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

        Yes, but that does not mean that the problem isn't solvable in 1 second using Java. As mentioned in previous comments you need to shuffle the data before sorting to avoid the worst-case performance of Java's sorting algorithm.

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

          true but this not the point,the problem is having same Algorithm that passes in one language and not on the other , and this isn't right in an Algorithm competition , specially if the difference very small.

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

            I failed the problem due to anti-quicksort test too. But I think it was a lesson well learned.

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

This is the first time I do in codeforces environment. So I'm sorry if this is an already known issue, but in problem C, using C++, reading a long long integer from std::cin isn't really operated, while on my local machine with gcc 4.2.1 does. I was struggling against this for an hour and found that using scanf("%I64d", &longint) only solves this.

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

    I just took a look at your submissions and realized the problem is that you declared k as int, not long long.

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

What a pity!The school network was broken at 23:30 and i could not finish the task...and my rating has decreased a lot. :-( TT

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

what pears do we have on this test?

3 3

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

    1 1

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

      and why ? all pears are ~~~~~ (1,1),(1,2),(2,1),(2,2) ~~~~~

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

        try to read all comments before asking questions like this

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

        there is n^2 pairs ;-) (sometimes I miss similar conditions, so I perfectly understand...)

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

is there anyone can tell me why i got WA on this submission? (http://codeforces.net/contest/160/submission/1299317) i tested on my computer and got a right answer. (15 lines of ‘at least one’)

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

    Look carefully and don't be confused between your output and the answer. It must be 1 "any" + 14 "at least one".

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

Does who MLE on D? Help me please.

→ Reply