fcspartakm's blog

By fcspartakm, history, 5 weeks ago, translation, In English,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #592 (Div. 2). It'll be held on Sunday, October 13 at 12:05 MSK. Note that round starts in the unusual time!

The round will be rated for the participants with rating lower than 2100. The statements will be available in Russian and English.

This round is held on the tasks of the regional stage All-Russian Team Olympiad of Informatics 2019/2020 year in city Saratov. The problems were prepared by Ivan BledDest Androsov, Vladimir Vovuh Petrov and me.

Great thanks to Ivan isaf27 Safonov for helping in preparing the contest, to Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platform and to Ivan CaseRuten Khudoshin, Ivan Ivan19981305 Georgiev, Leonid Peinot Mironov, Anton anon20016 Lebedev, Ksenia Pavlova Pavlova and Dmitriy dmitrii.krasnihin Krasnihin for writing solutions.

You will be given seven problems and two hours to solve them. The scoring distribution will be published soon. Good luck everyone!

UPD The scoring distribution 500-1000-1500-1750-2500-2500-3000

UPD Editorial

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

»
5 weeks ago, # |
  Vote: I like it +125 Vote: I do not like it

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

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

Too early, again... But i_love_Vovuh

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

unusual time!

»
5 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

A friendly time to Chinese.

Hope this round will no DDOS.

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

    Yep,but for me it is a right time to have supper,so maybe I'll be hungry solving the problems.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +138 Vote: I do not like it

    Even I'm Chinese, I still want the round to be later. The darkness has given me dark eyes, but I use them to find bugs.

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

    Thanks to the time,I can participate for an official contest after a long period of time.

    Thanks to the contest writers.

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Short problem statements, please!

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

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

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Hope this round will be no DDOS attack.

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    You can simply just open the "Complete Problemset" page!

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

      I was not familiar with this "Complete Statement" option.

      Thnx Bhi.

»
5 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Wish me good rating

I wish you all too.

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Score distribution?

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

The Saratov olympiads are popular on Codeforces :)

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

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

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

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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it
    int t, n;
    string room;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        cin >> room;
        bool in = false;
        for (int i = 0, j = room.size() - 1; i <= j; i++, j--, n--) {
           //cout << "i: " << i << " j: " << j << endl;
           if (room[i] == '1' || room[j] == '1') {
             cout << n * 2 << endl;
             in = true;
             break;
           }
        }
        if(!in) cout << room.size() << endl;
    }
    
»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

What on earth is test case 5 for C

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

    :(

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

    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 weeks ago, # ^ |
    Rev. 2   Vote: I like it +35 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

      I am getting correct answer on your case, but still wa on 5 :(

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

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

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

        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 weeks ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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 weeks ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

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

      Really nice I was really confused about how to solve that diphonite equation.thanks mate

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

      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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Thank you for the easy-to-understand explanation!

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

      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 weeks ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        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 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

What is Approach for C??

»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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

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

    Diophantine equations i guess.

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

      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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

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

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

            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 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yeah, this is not a good way.

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

              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 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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 weeks ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                hey guys what about this solution xw+yd = p , x+y+z = n, so (w-d)x = d*(p-n)+z , we know that w-d > 0 must
                d*(p-n) + z > 0 , x = (d*(p-n) + z )/(w-d)
                we know x will integer so z = (d*(p-n))%(w-d);
                then x = (d*(p-n) + z )/(w-d) ; y = n -y — z;

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

                  sorry i just have made the wrong equation

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

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

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

      same here but could not cross test case 5

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +7 Vote: I do not like it

        try this test: 4 7 3 2

        answer: 1 2 1

        your answer might be: -1

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

          i've got WA 5 too.

          tried it but my aswer is 1 2 1

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

          No, my solution gives 1 2 1 but failed at test case 5.

          Edit: Overflow seems to be the issue.

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

            Overflow was not an issue, I used big integer library and diophantine function still it did not cross test case 4.

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

              i think that the case 4 is not about overflow

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

          me,too. my answer is also 1 2 1 but I failed.

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

      Same here. Stuck on test case 7.

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

    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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    brute force would work cuz small contraints on w or d

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

      I used brute force but got TLE on test 66

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

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

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

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could you explain your approach ??

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

        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 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          sam4i40 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 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please explain your approach?

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

    well let i be the win count then draw cound d would be = (Points — i * winPoint) / drawPoint ....(1)

    we know drawCount + winCount >=0 && drawCount + winCount <= totalGames

    substitute result (1) into the condition and you will get the minimum win count and maximum win count now all you need to do is find a value in this range such that (Points — i * winPoint) is divisible by drawPoint and that's the answer.

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

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

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Was E not a greedy solution?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +19 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

        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 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you please explain with a very small example?

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

          How can you be sure that the min/max number will always be present in the original array ? Since you are assuming a[i] to be min/max element.

          Can you please explain in detail ? I saw your code, but didn't get it.

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

    I guess, E is ternary search within binary search.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    i solved it greedy

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

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

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

»
5 weeks ago, # |
  Vote: I like it +59 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We also need 30 more minutes to submit more problems :)

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

    so is the system testing delayed by 30 minutes or it'll start normally?

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

how to solve C??

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

    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 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

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

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

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

      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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      maybe

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

      should be

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

      Am I right?

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

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

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      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 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    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 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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 weeks ago, # |
Rev. 2   Vote: I like it +96 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

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

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

How to solve D?

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

    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 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This was my first contest. Could only solve A. B and C got wrong answers on pretest :(

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

    me too. i used a formula that involves max to solve b. i failed. haven't touched c, my heart is too broken to solve it. d, e, f are out of my realm of knowledge.

    i fucked up bad. can you, a fellow failed contestant, console me?

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

What's the approach to solving E?

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

    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 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      can you please explain with a small example?

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

        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 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks, Now the approach is clear to me.

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

          Geothermal Nice approach, I came up with same solution but messed up implementation. two pointers implementations are tough for me :(

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

      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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have understood the greedy solution, I am wondering, can we apply binary search to the problem E?

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

what's the pretest 8 in E ? my program received wrong answer. https://ideone.com/DxJoFl

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

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve problem C using binary search?

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

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

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

      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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried binary search for both x and y... bot got WA on test 5 :\

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

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 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

D was very interesting problem, how to solve it?

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

    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 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

RIP testcase 5 for C

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

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem C really difficul with me :((

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

What is pretest 8 for E??

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

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't solve problem A

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

Great round, make more rounds like this!

»
5 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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 weeks ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    ??

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

      What @maxorand implies is not that he can't solve the problems, but that he thinks that the problem are too easy (too many problems with the difficulty of a Div2 C).

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

    +1. DEF are all at same level.

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

C is more difficult than D, E and F.

Unfortunatly did read E and F after contest :/

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I think you misread E. E was not easy

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

      You are right, implementation is not that simple as I thought first.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

    You dont need it. You can just brute for all number of draws < W. (1e5)

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

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

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

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

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

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

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

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

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

Wow!!!!! Problem C is really strong. Before system testing,my rank is over 1000,but after my rank became 800+. What a clever choice to give up C!

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

what is pretest 6th in d??

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

    It seemed to be a very large answer. At first,I got a Wrong Answer at the 6th pretest. And then I found my intial value of the answer is too small. So I make it 10^15,then I passed pretests. Hope this can help you.

»
5 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Loved the contest!

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

what is the core logic behind F?

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

    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 weeks ago, # |
  Vote: I like it -37 Vote: I do not like it

Excuse me... Why my code get skipped?

»
5 weeks ago, # |
  Vote: I like it -43 Vote: I do not like it

The problems of this round are sooooooooooooo hard to implement!

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    p <= 1e17

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

    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 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Editorials?

»
5 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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

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

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 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks

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

      What's the idea/observation behind this specific solution? I understood till the line " p /= g, d /= g, w /= g; "

      What's happening after that?

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

          Thanks

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

          Okay, I have one more question. Does it ensure that x+y will be minimum as I can see you've checked for the only root found from the modInv? Otherwise shouldn't I be looking around for other roots?

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

            I guess it is minimum. Since $$$d < w$$$ and we must use either $$$wx$$$ or $$$dy$$$ to "fill" $$$p$$$, it seems to be optimal to use the smallest possible $$$y$$$.

            And there should only be one $$$y$$$ under $$$w$$$.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Found a blog-post to overcome the overflow including proof on the comment section. Works fine for this problem as well. Avoid overflow in linear diophantine equation

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    You can use this BigInt struct.

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

???? My rating is lost???

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

    Me too, there may be some technical problems.

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

      :((( the first time I become expert :<<< so sad.. may be it's unrated :(

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

    Everyone's rating history is lost, as I am not able to see anyone in rating lists. Something wrong with the system.

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

    It's back :D

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

How to solve E?

»
5 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Oh my god , is this round unrated ?

I'm a step away from the master .

»
5 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

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

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

someone, please help why is this wrong for 627936103814 4254617095171609 45205 1927

my output = 70349468271 557586601962 33581

x+y+z = 627936103814

the given answer is 94118284813 15672 533817803329

in C problem

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

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    If y == w, we can say that we won d matches (y == w -> y*d == w*d)

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

      I can't understand.

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

        If y=k*w+r and x=x0 — solution, so: y=r and x=x0+k*d — solution too, because: r + (x0+k*d)<r+x0+k*w<=n (This thing reminded me about Pell's equation xD)

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

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorial, please?

»
5 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

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

    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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Relatable.

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

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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 weeks ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Once you form equation for x = x1 - k*b/gcd(a,b) and y = y1 + k*a/gcd(a,b). x1 and y1 are two coefficient you get from extended euclid algo. Check which one is negative x1 or y1. From that you can derive one inequality k>=c1.

    Now known x+y <= n. Plug in equation of x and y in that. Only unknown in that equation is k. Solving this inequality will give you something like k<=c2.

    All values of k will give you one answer which satisfy above two inequaliteis. k>=c1 and k<=c2

    PS: This answer helped me understanding solution for Diophantine Equation. https://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c?rq=1

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

      How can you be sure that there(x1 & y1) will always a negative value?

      And what is c1 and c2?

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

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

why G problem is not that much hard ?

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

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 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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

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

How to solve E?

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

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

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

tutorials?