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

Автор cry, 8 месяцев назад, По-английски

Thank you for participating! We put a lot of effort into this contest. Special thanks to TheScrasse for contributing to these problems.

Rating Predictions

Solutions

1942A - Farmer John's Challenge

Problem Credits: buffering
Analysis: buffering

Hint 1
Hint 2
Hint 3
Solution
Code (C++)
1942B - Bessie and MEX

Problem Credits: buffering
Analysis: buffering

Solution 1

Hint 1
Hint 2
Solution
Code (C++)

Solution 2

Hint 1
Hint 2
Solution
1942C1 - Bessie's Birthday Cake (Easy Version) and 1942C2 - Bessie's Birthday Cake (Hard Version)

Problem Credits: cry
Analysis: cry

Solution (Easy Version)
Solution (Hard Version)
Code (C++)

1942D - Learning to Paint

Problem Credits: sum
Analysis: sum

Hint 1
Hint 2
Solution
Code (C++)

1942E - Farm Game

Problem Credits: cry
Analysis: sum

Hint 1
Hint 2
Hint 3
Solution
Code (C++)

1942F - Farmer John's Favorite Function

Problem Credits: sum
Analysis: sum

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)

1942G - Bessie and Cards

Problem Credits: smax
Analysis: smax

Hint 1
Hint 2
Solution
Code (C++)

1942H - Farmer John's Favorite Intern

Problem Credits: oursaco
Analysis: oursaco / rainboy

Solution 1
Code (C++)
Solution 2
Code (C++)
  • Проголосовать: нравится
  • +143
  • Проголосовать: не нравится

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

Thanks for the Lighting fast editorial

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

    ah you beat me

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

      It's a luck Sir

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

        I don't understand. How do all of your comments get downvoted? They seem like pretty normal comments to me.

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

          Because the original comment is unnecessary + kind of a cheeky way to exploit a human bias and get some upvotes.

          The downvotes on the reply are mostly continuing the process of "punishing" the same guy. Maybe punish is a too strong word, rather discouraging by means of downvoting is the correct expression.

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

    Bro you're everywhere lightning fast

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

second :(

C was pretty tough imo

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

How can you proof in F (the n>=6 observation)?

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

    Since $$$a_i$$$ are bounded, I just bruteforced inserting bunch of 1e18's to see how far it propagates

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

    Maybe it is the fact that the 64th root of $$$10^{18}$$$ is less than 2.

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

    Because $$$\log_{2}\log_{2}n<6$$$.

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

    I'm very disappointed with the editorial writers for not including this proof.

    The most straightforward proof is obtained by considering the image of function $$$f(i, x)$$$ — the answer after considering $$$i$$$ elements, if $$$a_1 = x$$$.

    $$$|f(i, [L; L + len])| <= |sqrt(len)|$$$.

    This can be shown using the inequality $$$sqrt(a+x)-sqrt(x)<=sqrt(a)-sqrt(0)$$$, this is because sqrt is a concave function, this is a very intuitive claim, you can kind of guess this by looking at the sqrt(x) plot.

    With this we can show that $$$|f(i, [0; 10^{18}])| <= 10^{18/2^i}$$$.

    However this isn't a complete proof as the RHS will approach 1, but never actually reach it so it could be that $$$f(0) = x-eps, f(1) = x, f(10^{18}) = x+1$$$.

    Let's say we already know that f(i, x) takes only 3 values, the thing is either $$$\left \lfloor{\sqrt{x}}\right \rfloor = \left \lfloor{\sqrt{x+1}}\right \rfloor$$$ or $$$\left \lfloor{\sqrt{x+1}}\right \rfloor = \left \lfloor{\sqrt{x+2}}\right \rfloor $$$, so $$$f(i+1, x)$$$ will only take 2 values.

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

      or, more simply, we have that

      $$$a+b\le a+b+2\sqrt{ab}=(\sqrt a+\sqrt b)^2$$$

      $$$\implies\sqrt{a+b}\le\sqrt a+\sqrt b$$$

      $$$\implies \sqrt{a+b}-\sqrt b\le\sqrt a.$$$

      Then $$$\sqrt{c+\sqrt{b+a}}-\sqrt{c+\sqrt b}\le\sqrt{\sqrt{b+a}-\sqrt b}\le\sqrt{\sqrt a}=\sqrt[4] a.$$$

      This extends similarly for more nested radicals. Thus, increasing $$$a_i$$$ by $$$x<10^{18}<2^{64}$$$ will only affect $$$f(i+6)$$$ by at most $$$\sqrt[2^6] x =\sqrt[64] x<2,$$$ the desired result.

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

I created video editorial for D: Learning to Paint

Practice Problem for building intuition for problems like today's D: Learning to Paint

I have added hints and thought process for D on CF Step.

Practice Problem for learning the technique of merging k-sorted list.

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

Man problem C was mega sexy... during contest it just gave my skills a serious reality check

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

B can also be solved backwards using the observation that the prefix mex is equal to the suffix min. This idea also appeared in the Cyclic Mex problem recently.

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

    It took me 90mins to solve B :(

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

    can u explain more this idea ? the prefix mex is equal to the suffix min

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

      If you have a sequence from 0 to n-1 (say). Then for any prefix of this sequence the mex will be the minimum element in the remainder of the sequence(suffix).

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

    could you please explain " mex = min(mex, p[i]) " this line in your code. why we will take minnimum value betwenn mex and p[i] as a new mex value ?

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

      A permutation contains all values from $$$0$$$ to $$$n - 1$$$. The definition of Mex is the first non-negative missing integer. If you consider the $$$i-th$$$ prefix, then which elements are missing from this prefix? All elements in the suffix $$$p[i + 1], \dots p[n - 1]$$$ are missing from it. By definition of mex, the minimum missing element should be the mex.

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

Can someone please explain the problem statement of D ?

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

    You can choose some subset of integers on $$$ [1, n] $$$. The beauty of a subset is equal to the sum of scores of each maximal contiguous subarray of selected elements (e.g. you cannot extend the subarray more to the left or right). A score of a subarray $$$ [l, r] $$$ is given by $$$ a_{l, r} $$$. Find the $$$ k $$$ greatest beauties possible from the $$$ 2^n $$$ possible subsets (including duplicates).

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

    I don't understand the statement of D either......

    It's like they don't want you to comprehend it :<

    they could've made it more clear in the Input or testcases description:(

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

      I take back my words. I found it a lot more comprehensible after reading others comments.

      Now it's simply that it is difficult:)

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

So many formulas in G :(((. Had the idea but probably bugged something there. Anyway, great problemset. It's funny that the "game" that problem E reduces to (by a series of really nice observations I'd say) (the game being subtract 1 from some number of piles) and the "paranthesis problem" that G reduces to both appear on cses in the problems Another Game and Bracket Sequences 2.

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

By looking at $$$f$$$ as a big integer in a weird changing base, F can be quite easily solved with a modified version of a Trygub Number (Big integer with negative digits)

254189455

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

Quoting problem E's editorial:

The number of ways to place the cows in the available positions given the gaps will be $$$2 \cdot {l - s - n \choose n}$$$.

Pardon me for being in the dark but why is this true? I thought it should be $$$l - s - 2n + 1$$$, since for each known set $$$(g_1,g_2,...,g_n)$$$, isn't it that the area of cows and inner gaps forms a solid block of $$$2n + s$$$ cells, and we would just need to find the starting place to put that block in?

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

    We are placing the location of each g, so each g counts for one space while choosing locations, which contributes a total of n, so it will end up being l-s-n at the top

    I am not sure where your +1 comes from

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

      Wait a second, I got why I was wrong. My claim up above would only secure that $$$b_i - a_i = g_i + 1$$$, yet wrongly assume $$$a_{i+1} - b_i = 1$$$, which is not always the case.

      Thanks for your help!

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

I could not solve beyond problem A. :(

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

    Yeah bro I coud not even solve problem A. Forgot there was a contest :(

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

    Happens, :)
    Div.1+2 can be somewhat overwhelming to beginners, try some Div.3 problems, or AtCoder Beginner Contests.
    Also, given the length/duration of the contest, if you didn't solve A, do reassess your approach. Did you play around with some small testcases to see patterns? Looking at the editorial, what could you have done to notice things sooner, etc.

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

      I was able to solve problem A. But could not solve Problem B.

      I tried to make some observations, but the concept of MEX was somewhat new to me. I only know what it does, not fully studied it's other details+implementations.

      I do plan to upsolve and go through the editorial tomorrow.

      Thank you.

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

      Can you explain the time complexity of B if there is a while loop for increasing mex?

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

        Consider the outer for loop.
        For any given $$$i$$$, there would be at most 1 while-check for has[mex] that yields false (stopping the while loop).
        Also, consider the number of times that the while-check for has[mex] can be true over all $$$i$$$ in total? It is also bounded by $$$n$$$, as any time the check is true, mex increases, and mex can only go up to $$$n$$$.
        Thus, overall, the contribution of the considered while loop is $$$O(n)$$$

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

        also think that the while loop doesn't start each time from the beginning it will continue from where it stopped before so the whole complexity will be N+N

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

        You can also create a set containing the numbers 0 through $$$n$$$, and after using a number, delete it from the set. Set's first element will be the current MEX.The total complexity of these operations will be $$$O(n log n)$$$. Because set operations are $$$O(log n)$$$.

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

For problem C (hard):

I think it should be "whether $$$g$$$ is odd oe even, we can choose $$$\lfloor\frac{g}{2}\rfloor$$$ vertices to make $$$g$$$ extra triangles."

For example, for a pentagon, if we have chosen $$$a=1$$$ and $$$b=5$$$, in which case $$$g=3$$$, then we can choose $$$\lfloor\frac{3}{2}\rfloor=1$$$ vertex ($$$3$$$) to make $$$3$$$ extra triangles ($$$123$$$, $$$135$$$, $$$134$$$). For a hexagon, if we have chosen $$$a=1$$$ and $$$b=6$$$, then we can choose $$$2$$$ vertices($$$3$$$ and $$$4$$$) to make $$$4$$$ extra triangles ($$$123$$$, $$$134$$$, $$$146$$$, $$$145$$$).

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

    I wasn't counting the first case, solely the second case where the extra triangle shares one side with the $$$x$$$-polygon and two with the outer.

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

My solution on problem D is kinda different and I have no idea why it works

Basically you do as editorial says: dp[i] stores the best k values among the prefix [1...i]

The bruteforce approach: iterate through the previous lists and see if you can get a better list by binary search. You are changing the last p values with the first p values and then you sort the list

The optimized version: instead of doing for every index the updating, you are inducing a order to do so: sort them by the best value of list j + current cost induced by the ith element. And then you do like the bruteforce approach.

I don't know if the tests are weak. It is 2-3 times slower then editorial approach.

254190056

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

Can anyone explain the time complexity for the B solution code? How does iterating over the HAS array impact the overall time complexity?

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

    it's O(n) as we are traversing each element of P and has array only once

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

      Can you please explain ?

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

        as variable mex is all increasing you are going each index of has array only one. sorry i cant explain better than this may be you read this or watch some tutorial about time and space complexity

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

A reminder to focus more on geometry .

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

Thanks for an Amazing round and a wonderful tutorial, Can someone help me with my code in problem D, I believe I have the same idea with very similar complexity O(nk log(k)). However, it got TLE and I can't figure out why... Here's my submission: 254196468

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

    Your complexity is $$$O(N \cdot k^2 \cdot log(k))$$$.

    For any index $$$i$$$, you are iterating over all $$$j < i$$$, which contributes $$$O(n)$$$.

    For each each index $$$j$$$, you are iterating over its complete multiset, which contributes $$$O(k*log(k))$$$ for each such $$$j$$$.

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

      Oh, thanks, do you have any idea how to speed it up?

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

        Yes, it's a famous interview problem. Given $$$k$$$ sorted lists, how do you merge them?

        The trick is to insert the indices of all the lists in a max heap, with a custom comparator that assigns highest priority to the index with the highest $$$a[ind]$$$.

        Then, you pop $$$k$$$ times from this modified heap. The time complexity is now $$$O(k*log(k*n))$$$

        Standard Problem Link

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

          Thank you, thank you, I'm both glad for almost having the solution and disappointed for missing it for a standard problem. Thanks again

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

      Almost the same code, What a miss! 254211857

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

    Just to clarify the process my solution goes with:

    1- I assumed there's a source vertex 0 and a sink vertex 2*n+4

    2- I assumed each node has two copies one that can start a segment and one that can end a segment, and the edges from nodeStart to nodeEnd have costs from the 2d array A.

    3- Now we DFS from the vertex and calculate the DP of the highest K paths to the sink.

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

I probably found the most interesting sol for the Question A, even idk why i did it -_- ;) ----------------------254136686--------------------------------------------------------

include

include

include

using namespace std;

void solve() { int n,k; cin>>n>>k; int arr[n]; int res=1; if(k==1||k==n){ for(int i=1;i<=n;i++){ arr[i]=res; // cout<<res<<" "<<i<<endl; if(i%k==0){ res++; } } for(int i=1;i<=n;i++){ cout<<arr[i]<<" "; }cout<<endl; }else{ cout<<-1<<endl; }

}

int main(){ int t; cin >> t; while (t--) { solve(); } return 0; }

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

lol I misread and tried to solve G for cards of types 1, 2, 3 instead of 0, 1, 2

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

    lol, then the probability of winning is 1, b/c everytime you play a card you draw some of them instead of that one.

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

      now I realize I even missed the first free 5 cards xD my game starts with just 1 card and she'll lose in cases like "1 1 1 special" or "2 special special" xD

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

Did 3 after a long time.. :)

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

Loved problem C1 & C2.... thanks for such a beautiful question :)

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

Hello everyone, I used a weird algorithm to solve Problem D. 254165883

I believe that my solution is wrong since that it should have $$$O(n^2*k*log(k))$$$, but I used a trick to speed it up. I guess that there is certain hack input, but it is really hard to construct. I failed to construct a sample data to hack myself. Can somebody help me to do that? Thanks!

PS: Can somebody tell me how to insert collapsed code blocks? I think my code may be too long here.

    for (int i = n; i >= 1; --i) {
        //  dp[i + 1][1:k] -> dp[i][1:k]
        while (!PQ.empty()) { PQ.pop(); }
        for (ll x : dp[i + 1]) { PQ.push (x); }
        for (int j = i; j <= n; ++j) {
            while (PQ.size() > k) { PQ.pop(); }
            for (ll x : dp[j + 2]) {
                if (PQ.size() < k) { PQ.push (a[i][j] + x); }
                else {
                    if (PQ.empty() || a[i][j] + x > PQ.top()) {
                        PQ.push (a[i][j] + x);
                        if (PQ.size() > k) { PQ.pop(); }
                    } else {
                        // a[i][j] + x <= PQ.top()
                        // I believe that this following line is the trick helps me speed up my wrong solution
                        break;
                    }
                }
            }
        }
 
        while (!PQ.empty()) {
            dp[i].push_back (PQ.top());
            PQ.pop();
        }
        sort (dp[i].begin(), dp[i].end(), greater<ll>());
        if (dp[i].size() > k) { dp[i].resize (k); }
  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится +110 Проголосовать: не нравится

    Hacked with $$$a_{i, j} = w_i + w_{i+1} + \ldots + w_j$$$, where $$$w_i = n - i$$$ is the weight of cell $$$i$$$.

    This way, the beauty of a painting is just the sum of weights of individual painted cells. In the best paintings, a long prefix of cells should be painted. And as you go in increasing order of $$$j$$$, you discover better and better solutions, substituting the previously found ones.

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

      Out of curiosity, I tried something awfully similar but with randomly shuffling previous j values before iterating on them. Is it possible to make a test that TLEs on my solution?

      Solution: 254452137

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

    I believe I did something very similar to your approach and it passed: 254663089. Not exactly sure why this still passes after your submission was hacked.

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

Nice problemset, thanks!

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

Can someone please help me to understand why my code is failing on the 30th test case in test 2 in the problem C2:

#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n, x, y;
	cin >> n >> x >> y;
	vector<int> a(x);
	for(auto &i: a) cin >> i;
	sort(a.begin(), a.end());
	int ans = 0, z = 0;
	for(int i = 0; i < x; i++) {
		int p = abs(a[i]-a[(i-1+x)%x]); // gap between two vertices a[i] and a[i-1]
		if(i == 0) p = n-p; // a[0]-a[n-1] handled separately
		if(p == 2) ans++; // if it forms a triangle 
		else if(p > 2) {
			int q = min((p-1)/2, y); // minimum of points that I can add(y) and points that are available between a[i] and a[i-1] (gap size-1)/2 
			z += q; // added points count increase
			ans += q; // equal number of triangles formed 
			if(q*2+2 == p) ans++; // gap(p) == 2*q + 2 means an additional triangle can be formed, this is an edge case
			y -= q; // added points count decreased from available points
			y = max(0, y); // if y has not become negative 
		}
	}
	z += x; // z vertices added, x was initially
	while(z >= 3) {
		ans += z/2;
		z -= z/2;
	}
	cout << ans << "\n";
}

int main() {
	int T = 1;
	cin >> T;
	while(T--) solve();	
}
»
7 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

pleasae help me debug hard C https://codeforces.me/contest/1942/submission/254210357(nvm found the bug %2 was missing)

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

I believe my solution to D is $$$O(n^2+k)$$$. It uses Eppstein’s algorithm.254149567 (implementation from this blog)

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

Rating predictions are actually pretty accurate

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

cry
Can you provide the test cases for problem C2, I need test 2
My code fails at 30th test case in test 2

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

    In your code, it seems that you just process the distances one by one. You have to process the even distances from small to large, and then the odd distance from small to large. Please try the follow test case (not official):

    1
    80 8 2
    1 12 23 34 45 49 53 57
    

    Answer: 12, Your output: 10

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

      Thanks buddy, after I read the editorial I figured it out that I didn't spend time thinking about the difference odd and even creates just simply went with the solution, thanks!

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

can someone explain problem B in a little bit more detail please ?

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

    U have to set a[i] = MEX(p1, p2,...,pi) - p[i] according to the problem statement
    Rearrange it, p[i] = MEX(p1, p2,...,pi) - a[i]

    for each index i, you have two options:-

    p[i] = MEX till index i-1

    Spoiler

    p[i] != MEX till index i-1

    Spoiler

    My code implementation:-

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

      how did we come to a conclusion that mex will increase whenever there's a positive element coming and in case of negative it remains same..

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

        There are only 2 things the MEX can do: increase or stay the same (it can never decrease since we are looking at larger and larger prefixes).

        In the case of a positive difference, if the MEX stayed the same then it would have to be greater than the current value, which is impossible because that value had to appear earlier on in the prefix. Since the MEX is calculated on a permutation that can’t happen. So it has to increase.

        In the case of a negative value, the MEX has to be less than the current value. But if it increased that means the current value changed its MEX, meaning its new MEX is at least (current value + 1) and it is actually greater. So it has to stay the same.

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

      u mean a[i] instead of p[i] right ?

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

    Hmm, I wrote a proof for the last line in the editorial: "you can show that P is unique," but I think a lot of that proof helps you understand the original problem too: https://codeforces.me/blog/entry/126942#comment-1135215.

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

In A's solution: For k=1, the construction 1,2,3…n will always work because in any other cyclic shift, 2 will be before 1.

It should be n will be before 1.

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

I solved C1 and was so happy for solving 3 problems only to discover after the contest that B got TLE. The phrase "If there are multiple possible p, it is enough to print one of them" confused me, so I made solved it using backtracking instead of a straight forward approach. I wish we had stronger test cases during the contest.

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

    Very sad and unfortunate. But you should also be a bit self-critic as well. It's not a super complicated instruction!

    In any constructive solution providing problem, of course it's possible to have multiple ways to do a task (construct an answer), and the question should come to your mind naturally that should I find all of them, or only one? If one, which one? In this problem, it was generous as you can print any of them. In some other problems, you are asked to print the lexicographically smaller/larger one (string) or in ascending manner (array of numbers) or has the highest sum over all possible solutions or some other constraints.

    Take this as an experience. Good luck!

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

I solved B in a peculiar way (probably). Let's define $$$mex_{i} = mex(p_1,...p_{i})$$$. Also, notice that at no point, $$$p_i < mex_{i-1}$$$ can be true because that number is already present in the $$$P$$$ array, $$$mex_{i-1}$$$ being larger than that is the evidence to that.

Case 1: $$$a_i = 1$$$. Imagine how $$$a_i$$$ can be $$$1$$$.

  • Case 1a: $$$p_i = mex_{i-1} - 1$$$. This way, $$$mex_{i}$$$ will stay the same as $$$mex_{i-1}$$$. But by the contradiction mentioned above, $$$p_i$$$ can never be smaller than $$$mex_{i-1}$$$.
  • Case 1b: $$$p_i$$$ has to be equal to $$$mex_{i-1}$$$, which will increase the $$$mex_{i-1}$$$ by $$$+1$$$ or more. But as it is guaranteed that valid $$$P$$$ exists, it will always get increased by $$$+1$$$. Otherwise $$$a_i$$$ cannot be $$$1$$$.

Case 2: $$$a_i \neq 1$$$.

  • Case 2a: $$$p_i \neq mex_{i-1}$$$. So $$$mex_{i} = mex_{i-1}$$$, making $$$p_i$$$ to be $$$mex_{i-1} - a_i$$$.
  • Case 2b: $$$p_i = mex_{i-1}$$$. If the previous case fails (results in an invalid $$$p_i$$$ such as negative or already taken), take this option.

It can be proved that under no circumstance, both approaches of 2a and 2b both can lead to valid $$$p_i$$$ for the same $$$a_i$$$. If this has to happen, 2a wants $$$a_i$$$ to be $$$mex_{i-1} - ?_{p_i}$$$ (some mysterious value for $$$p_i$$$), whereas 2b wants $$$a_i$$$ to be $$$mex_{i} - mex_{i-1}$$$ has to hold. For them to be equal, $$$?_{p_i} = 2 \cdot mex_{i-1} - mex_{i}$$$. But $$$mex_{i} > mex_{i-1}$$$, making $$$p_i < mex_{i-1}$$$ (again contradiction).

Thus, initializing a $$$mex$$$ variable with $$$0$$$, I read a number from $$$a$$$ and chose appropriate value for $$$p$$$. Need to maintain $$$mex$$$ variable properly. Complexity $$$O(n)$$$.

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

D accepted solution in $$$\mathcal{O}(n^2k)$$$ in C++20 254217379

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

can u explain more why if ( a[i] >=0 ... and the other way ... ) ?

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

    why mex should increase if a[i] >= 0 ? and why should stay the same in the other case

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

      if p[i] == mex 1 -> i-1 !

      a[i] = mex till i — p[i] !

      mex till i = p[i]+1 ?

      a[i] = 1 !!!!

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

      if a[i] >= 0 then mex(p1, p2, ..., pi) - p[i] >= 0 or mex(p1, p2, ..., pi) >= p[i]. But mex(p1, p2, ..., pi) can not be equal to p[i] (by definition MEX is an element not contained within the set). So mex(p1, p2, ..., pi) > p[i]. If the mex(p[1]...p[i-1]) = m (meaning the first i-1 elements in p had all the elements from 0 to m-1, and some greater than m(probably). Now when p[i] was added, the mex could either stay the same or increase. But if mex stayed the same it means p[i] is larger than m in which case mex(p[1] ... p[i]) - p[i] will be less than 0 (a contradiction). If you are thinking we might put p[i] as something smaller than m in the case mex does not change, then it is not possible since p is a permutation and all elements from 0 to m-1 is already a part of p.

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

Liked rating predictions idea , hope to see it each contest

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

Alternate Solution of D (Editorial's implementation is much simpler than this):

Maintain $$$dp[i]$$$ as mentioned in the editorial. Now for finding $$$dp[i]$$$, we can do binary search on the lowest value of the top $$$k$$$ elements. It can be easily done by counting the elements which will be greater than current $$$mid$$$ value, if the value is $$$>= k$$$, then $$$mid$$$ can be the possible answer.

Now we have got the lowest value of the top $$$k$$$ elements (let's call is $$$mn$$$), now to find all the possible values, we will take all the values $$$>= mn + 1$$$, whatever count is the remaining from top $$$k$$$ elements, append $$$mn$$$ that many times. Sort it and proceed.

Note : For smaller indices you can do brute force so that atleast $$$k$$$ possible combination of values can be obtained.

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

F is really nice! I did similar idea as editorial, but instead i first imagined bsearch working backwards then divided into blocks put in segment tree working backwards same way. Solution here.

Why is hint 3 possible?

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

    Also, I liked C and D quite a bit too :). A/B filler, E is math garbage tho.

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

    you are so awesome!could you teach me what should i do to be as good as you !

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

    This is because $$$\lfloor \sqrt{a+b} \rfloor = \lfloor \sqrt{\lfloor a\rfloor+b}\rfloor,$$$ when $$$b\in\mathbb{Z}$$$

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

can someone please explain why this $$$O({n^2})$$$ of mine works for Bessie and MEX problem

Submission

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

why this code is giving run time error and the logic is correct right anyone help me please?? submission link

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

    array p is so short that space limit is exceeded but it also wrong when i correct it . so,what are you facking coding ?

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

what can i say? how to solve D

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

I have another solution in $$$O(n \log n)$$$ for problem B.

Using this equation: $$$p_i = \mathrm{MEX(p_1,\dots, p_i)} - a_i$$$ We can test with the possible values of $$$\mathrm{MEX}$$$ in the current permutation. $$$\mathrm{MEX}$$$ always will have 2 possibilities:

  1. The actual $$$\mathrm{MEX}$$$ of the permutation, define this as $$$\mathrm{fmex}$$$.
  2. The $$$\mathrm{MEX}$$$ if we insert $$$\mathrm{fmex}$$$ into the current $$$p$$$

So, one of the possibilities will be invalid (Go out of valid values of $$$p_i$$$), so we must pick the valid possibility. We can store a copy of $$$p$$$ to simulate the second possibility, I used this implementation that allow us to get $$$\mathrm{MEX}$$$ queries in $$$O(\log n)$$$, we must precalculate the initial array $$$p$$$ in $$$O(n\log n)$$$.

This is the submission 254239126

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

Can someone pls explain the D problem statement, tried reading mutiple times didn't get the question itself

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

Can someone help me out in understanding how sorting in C1 keeps the algo within the time bounds?

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

    Upper limit for x is 2*10^5 so after sorting (Time complexity nlogn) it will be around 10^6 steps. It is well known that in 1 second you can do around 10^7 to 10^8 steps. So it remains within time limit.

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

In Problem B: The code given in solution 1 of the editorial is giving the answer:

0 1 4 2 4 (which is not a valid permutation)

for the testcase:

5

1 1 -2 1 -1

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

    The problem statement says: "The input is given in such a way that at least one valid $$$p$$$ exists." Your input is invalid because there is no answer.

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

How in problem F do we prove that we can consider f(n) be a floored sqrt and there will no be any calculations error?

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

    There is no integer $$$k$$$ such that $$$\lfloor f_{i-1} \rfloor +a_i < k^2 \leq f_{i-1}+a_i$$$, so $$$\lfloor \sqrt{\lfloor f_{i-1} \rfloor+a_i} \rfloor=\lfloor f_{i} \rfloor$$$, we can get $$$\lfloor f_n \rfloor$$$ correctly.

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

MAN,what can I say?

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

In problem D, i did not understand how 2-d matrix came in question Learning to Paint, there are n cells, how are n*(n-1)/2 description given? some one please help me to understand the question

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

    There is one value for every (l,r) where l <= r. Basically the upper triangle of a square

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

in this code for B

void solve() { int n; std::cin >> n;

std::vector<int> a(n);
for (int i = 0; i < n; i++) {
    std::cin >> a[i];
}

int mex = n;
std::vector<int> p(n);
for (int i = n - 1; i >= 0; i--) {
    p[i] = mex - a[i];
    mex = std::min(mex, p[i]);
}
for (int i = 0; i < n; i++) {
    std::cout << p[i] << " \n"[i == n - 1];
}

} why are we doing mex = std::min(mex, p[i]);?

can anyone please explain it

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

    When you add a new element the mex either increases or stay the same If it increases then the number you added to the set was equal to mex, if it stayed the same number you added to the set was greater than mex(since p is a permutation). You know the Mex of the entire array is n. Now you have found out the last element. When this element was added to the set of remaining n-1 elements, it either made the mex increase and which means this last number was equal to the Mex of the first n-1 numbers. If it did not increase the Mex then that means this number was something greater than Mex. That statement is just trying to achieve this:

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

you are so rude cry

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

https://codeforces.me/contest/1942/submission/254169040

Can anyone tell me how to correct this logic. What I am doing wrong how to correct it . Thanks in advance

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

Problems are very interesting and educational!!!

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

For a simpler problem D, when you just have to find the max score, how can we write the transition equation ?

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

can anyone explain me the time complexity for solution 1 of problem B , isn't it n^2 how does it work for 1.5 second time limit?

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

Alternative solution for E (initially I could solve only like this :D):

Let's understand that if we take all the cows in the coordinates $$$x_1$$$ < $$$x_2$$$ < $$$\ldots$$$ < $$$x_{2n}$$$, then the first player will always lose if and only if for each $$$1 \leq i < 2*n$$$, such that $$$i$$$ is odd, the difference $$$x_{i + 1} - x_i$$$ is also odd. Then from all possible ways, we can remove the number of states when the first player will lose and will get the answer.

Let $$$dp[l][n]$$$ be the number of states when the first player loses the game ($$$l$$$ is the length of the x-axis, $$$n$$$ is the number of cows for each farmer).

It's easy to see that $$$dp[l][n] = \sum_{k=0}^{n}{dp[\lfloor \frac{l}{2} \rfloor][k] * dp[l - \lfloor \frac{l}{2} \rfloor][n - k]}$$$. Let's note that the number of different values of $$$l$$$ will be at most $$$2 * log(l)$$$ and the following sum, we can calculate using FFT.

You can easily to see that the complexity of this solution is $$$O(l * log(l) * log(n))$$$, which I guess will not pass TLE, but anyway I decided to share it with you :)

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

The editorial of D , is as poor as it could be.

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

In C1, can someone explain why 254296468 is getting Runtime error on test 6, but 254301491 is accepted. Both are based on same logic.

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

**For problem B, the editorial says, **

Note that there is a way to show that $$$p$$$ is unique

Here's my proof.

AFSOC (assume for sake of contradiction) that $$$\exists P_1, P_2$$$ such that $$$\exists i$$$ where $$${P_1}_i \not= {P_2}_i$$$. WLOG (without loss of generalization), fix such an $$$i.$$$

Proceed by induction.

Base case: any $$$A$$$ such that $$$|A| = 1$$$ and $$$a_1 < 0$$$. No other definition of $$$A$$$ satisfies requirements for problem.

Inductive hypothesis: $$$\forall j < i, MEX({p_1}_1, ..., {p_1}_j) = MEX({p_2}_1, ..., {p_2}_j).$$$

Case on parity of $$$a_i.$$$

Case 1: $$$a_i > 0$$$. $$$MEX({p_j}_1, {p_j}_2, ..., {p_j}_{i-1}) = p_i$$$ for $$$j = 1$$$ and $$$j = 2$$$ because the MEX of a set changes if and only if the new element in the set is the previous MEX.

Case 2: $$$a_i < 0$$$. This means that $$$MEX({p_j}_1, ..., {p_j}_{i-1})-a_i = {p_j}_i$$$ for both $$$j = 1$$$ and $$$j = 2.$$$

Note that in both cases, by the IH (inductive hypothesis), it follows that $$${p_1}_i={p_2}_i.$$$ Since $$$i$$$ was fixed arbitrarily, this follows for all $$$i \in [1, n]$$$ why do CF and other judges insist on 1 indexing :'(

This is a contradiction since we originally assumed that there would exist at least one $$$i$$$ such that $$${p_1}_i \not= {p_2}_i.$$$

Therefore, $$$P$$$ is unique. . Please let me know if there is an error. thanks.

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

C can be solved alternatively by going through the array from back, like for the last element MEX must be n, now you got the last element, subsequently the penultimate element's MEX (MEX(a1,a2,...an-1)) would be Pn since its the only element, not present in the permutation sequence till then, if we go on like this, finding elements from the back, and then exploiting the fact that the MEX(a1,a2,a3,..ai) is min(Pi+1, Pi+2,....Pn)..we can find all the elements of the permutation

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

C is quite easy, isn' t it?

i think it is easier than B

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

What's the O(n^2 + k) solution for D (mentioned in the tutorial) ?

Any hints would be appreciated

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

    Did you find that solution? If not then can this problem be modelled as a Best time to buy and sell stock 4 problem? I have a blog related to a n+nlogk solution posted on codeforces regarding it.

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

How can I make this code better.

Task — C1

while(t--){
    int n,x,y; cin >> n >> x >> y;
    vector<int> a(x);
    for(int i =0; i < x; i++){
        cin >> a[i];
    }
    set<int>st(a.begin(),a.end());
    int ans = x-2;
    for(int i = 1; i <= n; i++){
        if(st.find(i) != st.end()){
            continue;
        }
        int left = i-1;
        int right = i+1;
        if(i == 1){
            left = n;
        }
        if(i == n){
            right = 1;
        }
        if(st.find(left) != st.end() && st.find(right) != st.end()){
            ans++;
        }
    }
    cout << ans << "\n";
}

Time limit exceeded on test 6

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

for the problem E, can anyone help me generate allowed positioning for l=6, n=2? I cant seem to find the positions but the correct answer should be 14. I prefer a notation like "XGOXGO" where,

  • X = cow for farmer 1,
  • O = cow for farmer 2,
  • G = gap

Wrong positions are:

  1. XOXOGG

  2. GXOXOG

  3. GGXOXO

  4. XGGOXO

  5. XOGGXO

  6. XOXGGO

if we flip X and O, then we get another 6. So I found total 12 Wrong positions out of 30 [2 * ncr(6, 4)]. So my answer becomes 18. Which 2 incorrect positions am I missing?

UPDATE: Thanks to a friend, i found out I was missing:

GXOGXO XOGXOG

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

Does anyone know how/when the winners will recieve the prize?

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

In Problem C1, We have a test case 8 4 0. The answer for this test case is given to be 2. But I found a construction giving 3 triangles. If you number the vertices serially from 1-8, then if we connect vertex 1 to vertices 5,6,7 then we get 3 triangles. Please tell me what am I missing. Construction Link

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

PROBLEM.C2: Bessie's Birthday Cake (Hard Version) i had the same logic. i cant doubt if its an implementation issue( WA submission ). but here is my submission: 255822976

#include <bits/stdc++.h>
using namespace std;

#define all(v)     v.begin(), v.end()
#define debug(var) cout<<(#var)<<": "<<var<<'\n'
#define dbcon(v)   cout<<(#v)<<": "; for(auto i: v) show(i); cout<<'\n'
#define fastio     fastip, fastop 
#define fastip     cin.tie(0)  -> sync_with_stdio(0) 
#define fastop     cout.tie(0) -> sync_with_stdio(0) 
#define fe(n)      for(ll e=1; e<=n; e++)
#define line(var)  cout<<(var)<<'\n'
#define ll         long long 
#define show(var)  cout<<(var)<<' '
#define tests(t)   cin>>t; while(t--)



int main() {
	ll t, n, x, y;
	fastio;
	tests(t){
	    cin>>n>>x>>y;
	    
	    deque<ll> a(x);
	    for(ll &i: a) cin>>i, i--;
	    
	    sort(all(a));
	   // dbcon(a);
	    
	    vector<ll> diff(x);
	    fe(x-1) diff[e]= (a[e]-a[e-1]-1);
	    diff[0]= n-a[x-1] +a[0]-1;
	    
	    sort(all(diff));
	    auto cmp= [&](ll a, ll b) {return((a&1) > (b&1));};
	    sort(all(diff), cmp);
	   // dbcon(diff);
	    
	    ll ans= x-2;
	    for(ll i: diff){
	        ll val= min(i/2, y);
	        ans+=(val+val);
	        
	        if(i == 2*val +1) ans++;
	        y-=(val);
	    }
	    
	    line(ans);
	}
	return 0;
}


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

.