Автор tourist, 8 лет назад, По-русски

Всем привет!

Третий, он же последний отборочный, раунд VK Cup 2017 начнётся 7 мая в 18:35 по московскому времени (время в вашем часовом поясе). Параллельно с ним на тех же задачах состоится Codeforces Round #412 для обоих дивизионов. Все три раунда будут длиться три часа и будут рейтинговыми.

Соревнование "VK Cup 2017 — Раунд 3" предназначено для команд, квалифицировавшихся из Раунда 2 или Уайлд-кард раунда 2. Лучшие 20 команд пройдут в финал, который состоится в июле 2017 года в Санкт-Петербурге!

Большое спасибо KAN, qwerty787788, PavelKunyavskiy, AlexFetisov, MikeMirzayanov и компании ВКонтакте за то, что этот раунд стал возможен.

Главным героем большинства задач станет платформа Codeforces. Не забывайте, что читать условия всех задач бывает полезно.

Удачи!

Поскольку на дворе 2017 год, разбалловка, безусловно, будет статической. Точные стоимости задач будут объявлены перед раундом.

UPD 1. Стоимости задач:

Div. 1 и VK Cup Round 3: 500 — 1000 — 1750 — 2500 — 2750 — 3500

Div. 2: 500 — 1000 — 1500 — 2000 — 2750 — 3500

UPD 2. Из-за вчерашних проблем с регистрацией на контест начало раунда отложено на 10 минут.

UPD 3. Поздравляем победителей!

VK Cup Round 3:

  1. zemen, Zlobober
  2. V--o_o--V, LHiC
  3. RomaWhite, witua
  4. YakutovDmitriy, budalnik
  5. Golovanov399, -imc-

Div. 1:

  1. Petr
  2. yosupo
  3. rng_58
  4. uwi
  5. Nezzar

Div. 2:

  1. ltaravilse
  2. btk15049
  3. RCG
  4. SUSTechDFS
  5. hieutrungle

UPD 4. Доступен разбор задач.

  • Проголосовать: нравится
  • +2247
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +1009 Проголосовать: не нравится

My first reaction to round author:

»
8 лет назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

What does this mean "maybe someone else"?

»
8 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

How many problems there will be ?

»
8 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Поскольку на дворе 2017 год, разбалловка, безусловно, будет статической. Динамическая разбалловка — моветон в 2017?)

»
8 лет назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится

Boss(tourist) is back in business after a long time .

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -73 Проголосовать: не нравится

БЕМ-БЕМ-БЕМ батя в здание(я про "tourist" )

»
8 лет назад, # |
  Проголосовать: нравится +87 Проголосовать: не нравится

Не дает зарегистрироваться на раунд командой, хотя мы попали в 20 на вайлдкарде.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +51 Проголосовать: не нравится

    Удваиваю, а ещё в списке зарегистрировавшихся нет команд

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    Разбираемся, скоро все будет.

»
8 лет назад, # |
  Проголосовать: нравится +77 Проголосовать: не нравится

Image and video hosting by TinyPic

Why can I register for both contests at the same time?

»
8 лет назад, # |
  Проголосовать: нравится +146 Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +738 Проголосовать: не нравится

I'll go to a trip the day after tomorrow (i.e., get up early) and I was planning to skip this round (it's late night), but the writer is tourist. I must change the sleeping schedule.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

STATIC scoring!

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится +87 Проголосовать: не нравится

What does this mean ?!

UPD: Fixed :)

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится +9 Проголосовать: не нравится

Poor connection :( I'm so sorry for repeating the comment. (edited)

»
8 лет назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

is there a qualification required to participate in the div2 and div1 rounds? , because it says "Registration is private" ... thank you

»
8 лет назад, # |
  Проголосовать: нравится +268 Проголосовать: не нравится

DIV 2 people right now

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится -16 Проголосовать: не нравится

I hope Statement.CLEAR && Statement.SHORT() always return true! :)

Good luck everyone!

»
8 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Register again, to take part in contest.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

The round writer is tourist . Do not miss the round!

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Ну вот раунд с матчом Арсенал-Манчестер совподает. Жаль, что не буду.... Не буду смотреть футбол...!!!

»
8 лет назад, # |
Rev. 5   Проголосовать: нравится -53 Проголосовать: не нравится

...

»
8 лет назад, # |
  Проголосовать: нравится +618 Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

I can break negative contribution record with this comment down votes coming

»
8 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Boss(tourist) is back in business after a long time .Yeah.

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

what does it mean that the score will be static?

»
8 лет назад, # |
  Проголосовать: нравится +78 Проголосовать: не нравится

If you want to be "Tourist" , Please visit my country Nepal. Very Beautiful and We welcome Tourists :P

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Into my mind the problems will be very interesting(and soulves too).

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Геннадий, видимо, решил, что если он не может поучаствовать в контесте (как и во всем чемпионате из-за участия в финале два года подряд), то непременно должен стать его автором.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Топ 10 по вкладу. Хайпанем немножечко?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -16 Проголосовать: не нравится

    Ну блиин, я думал, что нормальные люди его не смотрят. Я разочарован :)

»
8 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Why everyone so excited that the round is by tourist?! it doesn't mean that you participate a round by tourist and you become tourist also :P Go to visit somewhere and do the contest, you'll become a tourist participant of a contest by tourist!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I really hope that tourist could say hello to me.I would be happy all the night,maybe all the year.

»
8 лет назад, # |
  Проголосовать: нравится -35 Проголосовать: не нравится

I am Arab :| downvotes please

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    something else, do you have problems with Arabs, because of you people hate Arabs and Afghans, please don't do this "Stupid acts".

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -48 Проголосовать: не нравится

    You've got it wrong. People usually hate jews, but not arabs =)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      In fact people here hate ethnicity-related comments most of all, I think.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        so why no downvotes¿

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +49 Проголосовать: не нравится
          Spoiler
»
8 лет назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

Слава Україні!

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Ow I think I can do it this time with this comment: is it rated? GL & HF How many problems there are? Hope for short statements anything missing? please write phrases I should write in this comment

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Story of tourist and problems :

»
8 лет назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

Finally a round that tourist cannot take the first place :)

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

I have End-Semester exam tommorow. Well fuck it.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

More delays?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Rating? Or spend the semester? :'v

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Delayed by 10 min

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Delay, delay everywhere

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

Guys instead of fun I want you talk with you. Today I did this with an account to show you in life they are some people like this _VanGogh_ this people can be so bad for our duty. look, one of the codeforces best blogs ever can be hardly damned with people like this please, please I'm not joking please read this comment and try to remember it, there are many people like this in the real world don't make sense about them and let them for their own! at last be happy and I wish you all a good contest :) Sorry for my poor english :(

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -29 Проголосовать: не нравится

I hate delayed contest :(

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

delay, hope it won't be delay as much as 411

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Now 10 minutes late is a common factor of codeforces contest.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

There is nothing I hate in codeforces more than the delays xD

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Delays for situations like this (yesterday's registration) should be announced a day earlier when the registration failure happens, not 5 minutes before contest start.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I'm the only one that use delays to give contribution points??? I'm nervous, I hope to solve at least three problems...

»
8 лет назад, # |
Rev. 7   Проголосовать: нравится +23 Проголосовать: не нравится

after hearing the contest is on Sunday:

After hearing it is from tourist:

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +31 Проголосовать: не нравится

That's why I love problems of tourist:

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

What if I hate Math! xD xD

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Fairly difficult contest but great problems by a great problemsetter!

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What is test 10 for problem Div2 E? It's driving me insane.

»
8 лет назад, # |
  Проголосовать: нравится +138 Проголосовать: не нравится

There's definitely something wrong with problem B, I'm sure that my solution is correct but I kept getting wrong answer. Here's my idea, please correct me if I'm wrong: Only tourist can beat Petya, so I printed -1 for all test cases.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In DIV2D/DIV1B, does anybody have an idea, what test case 11 could've been like? Kept failing it.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I got WA once on test 11 with binary search.

    A linear scan got pretest passed.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

      binary search doesnt work always. Take case something like vasya cannot solve some problem and petya can solve it.then u are increasing its points

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes. I forgot the fact that if i can't have a correct solution for a particular problem, adding new accounts would increase the difference between two's score.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I literally just bruteforced my way until some large enough threshold, say 1e6. Since the original number of participants is quite small (<= 120)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Could you give me an example case that make binary search goes wrong? My idea is binary searching the answer and then using current "fake accounts" i use bitmask for every problem. 0 in the mask represents that all fake accounts must produce "failed submission", 1 in the mask that all fake accounts must produce "accepted". Firstly i check if there is any problem that Vasya hasn't solved yet, the fake account cannot produce the correct answer and move to the next mask. In any mask configuration that makes Vasya score gets higher than Petya, then current answer is able to make the score higher. Mine got WA on pretest 11

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What do you mean by linear scan?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        for i:=0 to a specific value check adding i accounts submitting solutions in an optimal way satisfies the requirement or not

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Damn. I did it with binary search, because I though a linear function would be too slow.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Got WA on pretest 12 (not 11) with a greedy solution

»
8 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Why points in scoreboard changed?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hack case for Div2.C?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

how to solve div2 problem D? Can anyone please help

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div2C?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    About binary search or math to solve it.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    binary search

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    Simple math, no need binary search (maybe will fail from systest):

    Code

    Got AC :)

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Firstly, divide p and q by gcd(p, q), next step is binary search parameter m, and check that we can make fraction N / m * q from x / y.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Solved it using math. we must find n and m integers, n, m >= 0 such as: (x + n) / (x + n + m) = p / q; => n = (p * m + p * x + q * x) / (q — p); and m = (n * q — n * p — p * y + q * x) / p; m = (n * q + q * x) / p — n — y; m = q * (n + x) / p — n — y; Because gcd(q, p) = 1 => n + x = cp, c integer, c >= 0, c minimum so n = cp — x; because n >= 0 => q * (n + x) / p >= n + y so: c >= (y — x) / (q — p) => c = ceil( (y — x) / (q — p) ) Notice that n = cp — x, so if cp — x < 0, we have a contradiction. Finally, c = max(c, ceil(x / p)); we calculate n and then m; we print n + m. be careful with border cases

  • »
    »
    8 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    See the comment at the top of my solution: http://codeforces.me/contest/806/submission/26929314

    1. least k s.t. kq >= y && x <= kp && kp <= x+(kq-y)
    2. k >= y/q
    3. k >= p/x
    4. k*(q-p) >= y-x
    5. k >= (y-x)/(q-p)
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you, please, add a bit more detail to the following transition:

      1. "min b s.t. (x+a)*q == p*(y+b) 0 <= a <= b"
      2. "least k s.t. kq >= y && x <= kp && kp <= x+(kq-y)"

      I don't understand how do we go from step 1 to step 2.

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        This reformulation is the crux of the problem, at least for me. I didn't think of it this way while solvingh; I wrote down #1, didn't think it was useful, decided I had to find k, and tried to write down conditions that would make a given k a valid solution.

        However, they are equivalent:

        kq-y is b, so the condition kq >= y is just saying b is non-negative.

        kp-x is a, so kp>=x is saying a is non-negative.

        And kp <= x+(kq-y) is saying a <= b.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is test 7 about DIV.2 problem B?

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve div2 C??? :/

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why I can't see others' solutions?

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится -20 Проголосовать: не нравится

For Div2 C, got WA on test pretest 4. What's wrong in my code? 26944035

»
8 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Fastest start of System Testing this year :o

»
8 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Understanding question div 2 B is harder than solving it

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div.1 D? It is correct that we should find exactly one path with cost X and length K to the some vertex U, and choose min(X + minEdge[U] * (n — K)) over all pathes K, U? How to manage this?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

    Let's fix the root u. What we want to find is actually a path from u to some vertex with minimal weight edge attached to it.

    Consider sorting the edges and add them one by one, let's say we're adding e(u,v), do we know the shortest path from u to some vertex with minimal weight, using this edge?

    We do indeed! it's equal to the weight of the edge, added by the result of vertex v. Notice that if we don't have result of vertex v, we notice that all the "empty" edges have same weight as the edge we just added, so it's weight * 2. Doing it for all edges and you get the answer.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Problem C [Success Rate]: Case 3 3 5 5 is the answer 0 or 2 ?

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

What an end for a contest by tourist. Petr wins it with a submission in last minute.!!!

»
8 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

what should the answer to problem div 2C be for the following output x=0 y=2 p=0 q=3 ?

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Nice Contest and questions were also interesting. Thanks tourist!!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

that moment when you got everything in div2D except that you had to do linear search not binary search and the limit would never rich 1e9+7 ...

»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

one of the team was "-xray- is gay". And the members are -xray-'s teammates. lol .

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is O(n^3) supposed to get TLE for problem Div2F?

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

3 задача была легкой только вот я незнаю как решать деофантовое уравнения (

»
8 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

Boss(tourist) is back, that's why we have a nice round. :)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain mathematical solution of Div1 A / Div2 C ?
Petr's one http://codeforces.me/contest/806/submission/26927108

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Find smallest integer t such that 0 <= p*t-x <= q*t-y. Submit q*t-y times and get AC p*t-x times then AC rate wil be p*t/q*t = p/q.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Petr has started doing screencasts with commentary, so probably we will be able to see his thoughts while he was solving this problem.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      I think he stopped doing it, as according to him it affects his thinking ability :(

»
8 лет назад, # |
  Проголосовать: нравится -38 Проголосовать: не нравится

эх а почему мы бы не обойтись без систем проверки ? а сразу все тесты впихнуть ? ну тем кому интересны хаки то могут на Эдакейшинл раунде

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

The most upvoted blog ever on CodeForces!

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

I just want to know, Am I the only one who spent more than 1 hour to understand Div.2 B? :D

»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Very nice round and well-written problems..... on a completely different topic : is there any problem with sharing the rating changes ? i can't see the usual buttons i.e: facebook , twitter ... and thanks again.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in Div2 C this test case" 2 8 8 32 " output 24 and it should be 0 and the code still AC why ???

»
8 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

why all my sloved skipped...

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    It means your solution resembles another's too closely, so either you cheated or you're pretty unlucky.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    MikeMirzayanov and the entire codeforces community hates cheaters.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Editorial? Nice set by the way

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For 1E, does the following logic work?

If the question just had 1 query for the case of n people, then we simply sort all of them by their estimated rating in ascending order and simulate.

In a different line of thought, consider a fixed arrangement of people visiting the blog. Changing somebody's vote downwards (ie. making him downvote) will never increase the final rating of the blog.

Suppose x people downvote the blog, y people don't vote and z people upvote it in the optimal arrangement. Then, there is an arrangement where we arrange the people in increasing order of estimated rating, enforce that the first x downvote the blog, the next y people don't vote, and the last z upvote the blog. Then this enforcement does not make anybody rate the blog better than usual, implying that the final rating is possible.

Furthermore, if y>=2 people don't vote, this is equivalent to forcing the first of the y people to downvote and letting the last of them upvote, so we may assume y<2.

This means that given a target rating, we can find out x, y and z required. Hence, we may binary search on the score. Queries are equivalent to asking whether the i-th largest element is greater than C-i for i<=k, for some constants C and k. This can be maintained using a modified balanced binary search tree.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Suppose x people downvote the blog, y people don't vote and z people upvote it in the optimal arrangement. Then, there is an arrangement where we arrange the people in increasing order of estimated rating, enforce that the first x downvote the blog, the next y people don't vote, and the last z upvote the blog

    Cannot see why it's correct :( Consider this case? 4 1 1 1 1 First one upvote, then the following 3 people does not affect the rating.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      uh I meant nondecreasing. Plus I wasn't being very clear I guess.

      What I meant is that: if we allow people to change upvotes to no vote/downvotes, and no vote to downvotes, we can achieve the desired format. In this case, we have the first person downvote it (it's not too hard to show that this cannot increase the final rating), then the second person (instead of upvoting) does not vote. Lastly, the last 2 people upvote, for a net +1.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve div 2 C without binary search?

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

    The fraction, that we need to get is fraction of this type: n * p / n * q. Now we need to find n. The only things, that we can do with starting fraction are +1 to denominator and +1 to both denominator and numerator. So, we cannot decrease y — x. That is why let's make an inequation: n * (q — p) >= y — x; n >= (y — x) / (q — p). Also, we cannot decrease numerator, so: n * p >= x; n >= x / p; Now, to find the first n, where the both inequations are correct let's take max of these ceiled values: (y — x) / (q — p) and x / p. The answer is: n * q — y, because the difference between numerators is always <= then difference between denominators due to our first inequation. Also, you shouldn't forget about cornercases, when p = q and when p = 0.

»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

But where is editorial?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve Div2 D/Div1 B ??

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    My solution gets like this : iterate all x for 0 to some high value (mine is 10000), this will be our answer. Check whether Vasya's score can be strictly higher than Petya's with current x.

    How do we check it? First we do some observations. For every problem, we can either :

    a. "maximize its score" (by using all fake account and get unsuccessful submission on this problem). Why is that? Because by using fake account to get unsuccessful submission for this problem, the number of participants increased and the number of solver of this problem remains the same. Therefore, the fraction goes more smaller as x goes higher, so this problem score increase

    b. Get all fake account have successful submission for this problem, it will make this problem score decreased. Contrary to the a. Option above, the number of solver and total participants are increased, therefore the fraction goes higher, and the score for this problem decrease.

    Since there are only 5 problems in total, bitmasking is not big. we can try all configuration from 0 to 31 for the mask. For each bits of the mask, 0 represents strategy a. While 1 represents strategy b. Then for each configuration, try whether at any point Vasya's score can be greater than Petya's. Please note that to apply strategy b., Vasya must first solve the problem. It's easy to check that if current bit is 1 and Vasya's status is -1, then this bitmask configuration is invalid and try next possible configuration

    Why we should try x only to 10000 and not 10^9 + 7? Because at some point the fraction as the number as fake account goes up, the fraction ratio of (solver/total_participant) will be extremely low or high so we can ignore them. Hope my explanation is clear

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      I didn't check all 32 cases for this problem.

      For each problem, Vasya should fake as many successful submissions as possible ONLY IF he solved it and his performance is WORSE THAN Petya's (to decrease this problem's score and minimize the score difference for this problem).

      Otherwise, just submit unsuccessful submissions.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      thanks, it's very clear. i wasn't able to comeup with bitmasking thing.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      nice

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Finally 2k17 :D One of the great contest of this year. Learned a lot

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

А когда будет разбор?

»
8 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

очень интересно посмотреть на авторское решение 3 задачи

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А мне четвертой, а то судя по посылкам там все не очень хорошо!

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

When will the editorial be posted?

»
8 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

In problem Div 2 D the point calculation says -> 2000*(1 - 40 / 250) = 1680

Where 40 is the time of solve and 2000 is max point. So what happens if he solves a problem at 0 min from the start of contest? This case is valid as it is used in 3rd test case.

Thanks in advance.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How I check,how many problems I solved in codeforces?