vaaven's blog

Codeforces Round #953 Editorial
By vaaven, history, 10 days ago, In English
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
  • Vote: I like it
  • +76
  • Vote: I do not like it

»
9 days ago, # |
  Vote: I like it +4 Vote: I do not like it

This was a great contest. Nice problems + superfast editorial + quick system testing.

→ Reply
»
9 days ago, # |
  Vote: I like it +22 Vote: I do not like it

Thank you for the quality contest and fast editorial. I had fun during this contest. :)

→ Reply
»
9 days ago, # |
  Vote: I like it +52 Vote: I do not like it

C was harder than DE :(

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

    Agreed but still a good one though :)

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

    Isn't it a bit sus how many people solved C?

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

      It was harder for me

      → Reply
    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      it's possible that this happened out of complete coincidence, but problem C appeared before in last year's ECPC finals which is the Egyptian qualifier for our ICPC regional, it was the exact same problem with just greater constraints for K on today's round which might have given advantages to people who solved it last year and people who upsolved it later on.

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

        Maybe, i guess just skill issue on my part :(

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

    yes, true :(

    → Reply
  • »
    »
    8 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    C was harder than DEF :(

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

      F xD!

      → Reply
»
9 days ago, # |
  Vote: I like it -14 Vote: I do not like it

D is a good problem! E is not hard. I think this is a very good round.

→ Reply
»
9 days ago, # |
  Vote: I like it +18 Vote: I do not like it

What is &mdash in the code of problem B,C ?

→ Reply
  • »
    »
    9 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Usually a formatting issue, — is equivalent to a minus symbol.

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

Whoa speed!

→ Reply
»
9 days ago, # |
  Vote: I like it -10 Vote: I do not like it

Fast editorial! Great Contest!

→ Reply
»
9 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Fast editorial!

I think C, D, and E were all roughly the same difficulty though. F also seems on the easy side.

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

How can you explain the $$$length <5$$$ in E? Also C's code has formatting issues.

→ Reply
  • »
    »
    9 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If you see the given range [l,r], the only only elements which gets affected are a[l], a[l+1], a[r] and a[r-1] and rest of them remains same. So when you check for these indices the range [l,l+1] and [r-1,r] should not cross each other, otherwise single index will be counted twice. Therefore, for len < 5 is done using brute force. One can use len < 7,8 it won't change the answer.

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

    We understand that we should first finish all the type 1 operations, since that will only increase the type 2's chances to increase the count of 1s in a. Consider a segment from [l, r]. Even in this we do the type 1 operation. This does the same affect in b in range l + 1 to r — 1 as when you would consider the whole string for such operations. Now when do b's operations, the range l + 1 to r — 1 then have the same influence on the range l + 2 to r — 2 as in the whole string. So, if we consider a range l to r, we only need to re calculate values which is within 2 length less from both sides. The inbetween can be used from the answer for this range when we calculate for the whole string, which can be precalculated and the count of 1s can be stored as prefix sums. Hence we need to first calculate the ans for the last two numbers from the ends of the range and add the precalc for the inbetween with it. Now, this precalculation obviously only needs to be added when the length of the range is >= 5.

    → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain in Problem C how do we prove that:

" maximum maxk is achieved with the permutation [n,n−1,n−2,...,1]"

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

    For each $$$i$$$ from permutation it can contribute to sum with $$$1$$$ or $$$-1$$$. Same for $$$i$$$ from neutral permutation. There are exactly $$$n$$$ numbers that contribute with $$$1$$$ and $$$n$$$ with $$$-1$$$. It's easy to see that maximal sum is achieved when $$$n$$$ greatest numbers contribute with $$$1$$$ and $$$n$$$ smallest with $$$-1$$$. Also you can see that with permutation $$$[n, n - 1, n - 2, ..., 1]$$$ we get this sum.

    → Reply
  • »
    »
    9 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Think like this:

    If the original identity permutation is : $$$[1,2, \dots , n]$$$, then swapping any indices $$$i$$$ and $$$j$$$ ($$$i < j$$$) would result in score going from 0 to $$$2*(j-i)$$$. So what would be most optimal?

    It would be swapping $$$(1,n), (2,n-1), \dots$$$ and so on. This would result in the max ans. This also proves the condition why for k odd, answer won't exist.

    → Reply
    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      In fact it's not so obvious that it would be most optimal. There is at least one permutation with same score:

      [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] = 50
[6, 7, 8, 9, 10, 1, 2, 3, 4, 5] = 50

      So proof of optimality is indeed necessary.

      → Reply
    • »
      »
      »
      9 days ago, # ^ |
      ← Rev. 4   Vote: I like it +4 Vote: I do not like it

      To see why this is indeed the max answer, we can see that if we write out the sum for the answer $$$\sum_{i = 1}^{n}|perm[i] - i|$$$, then each i occurs twice, one for the index i and one for the index j where perm[j] = i. If we remove the absolute value and write out the sum with the correct sign, each i occurs twice with either — or + sign, and there are n signs for each kind in front of these 2*n numbers.

      Now, collect the terms by sign. When is a sum of kind x = y — z maximized for positive y and z? It's when y is max and z is min => We take the occurrences of larger n numbers with positive signs and smaller n numbers with negative signs => all numbers greater than n/2 are with + sign in the answer, and smaller than n/2 are with — sign.

      An interesting consequence of this is that there are $$$(n/2)!^2$$$ such sequences for even n and $$$n*(n/2)!^2$$$ sequences for odd n with the maximum sum.

      Edit: Missed a detail

      → Reply
  • »
    »
    9 days ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    You can apply indirect proof. Suppose that there is a permutation $$$q$$$ other than $$$p = [n,n−1,n−2,...,1]$$$ that gives a higher value. This means that there are indices $$$i$$$ and $$$j$$$, $$$i < j$$$, where $$$q_i < q_j$$$. Now, consider elements $$$|q_i - i| + |q_j - j|$$$, those are elements of sum for $$$q$$$. Look that always $$$|q_j - i| + |q_i - j| \geq |q_i - i| + |q_j - j|$$$. So, if we swap elements and $$$q_i$$$ and $$$q_j$$$ we do not decrease the value of metric. We repeat this procedure until there are any such pairs left in $$$q$$$. If there are not, we reached $$$p$$$ without decreasing value (we always reach p since every swap sort permutation and the process converges), which contradicts the hypothesis and which proves the thesis.

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

Example given in D extremely weak imo, maybe intended

took nearly 2 hours to debug after contest

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i think there is a typo in the solution of D, since the index starts at 1, for every candidate the possible answer are 0,(i-1) and i. In the editorial u put 0,i and i+1 like index starts at 0.

→ Reply
»
9 days ago, # |
  Vote: I like it +4 Vote: I do not like it

I think the problems order should be A, B, D, E, C, F because C is really hard on both thinking and implementing. D is only about thinking and E is only implementing :(((

→ Reply
  • »
    »
    9 days ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Any tips on how to get better at constructive? I messed up so bad, got -155 delta

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

      I'm not sure if this is a good practice. I usually try to print the output by the brute force to see the pattern in the answer. I'm not very good at thinking of the algos by myself. In C, I printed all the permutations of an array and the respective score.

      → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

what would be the rating of C problem?

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For E, I ended up simplifying to the classic sweep line "how many intervals inside of my interval". Very nice problem!

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

    How so Orz?

    → Reply
    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I was lazy to type it all, but here it goes:

      The first idea is similar to the one in the editorial: We can transform 0s in A -> 1s in B -> 1s in A, in that order. First we compute the 0s in B that can become a 1. Each position will have an "interval" that is needed for that position to become a 1. For example:

      A = 010 and B = 000. The 2nd position in B has interval (1, 3), since we need this interval in A to make B = 010.

      One more time, we do the same procedure but on A, and we fix the necessary intervals to turn 0s in A into 1s. For positions that are originally 1, their intervals are (i, i), where i is its index.

      Finally, the problem becomes: For each query (an interval), how many intervals are there inside of it (since each interval is either (i, i), meaning it was initially a 1 in string A, or some other interval of type (l, r) if it used some operations to make the ith position of A a 1).

      To solve that problem, one can use a sweep line with a segment tree. We sort the updates by end_pos, start_pos, and update a segment tree at position start_pos with +1, and the query is a range sum over (l, r) when on time r of events on the line sweep. Overall complexity is O(n log n), for both sorting and segment tree operations.

      → Reply
      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Got it, thanks :) volta pro simusexo

        → Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

A good round and fast editorial, thanks! The problems are really good!

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem C, can anyone help in actually proving why k is odd gives no solution, i just got an intuition on that, couldnt really be very sure until i tried out lot of cases and could see k cannot be odd

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

    Say initially permutation was 1, 2, 3..n This will give minimum result 0, If you make any swap your result always changes in multiple of two

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

    Lets notice that |a — b| = a — b (mod 2). If |a — b| = a — b then it is obvious. If |a — b| = b — a then we need to check that a — b = b — a (mod 2). And its right because 2*(a — b) = 0(mod 2). So if we will look at |a_1 — 1| + |a_2 — 2| + ... + |a_n — n| in mod 2, we can say that |a_1 — 1| + |a_2 — 2| + ... + |a_n — n| = a_1 — 1 + a_2 — 2 + ... + a_n — n (mod 2). Then a_1 — 1 + a_2 — 2 + ... + a_n — n = (a_1 + a_2 + ... + a_n) — (1 + 2 + ... + n). And finally (a_1 + a_2 + ... + a_n) = (1 + 2 + ... + n) because a_1, a_2, ..., a_n is permutation. So, (a_1 + a_2 + ... + a_n) — (1 + 2 + ... + n) = (1 + 2 + ... + n) — (1 + 2 + ... + n) = 0. That means that |a_1 — 1| + |a_2 — 2| + ... + |a_n — n| = 0 (mod 2). So it must be odd :)

    → Reply
  • »
    »
    9 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    write the permutation as a graph (add a directed edge from p[i] to i), then the k value of that permutation will be the sum of the weights of all its edges if we let w(p[i], i) = |p[i] — i|. since only cycles can contribute to k, let's show that the weight of a cycle is always even: let u be the smallest value of a node in the cycle and let v be the greatest. then the cycle consists of a path from u->v and another path v->u.

    claim: both paths have the same parity as (v — u). proof: when the path u->v goes directly from u to v (ex: 1, 3, 5) the proof is easy, but if we go back at some moment (ex: 1, 4, 2, 5), we can think of it the following way: in the example, distance from 2 to 4 will be counted twice so it won't contribute to parity (it's 0 mod 2) so in the more general case whenever we go back we will count that distance twice since we need to get to v somehow. this means its contribution to overall parity will be zero and we can therefore use the parity of u->v which will be (v-u)%2.

    for the path v->u the proof is the same.

    since adding up two numbers with the same parity yields an even number, k is even.

    more about permutation graphs here :)

    → Reply
»
9 days ago, # |
  Vote: I like it +3 Vote: I do not like it

D is wow! I did not realize that it is enough to remove only maximal element, so I wrote treap descent to find such minimal k, that removing k maximums is optimal: 266013096

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give me a hint for how to make the permutation for C?

I think the yes/no rule is k % 2 == 0 and k <= 3n

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

what is &mdash?

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

    No clue

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

      i didnt like this contest that much, first questions itself didn't click to me and problem B was interesting but I was struggling with TLE and this solution is not helping either.

      → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why does this solution to E give wrong answer? Can you suggest a countercase?

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This was a great contest.

→ Reply
»
9 days ago, # |
  Vote: I like it +3 Vote: I do not like it

C and D detailed video editorial

C : https://youtu.be/paEcHyNKC7A?feature=shared

D : https://youtu.be/CQ7lUs6s_zc?feature=shared

→ Reply
»
9 days ago, # |
  Vote: I like it +7 Vote: I do not like it

can someone please explain editorial to D?

→ Reply
  • »
    »
    9 days ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it
    • First, you can add c to a[0] to simplify the problem.
    • Without any exclusions, it's clear that there's only one winner, whose ans = 0.
    • For other candidates, They will not benefit from any exclusions, unless they are the first ones, so we must exclude every candidate before the current one .
    Why not ?
    • Is this enouph ? No, check the second sample.
    • There maybe a later candidte whose votes are greater than all prefix candidates, so we must exclude him as well.
    • Is this enouph ? Yes, because he has already more votes than everyone else, and his votes will go the the current candidate, so the current candidate has the most votes now.

    Check my submission 266012471

    alternative
    → Reply
    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Hmm, i only considered prefix candidates only for the second index, thought that would be enough and that's what i got wrong. Thanks for the lucid explanation.

      → Reply
»
9 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Charge customers more for no reason. Real nice promotion there, Bob.

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C is just greedy.

→ Reply
»
9 days ago, # |
  Vote: I like it +5 Vote: I do not like it

div 3

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Almost gave up on C cuz it didn't click to me at all.

→ Reply
»
9 days ago, # |
  Vote: I like it +1 Vote: I do not like it

D was Nice. C was harder than D and E.

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial hasnt been added to contest materials yet

→ Reply
»
9 days ago, # |
  Vote: I like it +15 Vote: I do not like it

Just did virtual, almost AKed them (missed possible overflow on F but got it few minutes after the end).

Feedback: nice problems and solutions, but next time please use "index" instead of "number". Both problems A and D had this issue and I spent more time trying to understand the examples on A than solving the problem. Overall really nice problems

→ Reply
»
9 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

why binary search on k from 0 to min(n,b) is not giving correct answer for all testcases?what necessary must be done to make it work all testcases ?

int maxProfit = n*a; int l = 0, r = llmin(n,b), k = 0; while(l <= r) { k = l + (r — l) / 2; int profit = 0; profit += k*b — ((k-1)*k)/2; profit += (n-k) * a; maxProfit = llmax(maxProfit, profit); if(maxProfit <= profit) { l = k+1; } else { r = k-1; } } cout << maxProfit << "\n";

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

    Because it is not a monotonic space in k the function is quadratic in k. Can you tell me what your check function does in your binary search i can explain better if u tell that

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

      it checks,

      if profit for current k is greater than previously calculated profit, l = k + 1; i.e. BS in higher values of k.

      else if it is less than privously calculated profit, r = k -1; i.e. BS in lower values of k

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

        look for the graph of quadratic function a*x^2 + b*x + c where a is negative its a concave curve in downward direction not linear. So there is no monotonic space for the binary search to begin with. this is a monotonous space i'm talking about

        Y Y Y Y Y Y N N N N N

        k = 0 1 2 3 4 5 6 7 8 9 10

        Y is true and N is false for the check function this is required for binary search this will not occur in this case.

        You cannot binary search on k. But you can binary search on the maximum answer if you want with low = 0 and max 1e18 i guess its possible but we may get exceptions

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

        must be doing something wrong as my BS solution was accepted calculate profit at mi d and mid+1 then move accordingly

        → Reply
        • »
          »
          »
          »
          »
          5 days ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          if(till_mid<after_mid){ st=mid+1; } else{ end=mid-1; } Nice observation, The graph(coins vs k) for any test case will always be subgraph of a downward concave graph. so, This suits well.

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

    I just Used Math. It is Much Easier to solve using Math. 265997636

    → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

266121556 Can anyone tell me what's wrong with my problem D solution, it fails in the second test.

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

    I cannot Understand your code. You can check my code and understand the error. 266164533. I calculated the max number and its position and checked the cases. I guess you were missing a case.

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

      Basically, I pre-calculate leftmax array, rightmax array and presum. After reading the tutorial, I find the leftmax array is not needed and presum array space can also be saved with a variable. Finding the intial winner index is enough. But I am still curious why my code is not equivalent to the tutorial, and my code is stuck by what testcase. Anyway, thanks for your kind reply. Have a good day.

      → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Not sure how many of ya got stuck with C so I wanna share my own — practically author's solution but done almost mindlessly.

Spoiler
Extra thought #1
Extra thought #2
→ Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
- **Can be solve B using binary search whats wrong in this** 
- #include <bits/stdc++.h>
using namespace std;
using ll= unsigned long long int;
ll kvalue(ll n,ll a,ll b){
   ll ans=n*a;
   ll l=1;
   ll r=min(n,b);
   while(l<=r){
      ll mid=(l+r)/2;
      ll sum=b*(b+1)/2;
      sum-=(b-mid)*(b-mid+1)/2;
      sum+=(n-mid)*a;
      if(sum>=ans){ans=max(ans,sum);l=mid+1;}
      else r=mid-1;
   }
   return ans;
}
int main()
{   int t;
    cin>>t;
    while(t--){
          ll n,a,b;
          cin>>n>>a>>b;
          cout<<kvalue(n,a,b)<<endl;
        }
      return 0;
}
→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why was c so difficult to solve :'(

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

cada cuanto hay competencias de programación ?

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest is an example of why you should not stick to only one problem. I personally feel problem D was easier to do than problem C. I could not get the logic of problem C, but when I read problem D, I was quickly able to do it on the first attempt. Kudos to vaaven for creating such a problematic structure. The editorial is excellent

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

1978C - Manhattan Permutations i have solved the problem C theory wise in the contest time itself but when i submitted my solution it was showing runtime error in test case 2 (exit code 11) but i am not able to understand why this is happening ,so i am attaching my code submission here 266059429
i know that my approach is not exactly the same as that of the editorial but this is what i came up with so you can just do a debug session with the first test case of the problem in your editor to get a idea of how my algorithm is generating the sequence

thank you in advance

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

    Exit code 11 looks suspiciously likely to be a SIGSEGV/segmentation fault. Try to notice out-of-bound index access, as the most likely cause.

    Also I found something else fishy: casting k from long back to int is incredibly dangerous. If k is outside of int32 bound, it's certain that in the very first loop it will screw itself up and either make a WA or a different exit-code-11-causing access.

    → Reply
    • »
      »
      »
      9 days ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      can anyone tell me what is error in my logic i have done same as editorial but still cant pass test case 2. my code

      thanks i found it

      → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's consider what happens if we swap x and 1 in the identity permutation. — what does this means in problem c editorial can anyone help me???

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

    The problem wants us to construct an example permutation that is going to give us a Manhattan score of S lets say. A permutation is simply just [1,2,3...n] array with a few swaps right. So the editorial wants you to think what would happen when you swap lets say 1 and x in the identity permutation [1,2,3,..n] notice that you would get a permutation with a score 2*(x-1) , so basically all even number scores between 0 to n^2/2 (the max attainable score) can simply be constructed by using two pointers and swapping the numbers starting from the Identity permutation.

    → Reply
»
8 days ago, # |
  Vote: I like it +2 Vote: I do not like it

I really want to know why didnt the author use index instead of number it was confusing for both in d and a

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

meaningless and boring problem D!

→ Reply
»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

During the contest I used Mo's algorithm (莫队) to solve E and got accepted. Now I noticed I had made it more complicated. Interesting problems!

→ Reply
»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

In Problem D, the answer of the index i should be either 0, i-1 or i(not 0, i or i+1), because the index in the problem starts from 1 instead of 0.

→ Reply
»
8 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Does anyone have any idea why this solution for D does not work?

https://codeforces.net/contest/1978/submission/266203442

It seems to be failing for test case 235. wrong answer 235th numbers differ — expected: '3', found: '4'

Printing out the test case. C=0 and array is 0 1 2 2 0 https://codeforces.net/contest/1978/submission/266202827

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Another approach for problem E using Mo's algorithm

266205187

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

    Solved it with Mo's too, though the complexity is bigger that way.

    → Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can i use Binary search for Prob D ?

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me the 3rd test case of prob D?

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

    6 0
    2 2 2 3 3 3
    1 1 2 0 4 5

    without any deleting the 4th will win, becuase his max & smallest index,
    to win 1st anyone can be deleted
    to win 2nd the 1st must be deleted (a[0]+a[1]>a[imax])
    to win 3rd the 1st&2nd must be deleted
    4th win without any deleted
    5th can win only when the 4th deleted(becuase he is max with smallest index)
    but then first will win, because he get all 4th fans a[0]+a[imax]+c>=a[imax], must delete him,
    then second will win because he'll get 1st and 4th fans, so we should delete all chain till 5th
    6th the same

    → Reply
    • »
      »
      »
      8 days ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks brother, but I wanted to know the 3rd test case , 5 4 3 2 1

      So for 2nd one (4), minimum is 1 removal ,but how?

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

      well i understood ,by number they meant the index

      → Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D: Elections Video Editorial LINK

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why in problem C k must be even??? |z-x|+|x-y|+|y-z| can be odd for 0<x<y<z<n+1

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

    Suppose Parity(x)= 1 if x is odd and 0 if x is even.

    Then Parity(|z-x|+|x-y|+|y-z|)=Parity( Parity(z)+Parity(x)+Parity(x)+Parity(y)+Parity(y)+Parity(z)) = Parity( 2*(Parity(x)+Parity(y)+Parity(y)) ) = 0 indicating it is in fact always even.

    Similarly you can do this for more than 3 numbers, every time result will be even.

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

    if you pick ANY permutation, with parity P. after doing any swap between 2 elements on it, it will stay with the same parity.

    • |a-b|+|c-d| = +-a +-b +-c +-d (doing +- just for generalisation/simplification (it could be + or -))

    • |c-b|+|a-d| = +-a +-b +-c +-d

    • by mod 2 , -1 and 1 are the same thing, so +- doesnt change the parity . as such both values have the same parity. so the over all parity didnt change.

    • as such any number of permutations would not change the parity. and as it starts with parity of 0 then it always stays like so.

    → Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C problem is very interesting. Lot of different though processes you could follow to come up at the greedy solution.

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E, $$$t$$$ is re-defined (both number of test cases and string).

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

D and E are easyer than C

→ Reply
»
7 days ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

For Problem C, we could have an O(1) memory solution by instead realising the following property.

  • assuming the sum is possible ( k multiple of 2 and less than maxK)

  • if we select the largest m such as the total sum achieved by [m,m−1,m−2,...,1] is still less or equal to k. we can permute to k by taking the m+1'th number and permuting/shifting it back, each permute/shift back gives +2. so we can pick the difference between this sum and the required sum and divide it by 2 and thats how much we need to "shift" the m+1'th element. lets call that w

  • so the final answer would be [m,m−1,m−2,..., w+1 , m+1 , w , ... , 1 , m+2 , m+3 , ... , n ] example implementation (could be improved) https://codeforces.net/contest/1978/submission/266337230

more details:

  • the sum achieved by [m,m−1,m−2,...,1] can be calculated into the following formula with few observations ( m*m — (m%2) )/2; so we can use binary search to find m

  • we can prove that each shift back adds +2 to the sum.

→ Reply
»
6 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Could anyone explain why F is $$$O(n\log\log n)$$$? From what I read, we would first do a sieve to find the primes $$$\leq \max{a[]}$$$, which takes $$$O(\log\log(\max{a[]}))$$$ time. Then, we perform unions with DSU if two entries are divisible by the same prime and are less than or equal to $$$d$$$ apart, which can be done in $$$O(n)$$$. But since we do this for each prime found by the sieve and there are $$$\sim \frac{n}{\log{n}}$$$ primes up to $$$n$$$, this algorithm is $$$O\left(\frac{n^2}{\log{n}}\right)$$$, which is too slow.

→ Reply
  • »
    »
    4 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Let's say that some prime $$$p$$$ shows up in positions $$$b_{1}, b_{2}, ..., b_{m}$$$, i.e. $$$a[b_i]$$$ is divisible by $$$p$$$. Notice that we only need to do DSU union for the consecutive case, i.e. we only need to unite $$$b_{i}$$$ and $$$b_{i+1}$$$ which is O(m) operations because we can save when a prime last showed up using a set or something (as we are iterating through the array). Furthermore, among all the primes $$$p$$$ that show up as divisors in a[], the sum of all the $$$m$$$'s is $$$O(n \log (\max a[]))$$$, because each a[i] can show up for at most $$$\log (\max a[])$$$ primes.

    Tbh, I am not sure how the authors got O(n log log (max a[])), I think this problem is actually O(n log (max a[])). Nevermind, it seems like the unique prime factors of a number is usually $$$O(\log \log n)$$$. It doesn't seem like a strict bound though.

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

Any idea why my soln for C is failing for some edge case? https://codeforces.net/contest/1978/submission/266668069

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

    I don't know the exact testcase but by hit and trial your code is failing on this test case:

    1

    16 98

    K calculated from your answer is 92 instead of 98.

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks a lot @ZombieUser .. Yeah, right, there was a bug in my code that I found out through this test case. Have corrected and submitted the correct soln.

      → Reply
»
5 days ago, # |
  Vote: I like it +10 Vote: I do not like it

D is amazing!

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

on c test 2 wrong answer Manhattan value isn't equal to k (test case 1215)

→ Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone explain what condition am I missing here( E ) — submission

→ Reply