Editorial of Pinely Round 3 (Div. 1 + Div. 2)

The official implementations of all the problems are here.

1909A - Distinct Buttons

Author: TheScrasse
Preparation: TheScrasse

1909B - Make Almost Equal With Mod

Author: TheScrasse
Preparation: TheScrasse

1909C - Heavy Intervals

Author: TheScrasse
Preparation: TheScrasse

1909D - Split Plus K

Author: TheScrasse
Preparation: TheScrasse

1909E - Multiple Lamps

Author: TheScrasse
Preparation: TheScrasse

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

Author: TheScrasse
Preparation: TheScrasse

1909G - Pumping Lemma

Author: TheScrasse
Preparation: TheScrasse

1909H - Parallel Swaps Sort

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

1909I - Short Permutation Problem

Author: TheScrasse
Full solution: errorgorn
Preparation: TheScrasse

• 3 days ago, # ^ | Wrong.

  • 3 days ago, # ^ | gcd * 2?

    • 3 days ago, # ^ | Wrong (I tried it)

      • 2 days ago, # ^ | Sort the array and take the GCD of the difference of consecutive elements, then multiply it by 2. AC Submission : 238522780

        • 2 days ago, # ^ | Hi, can you please explain the logic behind the code ? specifically the gcd of differences and multiplying it by 2 part.

        • 47 hours ago, # ^ | I think we need not sort the array, directly taking GCD of absolute value of difference of consecutive element , then multiplying by 2, will be sufficient.

    • 3 days ago, # ^ | gcd tried it its wrong

      • 3 days ago, # ^ | Hi I also saw a code of gcd*2 Can you explain the proof/intuition of gcd*2?

• 3 days ago, # ^ | Wrong for case : 4 8 12 16

  • 2 days ago, # ^ | ← Rev. 2 →   0 it is correct the answer will come out to be 8 =(4*2)

• 3 days ago, # ^ | 1000 2000 7000 11000 16000

• 3 days ago, # ^ | You have to check for all the powers of 2, i.e. 2, 4, 8, 16, 32 ... Proof lies in the bitmasking

• 3 days ago, # ^ | why do i see ur username in red and gradmaster on ur profile .. is it the problem with everybody else

• 3 days ago, # ^ | ← Rev. 2 →   +53 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 and the second one in where 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 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:

  • 3 days ago, # ^ | Ah, unfortunate. Thanks for the insight!

  • 3 days ago, # ^ | 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?

    • 3 days ago, # ^ | 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.

• 3 days ago, # ^ | I think to find upper bound on set r, you should use r.upper_bound(x), not upper_bound(r.begin(), r.end(), x)

• 3 days ago, # ^ | ← Rev. 2 →   +12 idk why but pinely and codeton rounds are biased towards number theory and maths

• 3 days ago, # ^ | can you explain ,thank you

  • 3 days ago, # ^ | 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.

    • 3 days ago, # ^ | can u pls explain in detail

      • 3 days ago, # ^ | 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.

        • 3 days ago, # ^ | ← Rev. 2 →   0 got that tnx!! But how u got intuition of that solution

        • 3 days ago, # ^ | ← Rev. 2 →   0 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

          • 3 days ago, # ^ | ← Rev. 3 →   +13 This property is nicely applied in 1826B - Lunatic Never Content question if anyone is interesting in using this property to practice a task

    • 3 days ago, # ^ | its not correct

      • 3 days ago, # ^ | it works when you do the GCD of the Difference Arrays only as mentioned in the main comment

        • 3 days ago, # ^ | 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.

      • 3 days ago, # ^ | Can you provide a case?

    • 3 days ago, # ^ | 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

      • 3 days ago, # ^ | 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

        • 3 days ago, # ^ | Understood! Thanks for your time

• 3 days ago, # ^ | i was trying a similar approach but got stuck...please explain

• 3 days ago, # ^ | 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.

• 3 days ago, # ^ | 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 :)

  • 3 days ago, # ^ | 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.

• 3 days ago, # ^ | 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.

{

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

• 3 days ago, # ^ | 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.

  • 3 days ago, # ^ | got it

    • 3 days ago, # ^ | can you explain?

      • 2 days ago, # ^ | 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.

• 2 days ago, # ^ | 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;)

3 days ago, # | Worst contest for me so far. Didnt solve any. For who wants to see pure pain:

• 3 days ago, # ^ | please explain why mine 238560256 is wrong. I cant get it

  • 3 days ago, # ^ | got it

• 3 days ago, # ^ | a countertest for 238559680?

  • 3 days ago, # ^ | Consider cases where x = 0. If a special point is at x = 0, y = 1, what does your logic do? What is it supposed to do?

• 3 days ago, # ^ | You didn't participate

• 2 days ago, # ^ | Will it be added to the system tests and the final standing will differ or will be ignored? TheScrasse

  • 2 days ago, # ^ | That test case is invalid because the endpoints are not distinct.

    • 2 days ago, # ^ | ← Rev. 2 →   0 Thanks for replying.

• 3 days ago, # ^ | long long :(

  • 3 days ago, # ^ | Got it, actually I defined my map earlier, after that I used Macro for long long to int conversion ;)

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

• 3 days ago, # ^ | Your output on line 130 is 10 not 2. As a counter-example consider, a = [10, 20]

  • 3 days ago, # ^ | 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. :(

• 3 days ago, # ^ | Assume we create a new board , on which for each number written on our original board (call it ), we write the number on . Then, let's try seeing what our operation does. So, since (for the original board), and since we've written on our modified board instead of , this gives the observation that on , our operation just corresponds to replacing by two numbers such that . Then, solving this reduced problem is pretty easy (for implementation purposes, just subtract from each element of , and do the calculations on that itself).

  • 2 days ago, # ^ | Thanks for explaining.

  • 2 days ago, # ^ | Still I didn't understand it

• 3 days ago, # ^ | it was easy

  • 3 days ago, # ^ | can u explain editorial?

    • 3 days ago, # ^ | 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

      • 2 days ago, # ^ | Thanks for the great explanation

• • 2 days ago, # ^ | ← Rev. 6 →   +13 (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 ? Since the number of moves during the second phase is at most the number of Bs after the first phase, which is at most due to there being no two consecutive Bs and the last letter being an A.

  • 2 days ago, # ^ | ← Rev. 3 →   0 Also curious about these: Were you aware of a solution to H that made 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 operations?

    • 2 days ago, # ^ | H with operations sounds like a considerably more boring problem, as I believe you can simply simulate merge sort: suppose the right part starts at , then you can use operations on , 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 operations is a work of art :)

      • 46 hours ago, # ^ | 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 then this will move some elements right to left over and others left to right over . 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?

        • 34 hours ago, # ^ | Here's how I did it: imagine inserting just the rightmost element of the left half with operations. 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 doesn't need to go that far, and proceed to . Final case is if needs land next to , in which case we add one more swap at the end to achieve that.

          • 34 hours ago, # ^ | ← Rev. 4 →   0 I agree about and , but what if and need to keep moving to the right but you don't want to keep moving to the right? It's true that must move at least as far right as , but once you take into account the fact that must trail two spaces behind to move them rightward at the same speed, this is no longer true.

            • 34 hours ago, # ^ | For we can forget what does, and focus on operations moving . Since they don't want to swap, the same logic keeps applying.

    • 2 days ago, # ^ | ← Rev. 2 →   +10 I was not aware of any linear solution other than the official one. I didn't put as the operation limit to avoid spoilers. The original solution was "put the smallest elements in the left half of the array in operations, then recurse". Some testers found the "merge sort" solution explained by ffao.

• 3 days ago, # ^ | 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

• 2 days ago, # ^ | ← Rev. 2 →   0 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.

• 2 days ago, # ^ | Check my submission,i had different implementation you might find what you are looking for

• 39 hours ago, # ^ | even I got stuck at the gcd approach , the answer would be 2*(gcd of differences of successive terms)

• 45 hours ago, # ^ | ← Rev. 2 →   +33 Actually, you can prove that the number of such subset for is exactly since we can think of each switch associated with a vector and all the vectors are independent, so , , is the basis, and we only care when has less than or equal to bits on (excluding the case it is equal to zero), so we get the above result.

• 2 days ago, # ^ | Consider the case In this case is the best choice, which is incorrect. For only positive values, consider and . In this case smallest is that satisfies the condition, but you can't really make all numbers equal.

• 2 days ago, # ^ | what are you trying to say ? can you explain a little more ?

  • 2 days ago, # ^ | What is the difference between the approach explained in the editorial and my approach?

    • 2 days ago, # ^ | Your approach fails for , , . You claim that it's optimal to keep everything as it is, while the editorial makes , , ( is matched with the closest , which is ). The picture "explains" why the second solution is better than the first.

      • 47 hours ago, # ^ | Hi, I didn't understand the picture can you explain it once? what is the 3 and 5 and what the different colors represent

        • 46 hours ago, # ^ | ← Rev. 2 →   0 The red subinterval is the only one whose cost changes (from to ). 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.

          • 46 hours ago, # ^ | 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)?

• 47 hours ago, # ^ | If button is pressed, then s>>i will be . This line is to check whether pairs are satisfied.

• 43 hours ago, # ^ | Fixed, thanks.

• 76 minutes ago, # ^ | Actually, I only found it while preparing the problem (with constraints ). I was trying to build strong tests (where the valid 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 hours ago, # ^ | 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.

• 26 hours ago, # ^ | In the editorial, . If , you have to swap and .

• 82 minutes ago, # ^ | For each test case, you have to iterate over masks (in the worst case), and for each of them you can check if it works in .