Блог пользователя fcspartakm

Автор fcspartakm, история, 5 лет назад, По-русски

Привет, Codeforces!

13 октября 2019 года в 12:05 MSK состоится Codeforces Round #592 (Div. 2). Обратите внимание на необычное время начала раунда!

Раунд будет рейтинговым для участников второго дивизиона (с рейтингом менее 2100). Условия будут доступны как на русском, так и на английском языках.

Этот раунд проводится по задачам регионального этапа Всероссийской командной олимпиады школьников по программированию 2019, проходящего в Саратове. Задачи вместе со мной придумывали и готовили Иван BledDest Андросов и Владимир vovuh Петров.

Хотелось бы сказать большое спасибо Ивану isaf27 Сафонову за помощь в подготовке задач, Михаилу MikeMirzayanov Мирзаянову за замечательные системы Codeforces и Polygon, а также Ивану CaseRuten Худошину, Ивану Ivan19981305 Георгиеву, Леониду Peinot Миронову, Антону anon20016 Лебедеву, Ксении Pavlova Павловой и Дмитрию dmitrii.krasnihin Краснихину за прорешивание задач.

Участникам будет предложено семь задач и два часа на их решение. Разбалловка будет объявлена позднее.

UPD Разбалловка 500-1000-1500-1750-2500-2500-3000

UPD Разбор задач

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

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

I wish the round be nice without any DDOS attack, in queue or without any delaying, best of lucks.

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

I really hope no DDOS attack again again!

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

A friendly time to Chinese.

Hope this round will no DDOS.

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

Contest with unusual time, keeps the hackers from the crime <3. Hope a great contest for everyone!!

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

Short problem statements, please!

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

Желаю удачи и провести раунд без DDOS атак)

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

I wish no DDOS, no long queue, more Accept

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

A friendly time … Hope this round will no DDOS. no queue & Compact statement.

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

Rated Div.2 and a friendly time to Chinese again!!!

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

When contest will be start,open some problem in new window..May be it will be useful if DDOS attack happend.

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

Wish me good rating

I wish you all too.

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

Score distribution?

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

The Saratov olympiads are popular on Codeforces :)

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

Score........... :3

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

Why cant I submit my code on problem A? it says I have already submited the same code (I submited different codes for several times it says the same always), and in "My Submitions" there is nothing. os I cant submit my code on problem A.

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

How to solve B?

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

    The solution is max{N, 2 * (N — positionOfTheFirstStaircase), 2 * (positionOfTheLastStaircase + 1)}

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

    I used BFS and start point is (floor,room)=(0,0)(0,s.size()-1)(1,0)(1,s.size()-1)

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

      No need to use BFS or DFS actually, the solution is always fixed, you can use two pointers on each end of array, then you decrease the n, when you see 1's on either side you do the followings;

      10000 or 00001 -> If 1's is at first or last means = n*2 (where n is array size)

      In other situations like following, answer is always decreasing;

      initially n = 5;

      00010 -> n = 4 here, ans = 2*n = 8

      00100 -> n = 3 here, ans = 2*n = 6

      01000 -> again n = 4 here, ans = 2*n = 8

      It does not matter how many 1's we have, the point is we need to have at least one 1's and position of 1's

      01110 -> again n = 4 here, ans = 2*n = 8

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

    there are only two possible cases either you start from leftmost room and use rightmost stair or start from rightmost room and use leftmost stair. ans is maximum of these two cases.

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

What on earth is test case 5 for C

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

    :(

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

    I can totally feel you bro... i wrote a solution which worked for 10^6 test cases that I randomly generated using Chelper and my code passed without any error, but this case 5 totally took my life.

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

    try this if you use exgcd approach:

    1000000000000 90000000000000007 100000 77777

    Answer should be

    899999922230 99991 99999977779

    My exgcd template failed on this because of long long overflow when multiplying

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

      Nice catch! I got -1 in my implementation...

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

      Thanks for your sample so much. And how to use __int128 without Compilation error in Codeforces?

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

        me,too.I also got a Compilation error when I used __int128 to avoid the overflow with exgcd.And I also want to konw can we use __int128 in Codeforces?

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

        Codeforces runs on 32-bit system so __int128 is not supported.

        In this problem __int64 is enough to get accepted, where an extra mod should be added. Here is my code.

        LL cal(LL a, LL b, LL c)
        {
        	LL x, y;
        	LL gcd = exgcd(a, b, x, y);
        	if(c % gcd) return -1;
        	b /= gcd;
        //	x *= c/gcd;       // wa
        	x *= (c/gcd%b);   // ac
        	LL ans = (x%b+b)%b;
        	return ans;
        }
        
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    If you really want to solve that equation, maybe you could try something like this:

    The goal is to find the smallest possible $$$y$$$ such that $$$wx+dy=p$$$.

    We could first divide both $$$w$$$, $$$d$$$ and $$$p$$$ by $$$gcd(w, d)$$$ then $$$w$$$ and $$$d$$$ become coprimes.

    We take $$$mod\ w$$$ and the equation becomes something like $$$dy=p \ (mod\ w)$$$. Thus $$$y=p\times {d}^{-1}\ (mod\ w)$$$.

    For coprimes, modular inverse always exists and could be found by extended euclidean algorithm.

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

      So nice!It fits well with the data range.Perhaps cuz I am too inflexible when learning euclidean algorithm.

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

      Why we need to find the smallest value of y? I get all of your explanation except that smallest y part. Please help me out.

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

      Will this solution work if the value of w and d is big (1e9) ?

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

        I believe so (as 1e18 could still be handled by long long). But it may require more careful implementation.

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

What is C's solution?I solved A,B and D, but I could't solve C.:(

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

    first check if the (p % (gcd of(w,d) != 0) then the answer -1.

    then you should know the min number of draw matches you need cuz of (d<w) and more number of winning matches.

    so you should precalculate this : Mod[ (i*d) % w ] = min ( Mod[ (i*d) % w ] , i ) for each (0 <= i <= w-1) calculate def=(p%w) and now you know the min number of draw matches you need to achieve ( def = (Mod[def] * d) % w )

    the number of draw matches is Mod[def] and the number of winning matches is ( ( p — (Mod[def]*d) ) / w ) just make sure the sum of them less or equal to n then print them

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

      Thank you for the easy-to-understand explanation!

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

      Why condition (p % (gcd of(w,d) != 0) is correct? I think its correct if w and d can be <0. But in our task we have to find >= 0 multipliers. For example, n = 100(its doesnt matter), p = 17, w = 7, d = 6 (answer = -1, but the condition passes it). So, can someone explain me why do we need this condition?

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

        it is correct in all situations.

        I didn't say it's the only condition.

        it just to make the approach faster.

        after calculating the answer check if the values are valid, that's mean ((a+b)<=n &&(a>=0)&&(b>=0))

        your example : 17 7 6 def = 17 % 7 = 3

        Mod[0]=0

        Mod[1]=6

        Mod[2]=5

        Mod[3]=4

        Mod[4]=3

        Mod[5]=2

        Mod[6]=1

        Mod[def] = Mod[3] = 4

        so the numbers of draw matches are 4

        then the winning matches are equal to (p-(Mod[def]*d))/w .

        which is (17-(4*6))/7=(-7)/7 = -1 .

        (a<0) is not valid value.

        then the answer is (-1) .

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

What is Approach for C??

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

So weak at number therory, How to solve C...

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

    Diophantine equations i guess.

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

      I implemented Extended Euclidean alg and got one of the solutions of the eqnx*w + y*d = p and then the general soln for this eqn is x = x0 + k*(d/g) and y = y0 -k*(w/g). So I ran a loop for k from 0 to 1000000 and found if x+y<=n if yes then I print x y and n-x-y. But this is giving me wrong ans on test 4. :(

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

        k may be less than 0, but on test 4 it doesn't matter:( I tried the same way as you.

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

          I missed this case when k<0 shit. Thank you

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

            Even when k varies from -1e6 to 1e6 ; this does not help... I did the same mistake in contest and then got help from a friend to figure out that k can be huge too...

            Reason — your x0 and y0 will always be less than d ( or w ; which ever you use to find particular solution ) ;

            and then x = x0 + k * (d/g) when k has upper bound = 1e6 can only take you somewhere upto 1e11 even in best case.

            Then how would you ( and also I will )find solutions whose actual answer is something like ( 1e16 , 0 , 0 )

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

              Reason — your x0 and y0 will always be less than d ( or w ; which ever you use to find particular solution ) ;

              This is only true for y. You need the possibility to decrease the number. Only possible when transforming $$$w$$$ draws into $$$d$$$ wins not vice-versa.

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

                So do you mean we can vary k from -1e6 to 1e6 finding x0 first and then y0 ;

                And then vary k again from -1e6 to 1e6 in case we don't get a (x,y) ; but this time find y0 first and use it to find x0 ?

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

    I have tried the diophantine equation but no luck. What a bad problem for C..

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

    I tried to solve it using extended GCD algorithm. This helps you to find (x, y) such what:

    wx + dy = p, though after finding a initial value of (x, y) you need to somehow convert it into a valid solution (Here is where I got totally stuck)

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

    You can use extended Euclidean algorithm to find x and y(keep in mind there can be more than one solution to the linear combination, so you need to take the one where y is minimal while still being >= 0).

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

    brute force would work cuz small contraints on w or d

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

      I used brute force but got TLE on test 66

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

        Me too. It was enough to check if the solution exists by checking divisibility of p by gcd(w,d)...

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

    binary search and binary search and more binary search... no number theory no nothing only binary search... at least that's how I did it

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

      could you explain your approach ??

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

        First I search for an x(number of wins) such that there "may" exist a possible y(number of draw) value so that x*w + y*d = p. (if n = 30, p = 60, w = 3, d = 1, and you pick x = 1, even y = 29 won't be enough to get 60 points and if x = 30 you are way over 60 point mark and there does not exist a way to reduce points.) Notice the "may"? because even you pick a valid x, then remaining points you need to gain is rem = p-(x*w), and if (rem%d != 0) then there does not exist any y for which you can gain p points (because there won't exist a y for which rem = y*d). But d <= 1e5. So all we need is pick some x such that rem%d = 0. how to pick such x? brute force. start from the initial x that we found. then run loop for (x+i) where (i runs from 0 to 1e5). and another similar loop for (x-i).

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

          Legend_of_Azkaban coudnt understood this part "So all we need is pick some x such that rem%d = 0. how to pick such x? brute force. start from the initial x that we found. then run loop for (x+i) where (i runs from 0 to 1e5). and another similar loop for (x-i)" Can you explain? Thanks :)

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

            I assume you understood the part why we need such x such that rem%d = 0. The explanation of the next part is: say you have a number a <= 1e5. Now from any number x to x + 1e5, (that is x, x+1, x+2....x+1e5)it's guaranteed that there exists at least one such number c within this range that is a multiple of a. Now if you will consider only the multiples of some number b, that is you want to find one multiple of a from x, x+b, x+2b... then your search space should be x to x+ b*1e5. that's what I did, start from x and go to x+1e5. In the meantime see how rem changes. rem = p -x*w(initially). then rem = (p-x*w) -x, (p-x*w)-2*x, (p-x*w) — 3*x...(as you increase x by 1 every time, you are only considering multiple of x). Now if I run this loop till x = 1e5, then I traverse a range from rem to rem — x*1e5. And if that does not give us any multiple of 'd', then we won't find any even if we continue searching. Here We need to consider both increase and decrease of x. because maybe if you keep increasing x you may find x*w > p , before you have reached a multiple of d. But if you decrease the value of x, you will find one correct multiple of d.

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

    After contest, I solve F and G by myself, so C is the hardest for me...

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

Was E not a greedy solution?

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

    We ca use Binary Search to find minimum difference, The Min. element or Max. element in the final array after applying operations will be from the original array.

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

      can you please briefly explain, how can binary search be applied on E?

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

        We can do binary search on the ans(i.e minimum possible difference between max and min element). let's say we want to find if it is possible to apply <=k operations such that difference is less than equal to X. we can traverse the array and for ith element we can assume it to be the min. element than max. value must be a[i]+X; so now all the values less than a[i] must be made equal to a[i] and all values greater than a[i]+x must be made equal to a[i]+X, so we can find number of operations required to achieve this if we sort the original array and keep prefix sum, similarly we will assume the ith element to be max. value in array and min. value will then be equal to a[i]-X. and then find number of operations required. we will finally keep the min. number of operations required after traversing the array so if this value is less than equal to k than do right = X-1; else left=X+1;

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

    I guess, E is ternary search within binary search.

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

    i solved it greedy

    increase / decrease elements which frequency is less to the next element

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

    I solved it by greedy.I hope it passes the main system cases too!

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

Solutions of other participants and tests are locked for the next 30 minutes, since there is an onsite competition using the same problems. When it finishes, we will open the data for everyone.

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

how to solve C??

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

    We can employ brute force. Iterate over all possible numbers of draws from zero to $$$W-1$$$. We can easily compute the number of wins necessary with a given number of draws and whether this configuration is possible (this requires that $$$P = Di$$$ mod $$$W$$$, where $$$i$$$ is the number of draws, and that $$$(P - Di) / W + D$$$ is at most $$$N$$$, since we need to have an integer number of wins and can have at most $$$N$$$ wins and draws). As soon as we find a working configuration, just print it and exit.

    We now prove that this is optimal--in other words, this will find a solution if one exists. Note that if there exists a solution $$$(x, y, z)$$$ with $$$y \geq W$$$, $$$(x+D, y-W, z)$$$ is also a valid solution. Moreover, the total number of wins and draws in the second solution is lower than in the first, meaning the second solution is more likely to fit within our $$$N$$$ game limit. Thus, any optimal solution will have $$$0 \leq y < W$$$, as desired, so our solution will find a solution if one exists.

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

      How one can prove that number of draws must be below $$$W$$$? I iterated to 10^7 but couldn't prover that it's correct.

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

        As shown in the proof above, if there exists a solution with at least $$$W$$$ draws, there also exists one with $$$W$$$ fewer draws than this solution, so by this logic, we can reduce the number of draws by $$$W$$$ until it's less than $$$W$$$.

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

          I musunderstanded. Thought that $$$y$$$ is number of losses. And I iterated over $$$z$$$ instead of $$$y$$$. But pretests has been passed. Thanks.

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

        You can transform $$$W$$$ draws into $$$D$$$ wins.

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

      I dont quite understand the notation you wrote, is W is as same as w in problem (same with D)?

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

      I really liked your solution. Above all its simplicity. Very good idea

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

      Tank you Sir!
      That helps me a lot,and when I passed this problem I konw that the exgcd is not unique to solve problems like this.It is only faster than O(N).
      There's only one things you didn't mention that we must let P>=Di or we'll WA62,but anyway there maybe only me who don't think about it!

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

      maybe

      $$$(P-Di)/W + D$$$ is at most $$$N$$$

      should be

      $$$(P-Di)/W + i$$$ is at most $$$N$$$.

      Am I right?

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

Finally a successful round with no delay,queue and most importantly no DDOS

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

I think C can be done using Linear Diophantine Equation, but I don't know how to find x, y, z so that x+y+z = n is satisfied. Any hints?

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

    the z is variable, u should just minimize y due to w > d (it should be correct, but i had wa5 too :(

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

      yeah i know, z is variable. but i didnt know how to use Linear Diophantine Equation to find such x and y so that z can be obtained which satisfies x+y+z = n.

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

      You can just brute force on y, because it's at most W — 1, because you can always replace W draws with D wins and minimize it.

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

    find solution with minimum x+y such that x,y >= 0.

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

    It is the core part of my submission code with some comment. due to overflow issue, you should use python.

    if n-(x+y)<0:

    //n-(x+t*d/g + y-t*w/g) >= 0
    
    //n >= (x+y)+t(d-w)/g
    
    //(n-(x+y))*g/(d-w) <= t (inversed ineq because d-w<0)

    t=(n-(x+y))*g//(d-w) + (0 if (n-(x+y))*g%(d-w)==0 else 1);

    x+=t*d//g;

    y-=t*w//g;

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

    I have an solution: the problem can become this: xa+yb=c (a&b&c are known)

    And make y+x as minimum as possible (z = n-x-y)

    to achieve this we must let y as small as possible (since a>b) ,so (c-yb)%a=0

    because y must <a so try all the y,the smallest is the answer.

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

No DDOS attack No in queue, Finally codeforces was back.

Thanks to MikeMirzayanov and every on works in this awesome platform ^_^

UPD: WOW and Fast system test !!

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

Problem C makes me feel like I'm in ICPC onsite, instead of Codeforces. (╯^╰)

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

How to solve D?

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

    First, the answer is $$$-1$$$ unless the tree is a line (i.e. all vertices have degree $$$2$$$, except for two, which have degree $$$1$$$). Proof: suppose vertex $$$A$$$ is connected to vertices $$$B, C,$$$ and $$$D$$$. By considering the paths $$$B-A-C$$$, $$$C-A-D$$$, and $$$D-A-B$$$, we see that all four of these vertices must have different colors, but with only three colors, this is impossible.

    If the tree is a line, then there are six possible configurations, each of which results from fixing the colors of one of the endpoints and the vertex adjacent to it. We can simply brute-force all six configurations and print the best one.

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

    The tree has to be a straight line to have any solution, since if it has more than 2 degree it can't be satisfied with 3 colors. After that the color has only 6 possibility: $$$[1,2,3,1,2,3,..]$$$ $$$[2,3,1,2,3,1,..]$$$ .. and all other permutations of $$$(1,2,3)$$$ repeated

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

What's the approach to solving E?

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

    We employ a greedy approach. Start by sorting the data. Then, until we're out of moves and in increasing order of $$$i$$$, increase elements $$$0$$$ through $$$i$$$ to the value of element $$$i+1$$$ and decrease elements $$$N-1$$$ through $$$N-1-i$$$ to the value of element $$$N-2-i$$$.

    On our first iteration our answer decreases by one with each of our moves (since we are increasing/decreasing the minimum/maximum with every move), on our second iteration our answer decreases by one after every other move (since we need to increase the lowest two elements now each time we want to raise the minimum, and similarly for the maximum), and so on. It's relatively easy to see that we can't do any better, since at each step we're choosing the most efficient possible way of closing the gap.

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

      can you please explain with a small example?

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

        In sample case one, the sorted data is $$$1, 3, 5, 7$$$, and we have five moves. First, when $$$i=0$$$, we use our first two moves to increase the $$$1$$$ to $$$3$$$ and the next two moves to decrease the $$$7$$$ to $$$5$$$. Thus, we have one move left and have the array $$$3, 3, 5, 5$$$. Now, we have $$$i=1$$$, and we want to increase the first and second elements to the value of the third. With only one move, the closest we can get is the array $$$3, 4, 5, 5$$$ which has range $$$5-3=2$$$.

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

      Can anyone find the mistake with my algorithm? I WA on pretest 8.

      I defined Lcost(i) to be the cost to make subarray [1..i] equal to a[i] and Rcost(i) to be the cost to make subarray [i..n] equal to a[i]. Then used two pointers: For each l such that a[l] < a[l+1], let r be the minimum r such that Lcost(l) + Rcost(r) <= k. Since Lcost is increasing, r will be increasing as we iterate over l. Finally, we have some extra moves we are allowed to make: extra = k — Lcost(l) — Rcost(r). First, if r = l+1, then we can decrease the gap by floor(extra/min(l, n-r+1)). If r > l+1, then we try to fill the two gaps greedily: if l < n-r+1, then try to increase l first, then decrease r. Otherwise, do the opposite. There is an edge case which is we constrain l to increase by no more than a[l+1]-a[l] (this should not be necessary for r).

      I return the minimum of the answers for each valid l.

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

I started solving C before thinking that I can totally solve C fast. But a very very wrong decision :( from my side. And now I am totally going down in rating.

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

Is it possible to solve problem C using binary search?

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

    I tried Binary Search for y inside a binary search for x .. i got a WA on test 4 :\

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

      Binary search cannot work because of the boundary not being clearly defined. A y may not satisfy the equation due to divisibility but y-1 may.

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

Solution for C: Assume, that you have $$$X$$$ won, $$$Y$$$ draw games. Say, that you won't take $$$y$$$ more, that $$$w$$$, beacause, in other way we will get $$$(w + (y\mod{w})) * d + x * w\leftrightarrow w*(x+d) + d * (y\mod{w})$$$, and y will be less, that w. If we know Y, we can get X: $$$(p-y*d)\div{d}$$$ check, that this answer is correct, and print it, if true.

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

D was very interesting problem, how to solve it?

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

    Observation: If there is a node with more than/equal to three edges, whatever you paint you will get a path of three nodes with "only two" colours. So any valid painting must be a list/degenerate tree. The colour pattern must be a sequence of "RGB"/"RBG"/...

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

    tree is a line if not answer = -1. After that you calculate all case and chose a best case =))

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

RIP testcase 5 for C

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

C really difficul with me :((

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

Could someone tell what was the use of small constraints of w,d in C. How was it useful for brute force and when will the answer be -1?

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

    For number theory solution, one may need to solve a diophantine equation $$$xw + yd = p$$$. Take mod and we have $$$yd=p$$$ mod $$$w$$$. This "small" constraints enable brute force solving but not taking modular inverse.

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

problem C really difficul with me :((

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

What is pretest 8 for E??

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

I tried to solve C but I Got Wa on test 5 using Binary search I don't know why my idea is wrong, anyone can help ?

I was searching for number of wins so my start = 0, end = n, them (n — mid) will be number of draw matches, So total points so far = mid * w + (n-mid)*d, Now the idea,

if total points < p, I should win more matches, So start = mid + 1 and continue searching.

if total points == p, So I can win with this number of wins and this number of draws with 0 lose matches.

if total points > p, (rem now is the number of draw matches),

I will try to make the team lose from o to rem matches using the same idea(binary search) if I found at sometime I can make the same exact point this will be answer otherwise I will continue searching using the same idea of binary search

code: 62490213

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

I can't solve problem A

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

Too many shit problems in a single div2 nowadays.

Come on, even div2s got some dignity. Show some respect. Please don't shove bunch of div2Cs in div2s like people don't give a shit.

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

Great round, make more rounds like this!

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

Please don't just shove a bunch of div2Cs in a row in div2s. Come on, even div2s got some dignity :|

Too many shit problems in a single div2 nowadays :|

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

I am glad that the round passed without DDoS attack :)

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

C is more difficult than D, E and F.

Unfortunatly did read E and F after contest :/

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

Отличный раунд, однако так как в раунде 7 задач, по моему мнению он должен был бы длиться не 2 часа, а 2 часа 15 минут или 2 часа 30 минут. Тогда бы многие успели бы сдать еще задачи, в том числе и я.

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

    А если бы он длился 24 часа, то многие еще больше успели бы сдать...

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

    То есть, С у вас упала из-за того, что раунд был коротким? :)

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

In C you can just brute force on Y from 0 to 1234567, it's work but don't know why, can somebody explain?

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

Most system fail in today's Div 2 C. I wonder why they keep such weak pretests?

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

Problem C pretest were too weak, constrains were not checked.

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

OMG!! so many system test fails for C on Test 62.

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

Lol, nice system tests on C. What is approach failed?

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

Powerless to solve problem C when I haven't known diophante before.

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

How to solve C?I got a wrong answer on test 62...

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

It's a good choice to give up C :)

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

So, very nice round)) Everything was cool except C. Only 500+ solutions from more than 1500 have been accepted :(

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

Thanks so much... First time become blue <3 thanks ^^

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

what is pretest 6th in d??

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

Loved the contest!

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

Спасибо за очередной едук !!! ( Внимание! Задачи не отсортированы по сложности )

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

what is the core logic behind F?

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

    The observation is if we have a contiguous subsegment of single coloured cells, they would never flip. If we have a contiguous subsegment of alternating black and white cells, the length of this segment would decrease by 2 each time we flip it. (You can view this as the cells on the ends of this segment are absorbed by the single coloured segments adjacent to them). Based on this, we may work out the max possible number of flips each position could do.

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

Excuse me... Why my code get skipped?

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

За задачу С вполне можно было дать и 2000+.

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

The problems of this round are sooooooooooooo hard to implement!

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

If you got WA on test case 49 in problem C, you may miswrote p>n*w as p>=n*w in the beginning like me...TAT I submitted it very early and in the rest of competition I did nothing... What a pity!

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

I really liked the problems, but spent too much time on C :(

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

Can someone explain why brute force works on C? I brute forced for values of x between (p-n*d)/(w-d) and p/w. Isn't this still o(P)?

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

    p <= 1e17

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

    I tried to brute force on x it didn't work .. then i tried to brute force on y i got accepted , can anyone explain please ?

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

      you cant brute force on x cuz it could be between [1,min(n,p/w)]

      but y can be only between [1,w-1]

      proof : if y=w then y*d=w*d

      rewrite it like this y*d=w*(a1) where (a1=d)

      you can see (a1<y) cuz (w>d)

      so it's better to consider (a1) winning matches than (y) draw matches

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

I want to try to solve more problems like C, Kindly can anyone suggest those problems?

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

Editorials?

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

Very sorry to write this, but big downvote for problem C! A well-known problem. The statement itself contains exactly the equation you need to solve (x * w + y * d = p). And you have to deal with int64 overflow when solving it with extended Euclid! (test 7) WTF

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

More than 10 people in the top 40 did not pass C

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

During the contest, I use exgcd for problem C, then I realized that the answer in problem C may cause longlong overflow, so I tried to use __int128, and then

So I wonder if it is possible to solve problem C by using exgcd(No matter in python or C++).

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

???? My rating is lost???

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

is this contest unrated?because a few minutes ago i had updated ratings but now it is back to one which was before the contest

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

Oh my god , is this round unrated ?

I'm a step away from the master .

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

Why after the contest my rating was up, and after 2 hours it was resumed to the previous state?

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

Плохой раунд, ИМХО

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

RIP my rating. I was racking my brain trying to figure out a counterexample to my heuristic for B but turns out it was just a simple off-by-one bug.

Also had no luck figuring out the number theory required to solve C analytically, and missed the brute force solution.

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

Editorial ?

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

why Y can be atmost W-1 in problem C ?

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

Can somebody help me, why am i getting runtime error ? https://codeforces.me/contest/1244/submission/62522364

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

C was the only problem out of 7 I couldn't solve myself. Maybe once I will start reading all statements and won't stay on 1 for the whole round :P

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

Editorial, please?

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

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

    I took a lot of time thinking about C and later started solving D. When I finished the code, I saw: "Contest has ended. Thanks for your participation." :'(

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

    Relatable.

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

    Meh, graphs are a weakness for me. E though, I thought I had a chance of solving, but I kept failing at pretest 13

    edit: And it turns out it's an integer overflow bug. I'm just off my game this round

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

When the editorial will be avialable? C very interesting problem:)

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

How to solve Problem C using Linear Diophantine Equation?

Specially after finding x,y by using Linear Diophantine Equation how to maintain x+y<=n?

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

the most difficult problem for me was C, without it or putting it as the last one, the contest could have been a good div3

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

Thanks a lot.The time is friendly to Chinese.And no DDOS attack

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

Since when does E div 2 can be solved using greedy only?

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

why G problem is not that much hard ?

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

My English is not good...

In fact problem C is not as hard as you think,you don't need "exgcd" to solve solution.

Chinese solution

you see, $$$1 \leq d < w \leq 10^5$$$ .

Greedy, $$$w>d$$$ ,so we can make $$$x$$$ bigger,and you can implementation $$$d$$$

code:


#include<bits/stdc++.h> #include<iostream> #include<cstdio> #define ll long long using namespace std; ll n,p,d,w,x,y,z; int main(){ cin>>n>>p>>d>>w; while(y<d&&(p-w*y)%d) y++; if(y==d) return printf("-1")&0; x=(p-w*y)/d; z=n-x-y; if(x>=0&&z>=0) printf("%lld %lld %lld",x,y,z); else printf("-1"); return 0; }
»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I felt that the ordering of difficulty of questions in this contest was: A<B<D<F<E<G<C.

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

I should have gave up C to have a look at problem E QAQ

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

How to solve E?

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

Hi can anyone please tell me why my solution for D Problem keeps getting Memory Limit Exceeded Verdict ? 62615746. Thank You