HolkinPV's blog

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

Hello everybody)

Today is coming regular Codeforces round #163 for Div.2 participants. Traditionally the others can take part out of the competition.

The problems were prepared by authors: Rakhov Artem (RAD), Kudryashov Igor (Igor_Kudryashov), Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating the problems.

UPD: It is decided to use dynamic scoring system. The problems will be sorted from low difficulty to high by authors' opinion.

We wish everyone good luck and high rating)

UPD2: the contest is over, hope you enjoy it)

Congratulations to winners:

1) Aharon

2) marcoskwkm

3) ChaosLogic

4) Imsbuno

5) Conny

UPD3: the editorial can be found here)

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

Comments Comments (93)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

Im first, so i need most of neg votes.

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

last CF round of this month :(

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

    I wouldn't be so sure:)

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

      Considering Petrozavodsk training camp will start shortly — quite probable

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

I wish everyone good luck and high rating too! ;)

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

    u will surely get some positive votes for this :P

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

everyone's waiting for score distribution. wish well for all participants.

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

what do you mean by dynamic scoring system??

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

good luck evryone! :)

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

Ithink some of people from countries expect iran doesnt like iranian people:( becausa they give all iranian people negetive mark!

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

    Don'be so nationalistic-thinking! first of all, that's international community. Secondly, there's no flags around your ava — that's is not the main question! :)

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

almost 2800 Registered participants (including ones who are not in the competition). I think this round is the one having the highest number of participants (counting people registered before contests only). anyway good luck

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

it was a awful contest x(

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

Worst contest ever,

Top 30+ solved only A, B

and guess what?! from top 30+ down to the last ranked contestant, all have solved A, B only!

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

    i think problems are very interesting, but hard.

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

    It is not the worst contest ever! It just too hard to Div2, but problems were realy interesing.

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

      So when the first two problems are fucking easy and the rest three focking hard is normal?:D

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

      I think too. It`s not worst, but for most of Div 2 participants not interesting, because they compete only in speed of coding.

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

      It is not the worst contest ever! It just too hard

      Looks like the very definition of the worst contest (ok, ok, not worst ever, just very bad)

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

Why am I unable to see the pretest values in which my submissions failed? Did i miss something in the newsfeed?

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

    Because the contest is still running

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

      In the last contest I was in, I could see the test cases for which my code fails even while the contest was running.

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

    It is always unable to see pretest values except tests from the problem during the contest.

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

2200 participants during the contest with 0 Successful hacking attempt,system testing will be so fast :)

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

    I saw one around 5th page in standings (althrough that was from Div 1 coder)

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

Congratulations for the contest, the difference between place 1300 and place 100 is less than a 100 points.

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

A-B-E-E-E...

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

    I think that hardest problem was div1 E level.

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

      Not really. Quite straightforward interval tree, but requires some coding. Good for Div 1 D

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

        I don't know how can we multiplicate all numbers by (i-l+1)^k quickly. That numbers are distinct and they are not some good sequence, as for me.

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

          Actually if we calculate for all j up to k, we can then calculate required sum

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

            Would you please explain this problem in more detail?? Thanks!

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

              Let , and . Then (you can do calculations yourself)

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

      I think C, D, E have the correct letters assigned, but for Div 1.

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

Can anyone tell the algorithm for D? Be free to answer in English as well as in Russian

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

    Интересует тот же вопрос. Вначале я просчитывал путь от каждой вершины до каждой Флойдом, затем пытался расположить кафе на всех дорогах наилучшим способом. Сначала тернарником. Работал медленно + ВА10. Потом написал вычисления наилучшего способа вручную. ВА9

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

      Тернарник не работает, потому, что функция не выпукла. Там получается кусочно-линейная функция (зубчатая). Я думаю, что мое решение достаточно понятно для чтения

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

        Ясно, спасибо

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

Traditionally authors wish Successful Hacks .. Is this the first round I am seeing with no successful hacks ??

Hats off to the author for problem C. Looks so interesting and yet is so difficult to think.

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

Unexpected difficulty level was unexpected.

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

    yeah! from rank 200 to 2000, all of them solved 2 problems and they have been sorted by their typing speed!

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

actually in problem C we just need to sort all rows as increasing amount of 1's and sort the columns as increasing amount of 1's

note that sorting columns won't change any thing in rows and vise versa

so we don't need more than 2000 move

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

    I missed a really important constraint no of cells having ones are no more than n — 1. :(

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

    Sigh, I missed the second part...

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

    Actually you can not sort in O(n) time , you have to also tell the positions which were swapped. For the second part , you can sort by any trivial algorithm for sorting in O(n*n). Note that I was missing one important thing , No of ones in columns won't change if I swap the rows. So I can just count no of ones in columns also and do the same thing as done to rows.

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

    i think we don't need more than n-1 moves.

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

      do not be so accurate!

      I only wanted to show that sorting won't exceed the limit 10^5

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    • 00000
    • 00010
    • 00100
    • 01000
    • 10000

    it has been sorted, but it's not a correct answer.

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

      You have to take care of equal case , If equal then do the sort lexicographically decreasing.

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

Why ternary search is incorrect in D?

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

    Read above Egor's comment

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

    Because function within edge is not convex. It is segment-linear, with segments alternating y = x + b and y = -x + b

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

      Please explain the second part y = x + b and y = -x + b ??

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

        Function for each edge is segment-linear (i. e. edge can be divided into segments, and on each segment function would be linear). Generally linear function is y = kx + b, but in this case k is always either 1 or -1, and this values alternate throught edge

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

I think these div2-only contests are not really for div2 participants, only. I mean, they're more likely generic ICPC contests, with very easy problems and very hard problems. The final scoreboard today clearly shows that problems C,D and E are not equivalent to div1-A,B and C, as they usually are in regular, div1&2, 7-problems contest. For instance, problem D, that should be equivalent to a div1-B, was solved by 8 coders only — 6 of them were div1, out-of-competition ones. Although we know most div1 coders don't register for div2-only contests, we won't see only 6 coders solving problem B in a regular contest. So I think these div2-only contests are not really equivalent to div2 regular contests. Should they be?

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

edited

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

Same codes?

http://codeforces.net/contest/266/submission/2992482 http://codeforces.net/contest/266/submission/2989351

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

请使用英语。

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

How long does it usually take for ratings to update?

It's a matter of high blood sugar, or rather it's gonna be.

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

I think this contest is really a coding speed test for div 2 participants. I finished the first two problems less than 10 minutes. After that, I read the description of problem E. At the first glance, I thought it had something to do with segment tree. However, right after looking at the sigma notation, I just gave up. I played 2 games of League of Legends.

And surprisingly my rating still increased after the contest.

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

    And i played 2 games of Dota :D

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

Could anyone tells me, why dis the problem D can not use Ternary Search Algorithm ? I alawys get wrong answer on test 36 ! Many thanks ! this is my

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

    my code links : http://codeforces.net/contest/266/submission/2993280

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

    You should read egor's comment.

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

    You should divide each edge into several segments, and use ternary search on every segment. Just like what Egor have mentioned above. And you can also see more details in my submission. 2995464

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

      No need for ternary search, actually

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

        Yes, you are right. I found the function within each segment is unimodal, so I used ternary search to find extreme points, but I did not realize that it is possible to get extreme values by direct calculation. Thank you so much. I will correct my solution.

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

There is a grammar mistake in problem C. Some cells (n - 1 cells in total) of the the matrix are filled with ones, the remaining cells are filled with zeros. We can apply the following operations to the matrix:

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

please give me some hint about problem D ?

→ Reply