After being stuck at a problem for a while I look at editorial, In the editorial they provide the solution and sometimes the proof to why the solution works
But the problem I face is that a Proof for Solution $$$P\to Q$$$ assumes, if you already know $$$P \to Q$$$ you assume $$$P$$$ and try to prove $$$Q$$$. But in my mind I am unable to formulate $$$P\to Q$$$ and unless I formulate this, I cant Prove it. I am unable to discover the existence of $$$Q$$$. let alone combine them both. It's easy to prove "it" works, than to discover "it"
I can prove "it" but unable to discover "it"   A recent example for me would this:
B. Perfecto
In the editorial, we solve it by going through $$$A = [1, 2, 3, 4, ..., n]$$$
let $$$P_{i}$$$ denote prefix sum i.e $$$P_{i} = \sum_{k=1}^{i}A_k = \frac{i(i+1)}{2}$$$
if at any point the $$$P_i$$$ becomes a perfect square we swap $$$A_{i}$$$ with $$$A_{i+1}$$$ so $$$P_{i}$$$ becomes $$$P_{i}+1$$$
But how do the people who actually solved it and are not the authors of the question came to know "lets swap ith element with (i+1) element and (i+1)th element will not be a perfect square" it sounds so random. Now you can prove "it" works i.e $$$\exists x \in \mathbb{Z}^+ \ (\sum_{k=1}^{i} A_k = x^2) \to \neg\exists y \in \mathbb{Z}^+ \ \text{such that} \ \sum_{k=1}^{i+1} A_k = y^2$$$ we can use contradiction to prove it.
Another example would be this:
Combination Lock
In this question the if n is even then answer is -1, it was straight forward reasoning
But here is where I got stuck, if n is odd you have to come up with a permutation, in the editorial you simply print from $$$[n, n-1, n-2, ..., 1]$$$ After I looked at editorial I wasn't convinced with reverse order, I mean it worked, but there is no way I could have guessed printing reverse will give answer
But I wanted to do it without reversing so I came up with this
eg: [1, x, x, x, x]
curr=1
now perform a single rotation and increment the curr and set the curr index of permutation to curr;
repeat for all (n-1)
But this solution gave a TLE
This is has been happening for a while now, How do I overcome this?

Problem
Submission
What am I missing?

if(remaining_elements%2==0){
            cout<<(x+remaining_elements)<<"\n";
        }else{
            if(on_bits<=1){
                if(remaining_elements==1){
                    if(x==1){
                        cout<<(x+4)<<"\n";
                    }else{
                        cout<<(x+n)<<"\n";
                    }
                }else{
                    cout<<( x+remaining_elements+3)<<"\n";
                }
            }else{
                cout<<(x+remaining_elements+1)<<"\n";
            }
        }
    }

cout<<(x+4)<<"\n" this is pretty much handles a case, if x==1 and there are only one remaining_element i.e n=2

cout<<(x+n)<<"\n", this is when $$$x=2^i$$$ where $$$i \gt 0$$$ and remaining_elements = 1 i.e when n=2

cout<<(x+remaining_elements+3)<<"\n", this handles when we have $$$x=2^i$$$ for $$$i \gt 0$$$ and remaining_elements = {3, 5, ...}

We can generalize this, since remaining_elements will be odd $$$ \gt =3$$$ we can set 0th bit on for all remaining_elements, upto
(remaining_elements-1) then we set 1st bit($$$2^1$$$) for last element and last second so in total : $$$x+(RemainingElements-1)+2+2$$$

so where does this fail?

Problem

In the editorial it was mentioned that upper bound of this problem will be in the order of $$$1000.2^{50}$$$.
But I am unable to understand why is that the case
1)How would the test case for the $$$sum = 1000.2^{50}$$$ would look like?
This is my understanding of the problem:

Apply operation 2 as operation-1 just reverses the array, which doesn't affect the array sum. Reversing and doing operation-2 will just change the sign of the sum.

if we were to reverse the original array and did operation-2

Keep repeating until we have single element left in $$$A$$$ From my point of view it just doesn't feel intuitive that sum could be the order of $$$1000.2^{50}$$$

Submission
Problem

Approach

make the row and column sums to be equal to zero in other words let $$$x=0$$$ then construct the matrix

1. Create two vectors call them as "row_sums" and "col_sums".
   $$$RowSums[i]$$$ corresponds to sum of all elements in $$$row_{i}$$$
   Same goes for col_sums

given $$$A = n\times m$$$ matrix, where it's always the case that $$$A_{1, 1}=0$$$(one based index), here we have 2 options to go to from $$$A_{1,1}$$$

• Go right
• Go down

Right

Going right indirectly means that $$$A_{i, 1} $$$ where $$$i \in [2, n]$$$ for all $$$i$$$ are never went missing these values are unchanged, find column-1 sum then replace $$$A_{1,1}=0$$$ with $$$A_{1,1}=-\sum_{i=1}^{n}{A_{i, 1}}$$$ since $$$A_{1, 1}=0$$$ we can take summation without having to worry about subtracting $$$A_{1,1}$$$ from the column sum
Then update the col_sums and row_sums array. col_sums[1] += $$$A_{1,1}$$$ and row_sums[1] += $$$A_{1,1}$$$
Update the position of the current indexes based on the next character value that comes from string s. if next character is D then increase the row index by 1. if next character is R update column index by 1.

Down

Going Down indirectly means that $$$A_{1, j} $$$ where $$$j \in [2, m]$$$ for all $$$j$$$ are never went missing these values are unchanged, find row-1 sum then replace $$$A_{1,1}=0$$$ with $$$A_{1,1}=-\sum_{j=1}^{m}{A_{1, j}}$$$ since $$$A_{1, 1}=0$$$ we can take summation without having to worry about subtracting $$$A_{1,1}$$$ from the row sum
Then update the col_sums and row_sums array. col_sums[1] += $$$A_{1,1}$$$ and row_sums[1] += $$$A_{1,1}$$$
Update the position of the current indexes based on the next character value that comes from string s. if next character is D then increase the row index by 1. if next character is R update column index by 1.

Repeat the process for all missing values

Imagine a number N which is made of digits d repeating n times
eg:

From row 7 it keeps repeating
The reason i am asking this question due to this Problem

Is there any proof to this or is it just that I have to remember this.

It my first time encountering this pattern

Submission
C1. Adjust The Presentation (Easy Version)

Approach: Assume that answer is "YA" and try to contradict it, if contradicted print "TIDAK"

1. create a unique vector that consists of elements of "b" in such a way that no two consecutive elements are repeating
   b = {1, 1, 2, 2, 3} unqiue = {1, 2, 3}
   
2. create a map mp that stores whether a element element has already occured(useful to verify if the slide encountered, b_i can be given by person with same as b_i).
   eg: b = {1, 2, 2, 1}, a = {1, 2, 3}, since person-1 and person-2 can give slide-1, 2. Then again we encountered slide-1 at b[3](zero index) so person-1(he's visited it) can be rearranged into giving slide-1 at b[3], map stores this information
3. • Iterate through all elements of unique if the index i goes out of bounds for array a then break the loop;
   • if you find a[i] != b[i] && mp[unique[i]]==false then we can't arrange the persons in array to get our element b_i print "TIDAK"

Submission this is the problem I'm trying to solve, my approach is to create a map that consists of each element and their frequency count, then for intial MEX i try to find elements less than MEX and such that x%(mp[i]-MEX)==0 and mp[i]>1. i try to convert that repeating element into MEX, if i couldn't I'll break out and print the MEX as answer, else I'll repeat the process until i reach size of array n. Where am i going wrong?

Submission Problem

Submission : Submission Problem : Problem

problem link: Problem

Submission Link : Submission