Recent actions

This will work .

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


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

I don't think it is posted 20 hours ago. That's the time it is written. It is posted about 3 hours ago. (about when the first comment is posted)

Created or updated the text

Sorry I was following this blog. Thanks

It was posted 20 hours ago

When will the editorial be posted?

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.

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

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

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

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

These upvotes prove how much people love tourist

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.

What did you learn?

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

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.

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.

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

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.

MikeMirzayanov and the entire codeforces community hates cheaters.

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

how to solve Div2 D/Div1 B ??

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.

But where is editorial?

How to solve div 2 C without binary search?

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.

Editorial? Nice set by the way

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

See the comment at the top of my solution:

  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)

p and q must be relatively prime

why all my sloved skipped...

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

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

I haven't read the problem myself, but given that n is 2000 it should TLE.

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

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

ok, now its clear. thank you

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

Same Here .... More than 1 Hour .

i can't understand your formulas for t

ll s=max((x+p-1)/p,(y+q-1)/q);

but how to implement it?

Me too bro

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.

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

The most upvoted blog ever on CodeForces!

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.

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

Can someone explain mathematical solution of Div1 A / Div2 C ?
Petr's one

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

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

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

0, since the ratios are already the same.

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

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

And also I felt tourist thought to bluff Div1 B as binary search (only my personal opinion)

WoW! ... ;)

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

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

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

Got it, Thanks!

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

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

p/q is guaranteed to be irreducible.

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

We all know why :D :P

Hail tourist :D

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.

Actually, I can see them now.

You can see now

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.

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

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

Is 0/1 irreducible or reducible?

Hmm okay, I should carefully read statement.


I'm too... It's so sad(

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?

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

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

But it is down now.

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

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

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

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.

Understanding question div 2 B is harder than solving it

Fastest start of System Testing this year :o

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

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

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

But we don't know c1 and c2 right?

(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 .

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

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

What do you mean by linear scan?

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

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