TheScrasse's blog

By TheScrasse, history, 4 months ago, In English

The official implementations of all the problems are here.

Timeline of the round proposal (may contain spoilers)

1909A - Distinct Buttons

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Solution

1909B - Make Almost Equal With Mod

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

1909C - Heavy Intervals

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

1909D - Split Plus K

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

1909E - Multiple Lamps

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1909F1 - Small Permutation Problem (Easy Version), 1909F2 - Small Permutation Problem (Hard Version)

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1909G - Pumping Lemma

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

1909H - Parallel Swaps Sort

Author: TheScrasse
Full solution: Endagorion, errorgorn
Preparation: TheScrasse, franv

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Hint 7
Hint 8
Hint 9
Hint 10
Hint 11
Hint 12
Solution

1909I - Short Permutation Problem

Author: TheScrasse
Full solution: errorgorn
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution
  • Vote: I like it
  • +354
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks for the fast editorial!

»
4 months ago, # |
Rev. 2   Vote: I like it -81 Vote: I do not like it

del

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for the quick editorial. I will probably become expert in this round. Thanks.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why this solution receives TLE? I assumed that the time complexity would simply be O(nlogn): 238557809

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

    That's because you've used

    upper_bound(r.begin(), r.end(), l[i]);
    

    instead of

    r.upper_bound(r[i]);
    

    The first one works in $$$O(n)$$$ and the second one in $$$O(log\;n)$$$ where $$$n$$$ is the size of the set. This is due to the fact that the first function is a generic function that works with any container and is guaranteed to work in $$$O(log\;n)$$$ only if the container supports random access (std::set doesn't support random access), while the second one is a specific function designed only for sets and is guaranteed to have good complexity. You can refer to the documentation in case you're confused:

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah, unfortunate. Thanks for the insight!

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have basically the same code and I did use r.upper_bound, but I still get TLE: 238528720. Did I perhaps get constant factored?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think I did get constant factored :( Instead of storing the segment in a vector<pair<int, int>>, I removed this intermediate step and stored the length of the interval in a vector<int> directly and it passed 238595993. I don't understand why this would impact the time factor; I thought this would only cost a bit more memory.

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

    I think to find upper bound on set r, you should use r.upper_bound(x), not upper_bound(r.begin(), r.end(), x)

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I Feel so stupid for not getting B in an hour

»
4 months ago, # |
  Vote: I like it -7 Vote: I do not like it

MathForce. All problems have math tags.

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

    idk why but pinely and codeton rounds are biased towards number theory and maths

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great round. Thanks for fast editorial

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the fast editorial

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

238549718 why does my soln of B work?

»
4 months ago, # |
  Vote: I like it +130 Vote: I do not like it

I have a different solution for H so I'll leave it here.

Let's assume $$$N$$$ is even. Consider $$$N$$$ operations $$$(1,N),(2,N-1),(1,N),\cdots,(2,N-1)$$$. These operations reverse the whole permutation. For odd $$$N$$$, one can do similar operations.

During this reversing process, every pair of numbers become adjacent at some moment. Therefore we can "insert" adjacent-swap operations to achieve the arbitrary-swap operation in the final array.

The pitfall is that when we try to do multiple arbitrary swaps, they can interfere with each other during the reversing process. However, if the target permutation has a matching structure, there are no worries about interference.

Then, remember that we can obtain any permutation by composing two appropriate matching permutations. Therefore by repeating the reverse-and-swap process twice one can sort the input permutation.

The time complexity is $$$O(N)$$$ and it's better than the intended solution. However, the number of moves is $$$3N+const$$$ and it's worse than $$$2N$$$. I'm so glad that the author didn't ask me to optimize this constant. (By the way, I'm wondering if it's possible to achieve a better constant factor with my approach.)

»
4 months ago, # |
  Vote: I like it +37 Vote: I do not like it

I solved B ..By getting gcd of all v[x]-v[x-1] and multiply it by 2

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

    can you explain ,thank you

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

      first, every number % gcd would be same.

      second, if every number % (gcd * 2) would be same, then gcd will not be gcd, it should be at least 2 * gcd.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can u pls explain in detail

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

          for example,

          7 10 16

          the gcd of the difference is 3

          So we know that after mod 3, they will be same. i.e. 1 1 1

          If we look at gcd * 2, i.e. 6. we can see the result would be 1 4 4. There could be only two elements in it. Also, if everything are still the same, then we must be have a wrong gcd in the first step.

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

            got that tnx!!

            But how u got intuition of that solution

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

              can you help me understand, why taking the gcd of difference works ?

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

            nice explanation I want to add that this rule will help in understanding this approach

            if a % k == b % k then (a-b)%k==0

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        its not correct

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          it works when you do the GCD of the Difference Arrays only as mentioned in the main comment

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh I thought I made it clear. The gcd in my comment means the gcd mentioned in mostafaabdelaal_03's comment, which is the gcd of the difference.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you provide a case?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hello, Sorry if my doubt sounds dumb but I agree that everynumber%(gcd*2) won't be the same but how can you claim that those "not same" %(gcd*2)s will be "same" as there have to be exactly 2 numbers one would be those who are still %(gcd*2)==0 and the other ones who are not zero but how can you claim that the other ones who are not zero will be equal

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

          let's say every number mod gcd is x, i.e. a[i] = x + num * gcd for some integer num

          then everything mod 2 * gcd would be either x, or x + gcd.

          This is because when num is even, a[i] % (2 * gcd) would be still x,

          when num is odd, a[i] % (2 * gcd) would be x + gcd

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Understood! Thanks for your time

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

            thank you for the explanation

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

    i was trying a similar approach but got stuck...please explain

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, when we are doing operations on a[i]and want to make it to "tar". You are just doing partitioning. Won't there be cases where we partition a[i] into y, a[i]+k-y, and then recursively do operations on both of them?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think about adding operation as ratios, and I can spread the total sum among all of the buckets I produce (from that ai) however I want.

»
4 months ago, # |
  Vote: I like it +186 Vote: I do not like it

The amount of effort that went into this round is insane, the timeline doesn't really do it justice. Kudos to TheScrasse for never settling on anything less than perfect, and errorgorn for coordinating this extremely demanding set. This turned out to be one of the most quality rounds in my recent memory!

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

    Thanks a lot for the solution of problem H! It's my favorite problem in this contest, but I don't deserve the merit because you've solved it :)

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

      That makes two of us for the favourite problem part. =) Coming up with a concept this interesting is surely worth of the problemsetter's merit. I was glad to contribute, and had much fun thinking about this excellent problem some more.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you very much for fast Tutorial! I dream of seeing an analysis of the problem D. Thank you for this good round!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F1 with combinatorics?

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

    A way to think of this is to maintain the invariant that the difference of p between consecutive elements in front of the ith element is correct and also to satisfy the current consecutive difference. Denote unallocated elements smaller than i as k.

    If we want to make a consecutive difference of 2, we must assign the current largest element in previous k-1 vacant place, and place any of other k-1 element in current place which is (k-1)*(k-1) ways. Note that placing the current largest element in front of ith element will not break the difference invariant.

    If we want to make a consecutive difference of 1, we can either put the current largest in the previous k-1 vacancy or place any of current k element in current place. This results in 2k-1 ways. As mentioned before, placing the current largest element in front of ith element will not break the invariant.

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

while (true)

{

    int div = 0, ndiv = 0;

    for (int i = 0; i < n; i++)
    {
        // st.insert(a[i] % d);
        if (a[i] % d == 0)
            div++;

        else
            ndiv++;
    }

    if (div > 0 && ndiv > 0)
    {
        cout << d << '\n';
        return;
    }

    // if (st.size() == 2)
    // {
    //     cout << d << '\n';
    //     return;
    // }
    d *= 2;
}

why is not working when I keep the track of two distinct remainders using two variables instead of a set. the loop is running infinitely for some test case when I use the two variables.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had similar approach, got any idea why using set/map to check the size won't work?? i am still stuck with that part.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      got it

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you explain?

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In your approach, number need not to be perfectly divisible by K.

          take one testcase where your code is failing. 2 3 1 so here answer is 4, but your code won't output anything. you just have to check if the two reminders are distinct or not. one need not to be equal to zero.

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

can someone please explain first three lines of solution of problem D ?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    let's forget array and assume that we have to deal with single element.

    if this element is greater than k say (k+x),now in one operation we have to find 2 number a,b such that a+b=(k)+(k+x), to reduce complexity of question we are doing this trick

    a+b=(k)+(k+x)=> (a-k)+(b-k)=(0)+(x)

    we don't care about final number we care about how many operation so we reduce all number by k so our operation changed in select number and break it such in two number such that sum is our x((k+x)-(k)).

    in short after reducing by k we don't have to deal with k;)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

All the problems were great and overall the contest was very enjoyable to solve. Thank you for such a good round!

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Worst contest for me so far. Didnt solve any. For who wants to see pure pain:

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Story timeline of the round was something new and quite interesting, I enjoyed it.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In question C I have a test case : 5 1 2 3 6 7 3 4 5 7 8 1 2 3 4 5 in which many got answer 14 and 18. according to me answer is 18 as 14 is not possible please comment on it.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why my solution gives WA 238595753 in B. Got the logic but got stuck with WA. can anyone explain why this is happening??

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    long long :(

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it, actually I defined my map earlier, after that I used Macro for long long to int conversion ;)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Last Dance, gud taste m8.

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

This is my soln to the problem B:

bool check(vi arr, ll num){
    map<ll,ll> m;
    loopi(0,arr.size()){
        m[(arr[i]%num)]++ ;
    }
    if(m.size() == 2) return false ;
    return true ;
}
void testcase(){
 
    ll n; cin>>n;
    vi arr(n); 
    loopi(0, n){
        ll x; cin>>x; arr[i] = x ;
    }
    if(n==2){
        cout<<10<<endl;
        return;
    }
    ll num = 2 ;
    while(check(arr,num)){
        num = num*2 ;
    }
    cout<<num<<endl;

    return;
}

this passed the pretests but in the system test's testcase-4 line 130 it gives ans as 128 but my output is 2. Idk how this is possible with this code cause every time for every power of two a new map is made and values are added... also, it's almost the same as the ans present in the editorial... can someone explain why my soln would give the wrong ans...? The link to the submission is:- 238532052

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your output on line 130 is 10 not 2.

    As a counter-example consider, a = [10, 20]

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I thought the problem was to do this for size(array) > 2, as an array of size = 2 would already contain distinct elements, but I ignored the fact that the question had mentioned "apply this operation exactly once" in it and not at most once. :(

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I was trying to find some cheaters of contest and found this...

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

In the editorial of problem D(solution section),

Shouldn't it be "replace y with x+y" instead of "replace x with y+z"

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

B in O(n): $$$\large 2^{ctz((a_1 \land \cdots \land a_n)\oplus(a_1 \lor \cdots \lor a_n))}$$$

238596786

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing contest! Problems were fantastic. Thanks a lot for the round TheScrasse and all testers.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the concept behind problem D.I didnt understand the editorial

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    +1

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

    Assume we create a new board $$$B$$$, on which for each number $$$x$$$ written on our original board (call it $$$A$$$), we write the number $$$x - k$$$ on $$$B$$$. Then, let's try seeing what our operation does. So, since $$$y + z = x + k \implies (y - k) + (z - k) = (x - k)$$$ (for the original board), and since we've written $$$y - k, z - k$$$ on our modified board instead of $$$x - k$$$, this gives the observation that on $$$B$$$, our operation just corresponds to replacing $$$x^{*}$$$ by two numbers $$$y^{*}, z^{*}$$$ such that $$$x^{*} = y^{*} + z^{*}$$$. Then, solving this reduced problem is pretty easy (for implementation purposes, just subtract $$$k$$$ from each element of $$$a$$$, and do the calculations on that itself).

»
4 months ago, # |
  Vote: I like it -24 Vote: I do not like it

spoilers make the whole text unreadable

»
4 months ago, # |
  Vote: I like it -34 Vote: I do not like it

writing complexity at the end of an editorial is cringe

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem B was really something...

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it was easy

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can u explain editorial?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        well it is kind of obvious intuition you get once u see 2 distinct values modulo some k you think of 2 since only two values are possible however then you remmeber all values might be pair hence there is only one value and then this amazing idea gets to u about the next power of 2 which is 4 well since the numbers were allwith the same parity they have only 2 values possible (pair numbers possible values are 2 or 4 and impairs values are 1 and 3) and then again there is possiblity that they all have same value time to check 8 again only 2 values are possible, you can conlcude that the sol requires checking all powers of 2,genius,see this much easier than what the editorial makes it look like.By the way i just guided you trough how the logical thinking went in my brain

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for the great explanation

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

          How did you know it would work when all the values were odd?

          edit: nvm. you said that if they're all odd then they'll either be 1 or 3 after you mod by 4.

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

TheScrasse How does the grader for H work?

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

    Link to comment

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 6   Vote: I like it +13 Vote: I do not like it

      (Nvm, this is wrong if you run it on a decreasing array.)

      By the way, isn't the number of moves for the editorial solution actually bounded above by $$$3n/2$$$? Since the number of moves during the second phase is at most the number of Bs after the first phase, which is at most $$$n/2$$$ due to there being no two consecutive Bs and the last letter being an A.

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

      Also curious about these:

      • Were you aware of a solution to H that made $$$3n$$$ operations before the contest? Or did the limits just happen to be large enough to allow that to pass?

      • What was the original solution to H with $$$O(n\log n)$$$ operations?

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

        H with $$$O(n \log n)$$$ operations sounds like a considerably more boring problem, as I believe you can simply simulate merge sort: suppose the right part starts at $$$x$$$, then you can use operations on $$$[x-1,x]$$$, $$$[x-2, x+1]$$$ etc to create a train of moving elements from right to left, and you remove elements from the train when they reach their final positions.

        Other than the very annoying implementation, H with $$$O(n)$$$ operations is a work of art :)

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hm, I don't fully understand.

          By merge sort, do you mean that given two sorted arrays on consecutive ranges, you can merge them into one sorted array?

          If you do operations on $$$[x-1,x], [x-2,x+1], [x-3,x+2], \dots$$$ then this will move some elements right to left over $$$x$$$ and others left to right over $$$x$$$. But how are you removing elements when they reach their final positions? What if there's some element in the middle of the train that you don't want to keep moving?

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Here's how I did it: imagine inserting just the rightmost element $$$a_i$$$ of the left half with $$$[x - 1, x]$$$ operations. $$$a_{i - 1}$$$ can trail behind two positions away for free simply by extending the segments to the left (skipping the first one). We stop the trail early if $$$a_{i - 1}$$$ doesn't need to go that far, and proceed to $$$a_{i - 2}$$$. Final case is if $$$a_{i - 1}$$$ needs land next to $$$a_i$$$, in which case we add one more swap at the end to achieve that.

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

              I agree about $$$a_i$$$ and $$$a_{i-1}$$$, but what if $$$a_{i-2}$$$ and $$$a_i$$$ need to keep moving to the right but you don't want $$$a_{i-1}$$$ to keep moving to the right?

              It's true that $$$a_i$$$ must move at least as far right as $$$a_{i-1}$$$, but once you take into account the fact that $$$a_{i-1}$$$ must trail two spaces behind $$$a_i$$$ to move them rightward at the same speed, this is no longer true.

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

                For $$$a_{i - 2}$$$ we can forget what $$$a_i$$$ does, and focus on operations moving $$$a_{i - 1}$$$. Since they don't want to swap, the same logic keeps applying.

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it +10 Vote: I do not like it
        • I was not aware of any linear solution other than the official one. I didn't put $$$2n$$$ as the operation limit to avoid spoilers.
        • The original solution was "put the $$$n/2$$$ smallest elements in the left half of the array in $$$O(n)$$$ operations, then recurse". Some testers found the "merge sort" solution explained by ffao.
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hints are very helpful,thanks for editorial

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please explain why my solution of problem C — Heavy Intervals does not work

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In test case l=[1,2,3], r=[10,12,13], c=[1,1,100] it's best to pair (3,10)*100, but in your solution c=100 is multiplied by 10

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Writing timeline of the round is very cool.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

too much math and number theory

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very well written editorial! Excellent hints that actually do help a lot if we don't want to see the full solution. Thank you TheScrasse for the good contest and the great editorial.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D is very nice!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved problem B using random numbers.The submission:238551759.

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The subtasks of F is helpful for some but also misleading many participants including me :(

anyways, good problems and good contest

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In E, I only understand this phrase in the statement after reading editorial:

If you press the button ui, you also have to press the button vi,(at any moment, not necessarily after pressing the button ui)

It's my fault to not read it properly, and couldn't think that it is possible to press all buttons

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the editorial :)

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

Can someone please prove this If ai mod k=x , one of the following holds:

ai mod 2k=x ; ai mod 2k=x+k ; problem B

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

    This is not a proof but this might help in understanding more intuitively. consider this array A=[42,10,26]. let's write these numbers in the bit representation.(i will use term 'bit position k' which means kth bit from right).
    42 = 101010
    10 = 001010
    26 = 011010

    let's take k=4

    can you tell what will be A[i]%k for all i ,(where k=4) just by looking at bit representation?

    using k=4, we got only one distinct element i.e. 2
    let's do same thing for k=2*k. follow the same steps that we did for k=4
    for k=8, we will get only one distinct element i.e. 2
    for k=16, we will get only one distinct element i.e. 10

    now when k=32, the set bit position is 6. The bits for each number in A which lies on right side position of set bit are reminders.

    42%32 is 01010
    10%32 is 01010
    26%32 is 11010

    for k=16 we got
    42%16 = 1010
    10%16 = 1010
    26%16 = 1010

    see the transition in results from k=16 to k=32. Upto bit position 4 the reminder is same(which is 10) but when we did the mod operation for k=2*16 we got 5 bits. The new bit that we got will be either 0 or 1. If it is 1 we will add previous k(16 in our case) to the previous reminder, and if it is 0 we will get the previous reminder as it is. So we finally got 2 distinct values which are (previous reminder+previous k) and previous reminder as it is.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B was such a good question. Was stuck on the gcd approach for a while before realizing the pattern in the bits.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check my submission,i had different implementation you might find what you are looking for

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    even I got stuck at the gcd approach , the answer would be 2*(gcd of differences of successive terms)

»
4 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Lot of mathematics, I feel they should also try not giving just mathematics. B was too hard for me,i never would have thought it that way.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem D why the answer is -1 when we have both negative and positive in our array after applying the operation (a[i] = a[i] — k) ?

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

    First, notice how the number of operations required to make the "shifted" array (as it is called in the editorial) have equal values is the exact same as in the case of the original array.

    Now, with that out of the way, let's establish some notations. We'll denote the first element in the shifted array with a1', the second element in the shifted array with a2' and so on. The final value will be val (after all the operations, the shifted array will have all its elements equal to val). The number of operation required to change the first element of the shifted array to val (which is the same as the number of operations required to change the first element of the initial array to val) will be written as nop1. For the second element it will be nop2 and so on.

    We will consider a shifted array with only 2 value, but the proof can be generalized.

    Notice that a1' is equal to (nop1 + 1) * val and a2' is equal to (nop2 + 1) * val. This means that we can write val with respect to a1' and a2':

    val = a1' / (nop1 + 1)

    val = a2' / (nop2 + 1)

    This means that:

    a1' / (nop1 + 1) = a2' / (nop2 + 1)

    At first glance it seems that this equality always holds true. However, notice how a1' and a2' can have any integral value but nop1 and nop2 can be only non-negative numbers (it doesn't make sense to have a negative number of operations). This means that this equality is valid as long as a1' and a2' have the same sign. The moment they have different signs, this equality doesn't hold anymore and val can not exist.

    On a side note, following the same rationale you can determine that val doesn't exist in the case where there are 0 and non 0 numbers in the shifted array.

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Alternative solution for E:

Let's call a subset $$$S$$$ of pressed buttons good if at the end at most $$$\left \lfloor \frac{n}{5} \right \rfloor$$$ lamps turned on. For $$$n \leq 19$$$, the amount of such subsets is $$$\leq 1159$$$. We can find them for each $$$n \in [1, 19]$$$ in $$$O\left(\sum\limits_{n=1}^{19} 2^{n} \cdot n \log n\right)$$$, and then check only them for each $$$n \leq 19$$$ testcase in $$$O(nm + 1159n)$$$.

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

    Actually, you can prove that the number of such subset for $$$n = 19$$$ is exactly $$$\binom{19}{3} + \binom{19}{2} + \binom{19}{1} = 1159$$$ since we can think of each switch $$$i$$$ associated with a vector $$$v_i \in \mathbb{Z}_2^{19}$$$ and all the vectors are independent, so $$$v_1$$$, $$$\dots$$$, $$$v_{19}$$$ is the basis, and we only care when $$$\oplus_{j = 1}^k v_{i_j}$$$ has less than or equal to $$$3$$$ bits on (excluding the case it is equal to zero), so we get the above result.

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

In problem D could we have solved for the smallest x in x*k+ Sum of Ai which is divisible by x+n

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider the case $$$A = [1, 2, 3].$$$ In this case $$$x = 0$$$ is the best choice, which is incorrect.

    For only positive $$$x$$$ values, consider $$$A = [10, 10, 20]$$$ and $$$k = 10$$$. In this case smallest $$$x$$$ is $$$2$$$ that satisfies the condition, but you can't really make all numbers equal.

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

Can anyone help me with a simple test case for which my submission is wrong for C? It's the same logic as the above solution

https://codeforces.com/contest/1909/submission/238575783

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I love long and clear explanations in math and number theory problems. thanks to errorgorn TheScrasse franv Endagorion and everyone who contributed.

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

In problem C, making small intervals is not the same as sorting the sequences of left and right endpoints and pairing the corresponding indices. Let, $$$u = L_1,L_2,...,L_n$$$ si obtained after sorting $$$l_1,l_2,...,l_n$$$ and $$$v = R_1,R_2,...,R_n$$$ is obtained after sorting $$$r_1,r_2,...,r_n$$$. Then the new intervals will be $$$[L_1,R_1], [L_2,R_2],...,[L_n,R_n]$$$.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what are you trying to say ? can you explain a little more ?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the difference between the approach explained in the editorial and my approach?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your approach fails for $$$l = [1, 2]$$$, $$$r = [3, 4]$$$, $$$c = [1, 2]$$$. You claim that it's optimal to keep everything as it is, while the editorial makes $$$l = [1, 2]$$$, $$$r = [4, 3]$$$, $$$c = [1, 2]$$$ ($$$3$$$ is matched with the closest $$$l_i$$$, which is $$$2$$$). The picture "explains" why the second solution is better than the first.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hi, I didn't understand the picture can you explain it once? what is the 3 and 5 and what the different colors represent

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

            The red subinterval is the only one whose cost changes (from $$$5$$$ to $$$3$$$). In general, you want intervals with big cost to be as small as possible, so you let intervals with small cost "steal" subintervals from intervals with larger cost.

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thank you! Got it now.

              Also the symmetry case with Ci>Cj means we would just assign Cj to the first interval(instead of Ci in explanation) to have same condition where total cost does not increase(as interval with Ci cost is decreased and interval with Cj cost is increased)?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, would be great if someone explained why the following idea for B does not work

https://codeforces.com/contest/1909/submission/238648704

I was thinking of the following test cases

It should seem to always be possible for k to be a single digit value unless all numbers are multiples of 10.

If there are 2 distinct numbers for each last digit, k=10 is always a solution.

If there are more than 2 distinct numbers for each last digit, we can iterate k=2-9 to find a value for which it works

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

learned a property of divion and remainder in binary form.Thank you

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, What the following line does inside the check(int s) function of Jiangly's code 238527503

if (s >> u[i] & ~s >> v[i] & 1)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If button $$$i$$$ is pressed, then s>>i will be $$$1$$$. This line is to check whether $$$m$$$ pairs are satisfied.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for interesting tasks.

Little comments for authors. problems $$$B, D, F$$$ are really cool, because they can be solved without any algorithms with only a brilliant idea.

Problem $$$C$$$. Maybe it was better to make more samples, because there were a lot of WA's and a lot of greedy solutions can pass example tests(but of course incorrect).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E is kind of funny.I tried to use complicated graph algorithms but failed.And the official solution is cool!I love it!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast editorial!

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I have another solution for problem G. It is easier than the intended one in my opinion, at least idea-wise.

Solution
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, "Now, the operation becomes "replace x with y+z such that x+y=z+k⟹(x′+k)+(y′+k)=(z′+k)+k⟹x′+y′=z′ ". Therefore, in the shifted problem, k′=0" .

I think it should be y+z = x+k instead of x+y = z+k.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I can understand the solution of G now,but I've got no idea about how the vital observation "$$$(a,b)$$$ is valid then $$$(a+1,b+1)$$$ is valid if and only if $$$s_{b+1}=t_{b+1}$$$" was found.What inspired you think about that?Can someone help me?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, I only found it while preparing the problem (with constraints $$$n, m \leq 2 \cdot 10^5$$$). I was trying to build strong tests (where the valid $$$y$$$ of fixed length are not consecutive), but I ended up proving it's not possible.

    I'm curious about how actual contestants figured it out.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I see lots of people have doubts about why '2' in B,and I have difficulty in it too.Actually it's difficult to find 2 when in competiton for man who didn't cotact number theory.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can tell you how it worked for me. It is easy to get that if the array has even one even and odd number k can be taken as 2. Now the arrays left will have either all even or all odd numbers.

    For arrays with all even numbers, upon taking k as '2' the only value we get will be zero, but these might not all be divisible by '4' which forces us to think to take k as 4, which can yield two distinct values as zero and two, and again if this doesn't work we can keep on taking k as 8, 16, 32...

    For arrays with all odd numbers if we take k as 2, the only value we'll get is one, or the other way round if we remove 1 from all numbers again they all are divisible by 2, which again forces us to think that these all numbers(after one being removed from them) might not be divisible by 4, hence taking k as four can yield values as one if the number is divisible by 4 or yield as three if it's not divisible by 4, and again we can take 8, 16, 32...similarly until we get two distinct values.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain with a proof how does subtracting k from every a[i] in problem D, effectively convert it into a shifted problem with k = 0?

for all problems with k = 0, our job is to divide the sum of the numbers in the array into pieces which are all equal right? so i assume, we subtract k from the numbers in the original problem in order to reduce the sum. but since every time we do an operation we increase the sum of the numbers in the array by k, how does it guarantee that subtracting k from all the numbers lets us forgo this requirement, i.e. we subtract n*k from the original sum but it is not true that we have to do exactly n operations every time and hence subtract n*k from the original sum.

i'm sure there is some misconception in my assumptions, if someone would be nice enough to point it out to me, it would be very cool. thanks for reading.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the intution behind problem C?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain how the rearrangement inequality is related?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I guess I actually do see how it is used in the problem (in sorting the cost array in descending order with the lengths), but that wasn't the hard part for me. The part that was hard was how to pick the elements l and r. I guess an intuitive explanation would be that you want to maximize the lengths so that you can pair a higher length with a a lower cost. To do that, for the smallest Rs, you want to pick and L that is the closest to them because you want to save the smaller Ls for the Rs that are larger, because that results in a larger lengths. I can elaborate more on this if anyone wants me to.

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

in problem c I'm trying to follow the editorial in the proof section he is saying at the third line If you swap ri and rj, the cost does not increase. I did that on the example n=2 provided and the cost increased from 6 to 7 first step he said match them any other order so: [2,4] [1,3] then he said You have also assigned some cost ci to [li,ri] and cj to [lj,rj] . [2,4] ci=2 [1,3] ci=1 now cost is 6 then ** If you swap ri and rj, the cost does not increase. ** swapping here will make the cost 7 so I don't get it can you please explain what is wrong here

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the editorial, $$$c_i \leq c_j$$$. If $$$c_i > c_j$$$, you have to swap $$$l_i$$$ and $$$l_j$$$.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me to explain the complexity of problem E plz?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For each test case, you have to iterate over $$$O(n^{k-2}) = O(k^{2k-4})$$$ masks (in the worst case), and for each of them you can check if it works in $$$O(m)$$$.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know how to prove $$$O(n)=O(k^2)$$$, but I don't know how $$$O(n^{k-2})$$$ comes out (especially $$$k-2$$$ power). Sorry for bad English expression.

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

        tl;dr replace $$$5$$$ with $$$k$$$ and $$$3$$$ with $$$k-2$$$ in the editorial.

        The largest solution to $$$\lfloor n/k \rfloor < \lfloor \sqrt n \rfloor$$$ is $$$n = k(k-1)-1$$$. In that case, you already have a solution which turns $$$\lfloor \sqrt{k(k-1)-1} \rfloor \leq k-1$$$ lamps on, so you can iterate over masks which contain $$$k-2$$$ lamps.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you so much!

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But here seems to be a little mistake? I suppose it should be "The largest solution to $$$\lfloor n/k\rfloor<\lfloor \sqrt{n}\rfloor$$$".

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

Can anyone provide more proof on editorial of C? Why does the algorithm mentioned on the editorial works? More mathematical proof?

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For D, the shifting part is still unclear to me(ik what is being done ,but how is it correct and how to think of it) thnx in advance if someone can spare their time or share related resources

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was really struggling for a while to come to grips with this solution and I think I am now (mostly) convinced of why it works, so I'll try to explain my way of thinking about it.

    Imagine a number line with numbers x, y and z marked such that y + z = x + k.

    Now think about the operation you can do: y + z = x + k. Going back to the number line, what this operation means is you would have to pick x and move it k unities to the right, then pick two numbers x and y such that their sum "lands" in (x + k) and not x.

    For each of those three numbers now, mark in the number line its value shifted k unities to the left, and call these new guys x', y' and z'. Clearly you can represent x by (x' + k), y by (y' + k) and z by (z' + k). So, looking again at our operation, we have (y' + k) + (z' + k) = (x' + k) + k -> y' + z' = x'.

    What that tells us is that if we had a magical way of taking every number on our line and shifting it k unities to the left, when we would execute the operation on an original number x, instead of doing that complicated process (moving it k unities to the right and only then finding numbers which add to it), we could map x to its representation in the shifted "world" and find two other numbers, also in the shifted world, such that their sum is equal to the representation of x.

    Our magical way of doing this shift is simply to take every number given in the input and subtract it by k. Now, for every operation we do in those numbers (including gcd), we are working with numbers from our shifted world; so we can now solve the problem as if k didn't even exist. Hope this is helpful in some way :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

clear proof for C

Disjoint intervals are okay.

But choosing between overlapping and intersecting intervals, it turns out that overlapping intervals give a smaller ans.

Checkout the writeup.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone give the intuition behind the idea of "shifted problem" for D ? is it a trick or just random manipulation for this specific problem

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell the error in this code for Problem C: https://codeforces.com/contest/1909/submission/239092120

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In D you can also do the reverse problem: Start at the final state which is a bunch of identical elements then apply "combine and subtract $$$k$$$" operations and arrive at a similar solution with algebra.

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

Just posting the snippet I took from my notes here, maybe it will be of help. The following attempts to explain why a possible solution to Problem B is outputting 2 multiplied by the gcd of the elements in the difference array.

Another method is presented in the comments. It states that, if performing mod (2 * g') on the input array (where g' is the greatest common divisor of the absolute value of the difference between two consecutive elements) there will be exactly 2 distinct values. Why is that?

We can write g' as gcd(a[i] - a[i-1]) assuming that a[i] is greater than a[i-1] (this can be easily accomplished by sorting the array or taking the absolute value).

Another useful notation is the following: let f(k) be the number of distinct values resulted after performing mod (k) on each element of the input array.

Another useful observation is that if a ≡ r (mod k), than there are 2 possibilities:

  1. either a ≡ r (mod 2k)
  2. or a ≡ r + k (mod 2k)

Now with that out of the way, we shall prove that f(2g') = 2.

Notice that f(g') = 1. Why? Because a[i] - a[i-1] ≡ 0 (mod g'), which means that a[i] ≡ a[i-1] (mod g'), that is, all elements have the same value after performing mod (g') on them.

How about f(2g') = 2? Well, based on the previous information, we can state that f(2g') should be either 2 or 1. So why it is not 1? Because f(2g') = 1 would mean that a[i] ≡ a[i-1] (mod 2g'), so a[i] - a[i-1] ≡ 0 (mod 2g'), so 2g' would be a divisor of a[i] - a[i-1]. However, do not forget that g' is the greatest common divisor, so there is no divisor greater than it, this means there is no way f(2g') = 1 as that would imply that 2g' is a divisor greater than the greatest divisor.

After all of this, if f(2g') can not be 1, it goes without saying it should always be 2f(2g') = 22g' is a valid solution.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Folks, can someone please help me with why my solution to D is failing for the 6th test case given in the question?

My solution
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in first probelm you said that i can visit it in any order so i can go to the point (1,0) after that to (-1,0) after that to (-1 ,-1 ) so i use just r l d so the answer in test two YES !!!!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D is amazing i have different approach for. suppose mn and mx are the max and min elements if mx == mn ans is 0. if mn <= k && k <= mx we can neve the values of array to a single value. if k < mn || k > mx ans will exist. assume at the end all the elements are equal to x so the last element we remove = 2 * x — k. second last element we would remove will be either 2 * x — k or 3 * x — k and so on. it shows that all the elements in the initial array is of the form .. pi * x — (pi — 1) * k, after rearranging pi(x — k) + k. now ans would be just summation of all pi.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody please help me with my doubt?

https://codeforces.com/blog/entry/125187

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

Problem I is 1900!!!

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

C seems to be a bit difficult for a 1400; or is it just for me?

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

    Div1C is different difficulty than a Div4C problem even if they're both rated same.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
ai mod 2k = x;
ai mod 2k = x + 2k;

There must be x + 2k instead of x + k.

For example, let ai = 5 and k = 2:

5 % (2*2) = 1;

Hence, x is 1.

If we go with ai % (2k) = x + k, then:

1 + 2 != 5

But:

1 + 2*2 == 5;

TheScrasse