By tourist, 6 months ago, translation, In English,

Hi everyone!

The last elimination round of VK Cup 2017, Round 3, will take place on May 7 at 18:35 MSK (check your timezone here), along with separate Codeforces Round #412 for both divisions. All three rounds will be three hours long, and all three rounds will be rated.

The contest "VK Cup 2017 — Round 3" is for teams qualified from Round 2 or Wildcard Round 2. The top 20 teams will advance to the final which will be held in July 2017 in Saint Petersburg!

Huge thanks to KAN, qwerty787788, PavelKunyavskiy, AlexFetisov, MikeMirzayanov, and VK company for making this round possible.

Codeforces will be the main character of most problems. Don't forget that it's useful to read the statements of all the problems.

Good luck!

As we're in year 2017, the scoring will obviously be static. The exact scoring distribution will be announced before the round.

UPD 1. The scoring distribution is:

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

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

UPD 2. Due to yesterday's registration troubles the start of the contest is delayed by 10 minutes.

UPD 3. Congratulations to the winners!

VK Cup Round 3:

  1. zemen, Zlobober
  2. V--o_o--V, LHiC
  3. RomaWhite, witua
  4. YakutovDmitry, BudAlNik
  5. Golovanov399, I_hate_ACM

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. Tutorial is now available.

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

»
6 months ago, # |
Rev. 2   Vote: I like it +1009 Vote: I do not like it

My first reaction to round author:

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +183 Vote: I do not like it

    My first reaction to number of upvotes!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's my first reaction when I saw that tourist can't take first place in a contest for once.

»
6 months ago, # |
  Vote: I like it -36 Vote: I do not like it

What does this mean "maybe someone else"?

»
6 months ago, # |
  Vote: I like it -7 Vote: I do not like it

How many problems there will be ?

»
6 months ago, # |
  Vote: I like it +75 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +77 Vote: I do not like it

Image and video hosting by TinyPic

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

»
6 months ago, # |
  Vote: I like it +146 Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +738 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    that's beauty :D Good luck to You :D

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +158 Vote: I do not like it

    Go to a trip and become a tourist :)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I have an exam tomorrow and I was planning to skip this round too but now I am planning to study hard now to attend the contest.

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

    i'm am participating after 2 months and the writer is tourist :(

»
6 months ago, # |
Rev. 3   Vote: I like it +87 Vote: I do not like it

What does this means ?!

UPD: Fixed :)

»
6 months ago, # |
Rev. 4   Vote: I like it +9 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +42 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +71 Vote: I do not like it

    No, there was a bug in registration settings, we are fixing it, the registration will soon be open again.

»
6 months ago, # |
  Vote: I like it +268 Vote: I do not like it

DIV 2 people right now

»
6 months ago, # |
Rev. 4   Vote: I like it -16 Vote: I do not like it

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

Good luck everyone!

»
6 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Register again, to take part in contest.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
Rev. 5   Vote: I like it -53 Vote: I do not like it

...

»
6 months ago, # |
  Vote: I like it +618 Vote: I do not like it

»
6 months ago, # |
  Vote: I like it -32 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it -11 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

what does it mean that the score will be static?

»
6 months ago, # |
  Vote: I like it +78 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing

»
6 months ago, # |
  Vote: I like it -20 Vote: I do not like it

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!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    work hard all that year and you will become ( or close to ) a tourist :)

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for you encouragement,I try my best to develop myself

»
6 months ago, # |
  Vote: I like it -35 Vote: I do not like it

I am Arab :| downvotes please

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -25 Vote: I do not like it

      everything I want is downvote And I'm also arab :/ They are great people but maybe it is a way for increasing downvotes

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      He can do anything to get upvotes :| !

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -48 Vote: I do not like it

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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

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

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        so why no downvotes¿

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
          Rev. 3   Vote: I like it +49 Vote: I do not like it
          Spoiler
»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I'm sure that you want to get upvotes.

    If you really want to get down votes remove: "Ow I think I can do it this time with this comment"

    You can learn from this guy: Comment

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try using "Up votes please :) "

    P.S. i'm perfectly satisfied with my contribution status, so if you wanna give me down vote, give it to this
    -TOPCODER- guy instead and help him reach his dream.

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Story of tourist and problems :

»
6 months ago, # |
  Vote: I like it +53 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    respect for everybody. Did tourist stood first in every contest?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      You can check.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +25 Vote: I do not like it

        so basically whenever he doesn't come first he loses rating? tough job

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

More delays?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating? Or spend the semester? :'v

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Delayed by 10 min

»
6 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Delay, delay everywhere

»
6 months ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

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 -topcoder- 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 :(

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    bruh.. do u even english?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Ironically enough , it says that he is from MIT :P

»
6 months ago, # |
Rev. 2   Vote: I like it -29 Vote: I do not like it

I hate delayed contest :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Delay again!!

»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
6 months ago, # |
Rev. 7   Vote: I like it +23 Vote: I do not like it

after hearing the contest is on Sunday:

After hearing it is from tourist:

»
6 months ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

That's why I love problems of tourist:

»
6 months ago, # |
  Vote: I like it +18 Vote: I do not like it

What if I hate Math! xD xD

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Rating drops deeper than Mariana Trench. :)

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Fairly difficult contest but great problems by a great problemsetter!

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +138 Vote: I do not like it

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.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I got WA once on test 11 with binary search.

    A linear scan got pretest passed.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      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

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you mean by linear scan?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Greedy?

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            make all new accounts submit a correct solution to a problem if time[Vasya] > time[Petya] and Vasya has a correct solution to the problem.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Why points in scoreboard changed?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack case for Div2.C?

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

how to solve div2 problem D? Can anyone please help

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2C?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    About binary search or math to solve it.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    binary search

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Search what?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Assume p*t/q*t =(x+c1)/(y+c1+c2).

        Now binary search for t

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But we don't know c1 and c2 right?

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            the condition for valid t is c1>=0 and c2>=0

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        (x+a)/ (y+b) = p/q this implies x+a = pn and y+b = qn for some n. Now apply binary search for n with high as 10^9 , i got the idea late :-/ Hope this helps. Check for conditions in binary search .

  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

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

    Code

    Got AC :)

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how is k fixed?? i did binary search on k but failled pretest.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In problem we have to find k such that k * p - x ≤ k * q - y. From inequality we get . Then check if k is answer or not.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          nice catch!! was solution same as this, or simpler

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      "It is guaranteed that p / q is an irreducible fraction."

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hmm okay, I should carefully read statement.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

  • »
    »
    6 months ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    See the comment at the top of my solution: http://codeforces.com/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)
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test 7 about DIV.2 problem B?

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve div2 C??? :/

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try using binary search

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    binary search multiple of q/p

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      yes I did that...check my submission. We basically check multiples of p/q such that it m*p-x <= m*q-y and both of the term >0

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it -10 Vote: I do not like it

      Is possible p=0? For example 1 0 2 0 3

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        That shouldn't be valid since p/q must be irreducible.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Is 0/1 irreducible or reducible?

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Irreducible, there surely is a test with 0/1. The statement also says that p >= 0.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think it can be done in O(1). Multiply q/p by a smallest constant such that newq-newp>=y-x

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        And how do you find this constant in O(1)? (This is incorrect anyway btw)

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Just compare the ratio of difference(denominator-numerator) of the two rational numbers. Code

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Interesting, I modified my own correct code to find the constant and it failed on test 1. Code

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Used Binary Search. Realized that after making more submissions final value of x/y must be a multiple of p/q.

    Let number of successful submissions, total number of submissions and such a multiple be k , d, g an, then g*(q-p) + (x-y) >= 0 and k >= 0 and d >= 0.

    The goal is to find the first multiple such that g*(q-p) + (x-y) >= 0. It turns out that we can binary search on the g.

    k = g*p-x d = g*q-y

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I can't see others' solutions?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To force us ask questions "How to solve ...?" here instead of looking at solutions by ourselves :)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    While system tests won't ended,you can't see solutions

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually, I can see them now.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can see now

»
6 months ago, # |
Rev. 4   Vote: I like it -20 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Fastest start of System Testing this year :o

»
6 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Understanding question div 2 B is harder than solving it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    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.

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    p/q is guaranteed to be irreducible.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    p/q is guaranteed to be irreducible, the answer is 0 though.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the answer should be 0 since the ratio is the same. btw p/q is irreducible fraction, so your input case is invalid

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is assumed that p/q is irreducible, so this case doesn't exist.

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it -10 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    0, since the ratios are already the same.

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it -14 Vote: I do not like it

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

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but how to implement it?

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      i can't understand your formulas for t

      ll s=max((x+p-1)/p,(y+q-1)/q);
      MX(s,(y-x+q-p-1)/(q-p));
      
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        (A+B-1)/B means ceil(A÷B).

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

The most upvoted blog ever on CodeForces!

»
6 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it -7 Vote: I do not like it

why all my sloved skipped...

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    MikeMirzayanov and the entire codeforces community hates cheaters.

»
6 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Editorial? Nice set by the way

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div 2 C without binary search?

  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    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.

»
6 months ago, # |
  Vote: I like it +14 Vote: I do not like it

But where is editorial?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve Div2 D/Div1 B ??

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      nice

»
6 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    What did you learn?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      He learned that he should not say "Learned a lot" on Codeforces if he doesn't really mean it. xD

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

When will the editorial be posted?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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