Codeforces Round 983 (Div. 2) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

README: Notice about solutions

2032A - Circuit

Author: AkiLotus
Development: AkiLotus
Hinter: AkiLotus
Editorialist: AkiLotus, Kuroni

Hint #1

Hint #2A

Hint #2B

Tutorial

Solution (C++)

Solution (Python 3)

Feedback

2032B - Medians

Author: Kuroni
Development: AkiLotus
Hinter: Kuroni
Editorialist: AkiLotus, Kuroni

Hint #1

Hint #2A

Hint #2B

Tutorial

Solution (C++)

Solution (Python 3)

Feedback

2032C - Trinity

Author: AkiLotus
Development: AkiLotus
Hinter: AkiLotus
Editorialist: AkiLotus, Kuroni

Hint #1

Hint #2A

Hint #2B

Hint #2C

Hint #3

Hint #4

Hint #5

Tutorial

Solution (C++)

Solution (Python 3)

Feedback

2032D - Genokraken

Author: AkiLotus
Development: AkiLotus
Hinter: AkiLotus
Editorialist: AkiLotus, Kuroni

Hint #1

Hint #2

Hint #3A

Hint #3B

Hint #4

Hint #5

Tutorial

Solution (C++)

Submission link: 289292866

Plaintext

namespace datastruct {
    // A doubly-linked list that only supports modify and (pseudo) deletion at pointer
    class DeleteOnly_DLL {
    public:
        vector<int> values;
        vector<int> prev;
        vector<int> next;
        int pointer;
        
        DeleteOnly_DLL(int size) {
            values.resize(size);
            prev.resize(size);
            next.resize(size);
            
            for (int i = 0; i < size; i++) {
                prev[i] = (i + size - 1) % size;
                next[i] = (i +        1) % size;
            }
            
            pointer = 0;
        }
        
        int current() {
            return values[pointer];
        }
        
        // Set value at pointer and move pointer to next
        void set_and_move(int val) {
            values[pointer] = val;
            pointer = next[pointer];
        }
        
        // "Delete" node and move pointer to next
        void erase() {
            if (prev[pointer] != -1) {
                next[prev[pointer]] = next[pointer];
            }
            if (next[pointer] != -1) {
                prev[next[pointer]] = prev[pointer];
            }
            
            int next_id = next[pointer];
            prev[pointer] = next[pointer] = -1;
            pointer = next_id;
        }
    };
}

namespace solution {
    bool hasMultipleTests = true;

    int n;
    
    int ask(int a, int b) {
        cout << "? " << a << " " << b << endl;
        cout.flush();
        
        int res; cin >> res;
        return res;
    }
    
    void answer(vector<int> &p) {
        cout << "!";
        for (int i=1; i<n; i++) {
            cout << " " << p[i];
        }
        cout << endl;
        cout.flush();
    }

    void preprocess() {

    }

    void input(int testcase) {
        cin >> n;
    }

    void solve(int testcase) {
        vector<int> p(n, -1);
        p[1] = 0;
        
        int r = 2;
        while (true) {
            int response = ask(1, r);
            if (response == -1) exit(2226);
            
            if (response == 1) {
                p[r] = 0;
                r++;
            }
            else break;
        }
        
        int tentacle_count = r - 1;
        
        datastruct::DeleteOnly_DLL tentacles = datastruct::DeleteOnly_DLL(tentacle_count);
        for (int i = 0; i < tentacle_count; i++) {
            tentacles.set_and_move(i + 1);
        }

        p[r] = tentacles.current();
        tentacles.set_and_move(r);
        r++;
        
        while (r < n) {
            int response = ask(tentacles.current(), r);
            if (response == -1) exit(2226);
            
            if (response == 1) {
                tentacles.erase();
            }
            else {
                p[r] = tentacles.current();
                tentacles.set_and_move(r);
                r++;
            }
        }
        
        answer(p);
    }
}

Solution (Python 3)

Submission link: 289292865

Plaintext

class DeleteOnly_DLL:
    def __init__(self, size: int):
        self.values = [None for _ in range(size)]
        self.prev = [(i + size - 1) % size for i in range(size)]
        self.next = [(i +        1) % size for i in range(size)]
        self.pointer = 0
    
    def current(self):
        return self.values[self.pointer]
    
    # Set value at pointer and move pointer to next
    def set_and_move(self, val):
        self.values[self.pointer] = val
        self.pointer = self.next[self.pointer]
        
    # "Delete" node and move pointer to next
    def erase(self):
        if self.prev[self.pointer] != -1:
            self.next[self.prev[self.pointer]] = self.next[self.pointer]
        if self.next[self.pointer] != -1:
            self.prev[self.next[self.pointer]] = self.prev[self.pointer]
        
        next_id = self.next[self.pointer]
        self.prev[self.pointer] = self.next[self.pointer] = -1
        self.pointer = next_id
    
# end DeleteOnly_DLL


class Solution:
    hasMultipleTests = True

    n: int = None
    
    @classmethod
    def ask(cls, a: int, b: int):
        print(f'? {a} {b}', flush=True)
        return int(input())
    
    @classmethod
    def answer(cls, p: list):
        print(f'! {" ".join(map(str, p[1:]))}', flush=True)

    @classmethod
    def preprocess(cls):
        pass

    @classmethod
    def input(cls, testcase):
        cls.n = int(input())

    @classmethod
    def solve(cls, testcase):
        p = [-1 for _ in range(cls.n)]
        p[1] = 0
        
        r = 2
        while True:
            response = cls.ask(1, r)
            if response == -1: exit(2226)
            
            if response == 1:
                p[r] = 0
                r += 1
            else: break
        
        tentacle_count = r - 1
        
        tentacles = DeleteOnly_DLL(size = tentacle_count)
        for i in range(tentacle_count):
            tentacles.set_and_move(i + 1)

        p[r] = tentacles.current()
        tentacles.set_and_move(r)
        r += 1
        
        while r < cls.n:
            response = cls.ask(tentacles.current(), r)
            if response == -1: exit(2226)
            
            if response == 1:
                tentacles.erase()
            else:
                p[r] = tentacles.current()
                tentacles.set_and_move(r)
                r += 1
        
        cls.answer(p)

# end Solution

Feedback

2032E - Balanced

Author: thanhchauns2
Development: thanhchauns2, Sagita_Phoenix
Hinter: AkiLotus
Editorialist: Kuroni, AkiLotus

Hint #1

Hint #2

Hint #3

Hint #4

Hint #5

Hint #6

Hint #7

Hint #8

Tutorial

Solution (C++)

Submission link: 289293300

Plaintext

namespace solution {
    bool hasMultipleTests = true;

    int n;
    vector<int> a;
    
    void apply_prefixes(vector<long long> &prefixes, vector<long long> &v) {
        for (int i = 2; i < n * 2; i++) {
            prefixes[i] += prefixes[i - 2];
        }
        
        for (int i = 0; i < n * 2; i++) {
            v[i % n] += prefixes[i];
        }
    }
    
    void construct_trench(vector<long long> &arr, vector<long long> &v) {
        vector<long long> prefixes(n * 2, 0LL);
        vector<long long> delta(n, 0LL);
        
        for (int i = 0; i < n / 2; i++) {
            long long diff = arr[n - 1 - i] - (arr[i] + delta[i]);
            
            delta[i] += 2 * diff;
            delta[i + 1] += diff;
            
            prefixes[n - i] += diff;
            prefixes[n + i + 2] -= diff;
        }
        
        apply_prefixes(prefixes, v);
        
        for (int i = 0; i < n; i++) {
            arr[i] += v[i] * 2;
            arr[(i + 1) % n] += v[i];
            arr[(i + n - 1) % n] += v[i];
        }
    }
    
    void construct_plateau(vector<long long> &arr, vector<long long> &v) {
        vector<long long> prefixes(n * 2, 0LL);
        vector<long long> delta(n, 0LL);
        
        for (int i = n / 2 - 1; i >= 0; i--) {
            long long diff = arr[i] - (arr[i + 1] + delta[i + 1]);
            
            delta[i] += diff;
            
            prefixes[i + 1] += diff;
            prefixes[n - i] -= diff;
        }
        
        apply_prefixes(prefixes, v);
    }

    void preprocess() {
        
    }

    void input(int testcase) {
        cin >> n;
        a.clear();
        a.resize(n);
        for (auto &z: a) cin >> z;
    }

    void solve(int testcase) {
        if (n == 1) {
            cout << "0\n";
            return;
        }
        
        vector<long long> v(n, 0LL);
        vector<long long> arr(n);
        for (int i = 0; i < n; i++) {
            arr[i] = 1LL * a[i];
        }
        
        construct_trench(arr, v);
        construct_plateau(arr, v);
        
        long long offset = *ranges::min_element(v);
        
        for (auto &z: v) cout << z - offset << " ";
        cout << endl;
    }
}

Solution (Python 3)

Alternative tutorial (Kuroni, rephrased by AkiLotus)

Feedback

2032F - Peanuts

Author: MofK
Development: MofK, AkiLotus
Hinter: AkiLotus
Editorialist: MofK, AkiLotus

Hint #1

Hint #2

Hint #3

Hint #4

Tutorial

Solution (C++)

Solution (Python 3)

Feedback

Comments (59)

Write comment?

heavenly_

4 days ago, # |

Problem D can be solved in $$$\mathcal{O}(n)$$$ with a queue quite easily as well, which is implemented directly into the stl so it's easier. The idea stays the same, just replace the double linked list with a queue

→ Reply

ma_moutahid

4 days ago, # ^ |

I believe there is an even lighter ( implementation wise ) sol to D. I keep track of the next parent to be considered ( stored in variable bp initiated at N-2 ) and the current node ind ( initiated at N-1) who's parent we're looking for, we (decrement ind iff bp is its parent) and decrement bp at each iteration till its 0

That's quite brilliant, though it feels less intuitive to me

Negationist

put an explanation below big dog

parthido

Tutorial of D definitely proves that the problem setter group had Asian influence ..

bihnehminduh

W contest.

PROELECTRO444

← Rev. 3 →

For D, there also exists n — 3 query soln instead of 2 * n — 6 query solution.

← Rev. 2 →

+24

Here is the solution.

def query(a, b):
    print(f'? {a} {b}')
    f = bool(int(input()))
    return f

t = int(input())
for _ in range(t):
    n = int(input())
    parent = [0] * n
    minParent = n - 2
    # for each value of minParent, from n-2 to 2, query will be called exactly once
    # => n-2 - 2 + 1 = n-3 times
    
    for x in range(n - 1, 1, -1):
        while minParent > 1:
            if not query(x, minParent):
                break
            minParent -= 1
        parent[x-1] = minParent
        minParent -= 1
        if minParent < 1:
            break
    print("!", *parent[:-1])

virusss

can someone pls prove the fact that the smallest two elements will always have to be continuous in the original array as well ? I am refering to problem C here

AaravSin

what do you mean by continuous?

IamYessir

it is evident that when the array is sorted, let's say a_1 <= a_2, ...., <= a_n, then of course, when you choose a_1 and a_2, and let's just say there exists a number a_k so that a_1, a_2, a_k are the sides of a non degen triangle, then a_1, a_3, a_k is still acceptable (with 3 < k) because the triangle equality still holds. In other words, the way we choose 2 consecutive elements has set a lower bound to all the answers with bigger number.

lrvideckis

another solution to E, although after reading the alternate solution, I think that is better

we can apply operation [-1,-1,1,1] to index i (e.g. a[i]--,a[i+1]--,a[i+2]++,a[i+3]++) by applying operation [-1,-2,-1] to i, and [1,2,1] to i+1

now, we can apply operation [-1,0,1] to index i by applying operation [-1,-1,1,1] to indexes i,i+2,...,until i-1

we can apply operation [-1,1] to index i by applying operation [-1,0,1] to indexes i,i+2,... until i-1

now applying operation [-1,1] keeps the sum constant, so we just need apply arbitrary operations [1,2,1] until (sum of a)%n==0 which is always possible

289298093

MASTERB4APRIL

same, and yet it's much simpler. 289315539

alexwice

Alternate solutions for E

Write the equations A[i+1] + V[i] + 2 * V[i+1] + V[i+2] = T. [eqn1] Taking differences, (A[i+2] — A[i+1]) + (V[i+3] + V[i+2]) — (V[i+1] + V[i]) = 0 [eqn2]

Solution 1. https://codeforces.me/contest/2032/submission/289289897 Write W[i] = V[i] + V[i+1]. eqn2 is W[i+2] = W[i] + A[i+1] — A[i+2], so we can fill all W[i]'s in terms of W[0], and all coefficients of W[0] are 1. So we can sum all rows of eqn1 to find W[0]. Now we want to solve for V in terms of W, which is easy by taking alternating sums of V[i+1] = W[i] — V[i].

Solution 2. https://codeforces.me/contest/2032/submission/289297804 Notice a solution for T=0 implies a solution for T=4k (V[i] += k). So, guarantee a solution for T=0 by first shifting A, then we can assume T=0. Now V[0] and V[1] determine V. By chasing eqn1, we will get 2 equations and 2 unknowns.

wice city

Andimeo

3 days ago, # ^ |

and all coefficients of W[0] are 1. So we can sum all rows of eqn1 to find W[0].

Could you elaborate more on this line? Thank you.

passwordisa

For C, I sorted then binary search on the minimum number of elements to reassign. 289211192

stils

I thought about binary search during the race, but I didn't finish it

stilss

You might need some WuXing.

Nandan1436

31 hour(s) ago, # ^ |

Could you please explain what you did inside the binary search? I used binary search too but i only kept comparing the sum of two values with the last element, which got WA for the test case "1 1 1 2". I understood that my approach was wrong but confused about the correct one. TIA.

awesomeguy856

Why was n forced odd in E?

Rvess

if n is even operation doesnt change the parity of the difference between sum of even and odd position elements. so if the parity is odd there is no solution

Yes, then you would output -1 according to the statement

ay012

in problem C whats the proof that ax and ay should be consecutive elements of the array in sorted order ? suppose we have x as operations needed using consecutive a[i] and a[i+1] lets say max we can reach is j , now if we let ax to be a[i] and ay to be a[i+2] then j can be much more than the original isnt if we have a[i]+a[i+2]>a[i]+a[i+1]? whats the proof that checking with consecutive elements does the job? AkiLotus

AkiLotus

Without that condition, you can't ensure that all triplets are valid.

One counterexample: $$$[3, 4, 5, 7]$$$. If you used $$$a_i$$$ and $$$a_{i+2}$$$ for pivoting, you'd conclude that $$$0$$$ operations are required, which is not true, as $$$(3, 4, 7)$$$ are invalid.

For your example i will consider the array two minimums be 3,5 now j will reach 7 so we have 3,5,7 max so total ops needed is 4-3=1 because i will change the one (i have not taken) like 4 between 3 and 5 to ay that is 5, so that validity is maintained.

I see, you wanna pick $$$a_i$$$ and the range $$$[a_{i+2}, a_j]$$$. Then... why don't you simply pivot $$$a_{i+1}$$$ and $$$a_{i+2}$$$ for a clearly not-lower upper bound $$$a_{j'}$$$?

okay yeah makes sense thanks

hrishabhpatel09

Finally Pupil

Di_Lorenzo.

Congrats!

SkibidiPilav

D was very fun, and F seems very interesting as well, thank you for the contest and +100 delta :D

misaki646

orz, you almost reach CM now.

papa-ka-para

Thank you for such detailed Editorial. I wish, other authors could also write editorials in such a way.

cockatooo

You can solve problem E by constructing matrix, as this comment pointed out. Its also not necessary to use FFT to solve this. The matrix inverse $$$M^{-1}$$$ is easy to observe, and each element of the inner product $$$(M^{-1}a)_i = -(M^{-1}a)_{i-1} + b_i$$$ where $$$b_i$$$ is a term easy to maintain ($$$b_i = -b_{i-1} + 4a_i$$$).

phsads

+16

my sol for E:

+[1 2 1] can be converted to +[1 1] by doing these operations:

[start = 1] 1 0 1 0 1 0 ... 1 0 1 0 1 0

(the start is the first index that gets affected by the +[1 1])

this can be performed with a prefix sum on odd/even indices

+[1 1] can be converted to +1 by doing these +[1 1] operations:

[start = 1] 0 1 0 1 0 1 ... 0 1 0 1

solving the problem with +1 is free

liugh

so great tutorial with lots of hints!

hundunlilun1

Interesting...

+15

Alternate solution to D by observation alone with ZERO DATA STRUCTURES knowledge required:

We find parents from max to min node, noting that each parent we look for must be less than the minParent we have assigned thus far. i.e if a previous(greater) node had the parent 4, no new nodes can have the parent 4 or greater, since this violates the tree. We can say is that we will never ask for more than n times, because the minParent decreases by 1 for every query(note that two nodes cannot have the same parent besides zero). So maybe we ask in the worst case for n-2 to 1, which is just n-2. 2n-6<n-2 becomes n<4(which is given), so this solution always works. Hope someone like it!

Now onto understanding the actual editiorial...

Yeah I have the same solution and you can actually do in n-3 instead of n-2.

https://codeforces.me/blog/entry/135622?#comment-1214687

Also if we count the number of valid tree for any n it comes out to be $$$2^{n-3}$$$ so n-3 is also the minimum number of queries.

neatshit

I feel like this should be the way every editorial should be written with good hints and simple language tutorial . Nice ;

I_will_keep_trying

It was a really great contest, thank you

i24

Can someone hack this Problem C solution? https://codeforces.me/contest/2032/submission/289342682

I'm quite positive this is wrong but can't find a counterexample. Thank you!

pupsicek

I think your solution is correct, because when we meet $$$a[l]+a[r]\le a[i_0]$$$ we must replace either $$$a[l]$$$ with something greater or $$$a[i_0]$$$ with something smaller. But if we again meet $$$a[l]+a[r]\le a[i_1]$$$ where $$$l=i_0$$$ we again must replace either $$$a[l]$$$ with something greater or $$$a[i_1]$$$ with something smaller. So, we can not replace only $$$a[i_0]$$$ to save one operation.

But what about the case 1 1 1 2? Here, we can't increase $$$a[l]$$$ to 2 because 1 2 1 2 wont make a triangle. Instead, we need to decrease $$$a[i_0]$$$

So, what is wrong? You need EITHER increase $$$a[l]$$$ OR decrease $$$a[i_0]$$$. You would need to increase $$$a[l]$$$ only if you further would need to increase $$$a[i_0]$$$.

tenick

For C, I just want to clarify some terminologies. When is it called sliding window instead of two pointers (or vice versa)? For me C sounded like it's a sliding window problem and not two pointers.

This is just my opinion, for a disclaimer.

I'll usually call something "sliding window" when it involves a fixed interval/range/subarray, and the updates of the window involves removing the leftmost and adding the rightmost per step.

mighty_itachi

for c i guess for 1st test case value is 2 for 7 1 2 3 4 5 6 7 for this test case 2 is minimum since array can become 7 7 3 4 5 6 7

7 7 3 4 5 6 7 is not valid since 3+4=7. You would have to replace the 3 with something else as well

misteg168

+27

Cool solution to E:

Let $$$b$$$ be an array of operations such that you "add 1" to the first position.

Let $$$c$$$ be the array of how many operations each position needs (i.e. $$$c_i = max(a) - a_i$$$).

The solution is the coefficients of $$$(\sum_{n=0}^{n-1} b_i x^i) (\sum_{n=0}^{n-1} c_i x^i)$$$, you can use FFT or any similar algorithm.

mhmakelvin

Details of the solution:

WLOG, assume the "Add 1" process is applying to the middle element $$$(i.e. a_{\frac{n+1}{2}})$$$ for easier calculation

Observe that

For $$$n = 5$$$ the array $$$b$$$ will be $$$[1,0,2,0,1]$$$

For $$$n = 7$$$ the array $$$b$$$ will be $$$[1,2,0,3,0,2,1]$$$

For $$$n = 9$$$ the array $$$b$$$ will be $$$[2,1,3,0,4,0,3,1,2]$$$

For $$$n = 11$$$ the array $$$b$$$ will be $$$[2,3,1,4,0,5,0,4,1,3,2]$$$

Hence we can guess that for any n. This code can geneate a array that add 1 to the middle element. (I will skip the proof here)

  v[n/2] = n/2;

  for (int i = n/2 - 2; i >= 0; i -= 2) {
    v[i] = v[i+2] - 1;
  }

  for (int i = n/2 + 2; i < n; i += 2) {
    v[i] = v[i-2] - 1;
  }

  for (int i = n/2 - 3; i >= 0; i -= 2) {
    v[i] = v[i+2] + 1;
  }

  for (int i = n/2 + 3; i < n; i += 2) {
    v[i] = v[i-2] + 1;
  }

Then by rotating the array, we can get the desired $$$b$$$ that add 1 to the first element

e.g. $$$[2,0,1,1,0]$$$ for n = 5

My submission in contest : 289280927

_bom_bom_

3 days ago, # |

Problem D. Can someone help me explain why the vertices is indexed in accordance to a BFS?

0
1   2   3 ... m
|   |   |     |
m+1 m+2 m+4   m+5
    |
    m+3

bfs order is (0, 1, 2, ..., m, m+1, m+2, m+4, m+5, m+3), but i dont see controdictions to px <= py iff x <= y

Naman_g17

There is a contradiction in your graph, as the parent of m+3 is m+2, while the parent of m+4 is 3. Clearly, m+2 > 3, while m+3 < m+4.

Naman1213

Hi Naman!

somanyducks

42 hours ago, # |

AkiLotus hi! for problem c, why's the answer for the tc "1 1 2" one? shouldn't the answer be zero (because no pairwise distinct triplets exist?)

thank you for writing this round, it was fun!

42 hours ago, # ^ |

"Pairwise-distinct" here applies for indices, not values.

Oops. Thank you for your quick reply.

purupuddu

3 hours ago, # |

← Rev. 5 →

I know I'm late, but i have a nice solution for E.

Look at the differences between adjacent elements. If you sum them you get 0 because the array is circular. You can notice that an operation adds [1, 1, -1, -1] to a subarray of the differences. The goal is to make this array 0, to make the original array constant.
After using this operation many times on alternating positions this happens (the parentheses are the center of the operation)

    [0, 0, 1, (1), -1, -1, 0]
    [-1, 0, 1, 1, 0, (0), -1]
    [(0), -1, 0, 1, 0,  0, 0]

With these operations it's possible to move an unit from a point to another at distance -2. Since the length of the array is odd, then it's possible to move an unit to any other cell of the differences array by just repeating this process

290156342

AkiLotus's blog