cry's blog

By cry, 5 weeks ago, In English

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++)
  • Vote: I like it
  • +143
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it -31 Vote: I do not like it

Thanks for the Lighting fast editorial

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

    ah you beat me

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

      It's a luck Sir

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

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

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

          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.

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

    Bro you're everywhere lightning fast

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

second :(

C was pretty tough imo

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

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

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

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

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

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

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

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

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

    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.

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

      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.

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

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.

»
2 weeks ago, # |
  Vote: I like it -32 Vote: I do not like it

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

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

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.

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

    It took me 90mins to solve B :(

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

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

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

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

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

    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 ?

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

      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.

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

        Thanks. Understood.

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

        I just want to know the concept but still can't get the logic.how this is work.Can you just explain a little bit of this concept.please..

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

Can someone please explain the problem statement of D ?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

      Now it's simply that it is difficult:)

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

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.

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

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

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

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?

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

    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

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

      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!

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

I could not solve beyond problem A. :(

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

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

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

    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.

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

      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.

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

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

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

        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)$$$

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

        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

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

        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)$$$.

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

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$$$).

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

    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.

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

      Oh, I have just understand that. Thanks.

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

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

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

    It seems that I used a similar solution to yours, the only difference is that you used binary_search but I used priority_queue. I am also seeking hack data for my solution. 254165883

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

    Hacked with the same test case as in this comment.

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

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

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

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

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

      Can you please explain ?

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

        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

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

A reminder to focus more on geometry .

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

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

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

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

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

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

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

        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

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

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

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

      Almost the same code, What a miss! 254211857

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

    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.

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

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; }

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

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

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

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

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

      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

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

Did 3 after a long time.. :)

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

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

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

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); }
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +110 Vote: I do not like it

    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.

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

      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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

Nice problemset, thanks!

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

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();	
}
»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

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

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

Rating predictions are actually pretty accurate

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

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

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

    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

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

      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!

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

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

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

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

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

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

        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.

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

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

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

    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.com/blog/entry/126942#comment-1135215.

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

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.

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

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.

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

    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!

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

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)$$$.

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

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

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

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

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

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

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

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

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

      mex till i = p[i]+1 ?

      a[i] = 1 !!!!

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

      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.

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

Liked rating predictions idea , hope to see it each contest

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

    you mean the current rating is not final yet ?

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

      problem rating predictions (see the spoiler in the second line )

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

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.

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

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?

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

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

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

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

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

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

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

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

Submission

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

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

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

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

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

what can i say? how to solve D

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

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

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

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

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

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

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

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

    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.

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

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?

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

    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.

»
2 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

MAN,what can I say?

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

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

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

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

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

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

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

    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:

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

you are so rude cry

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

https://codeforces.com/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

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

Problems are very interesting and educational!!!

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

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

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

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?

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

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 :)

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

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

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

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

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

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

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

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

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

C is quite easy, isn' t it?

i think it is easier than B

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nope. :) I solved A, B, and D but none of C1 and C2.

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

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

Any hints would be appreciated

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
10 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

»
10 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

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;
}