Problem C was very nice

Funny thing, I tried something like an $$$O(n^2)$$$ solution for B but after getting TLE I misread the constraints and thought an $$$O(n log n)$$$ solution was required lmao.

My solution is basically to sort all ranges in decreasing order, then for each range, the answer is the biggest element in the range that has not yet been picked. This is easy to accomplish with sets.

Code

Another $$$O(N^2)$$$ solution for B (see 140909239): keep track of how many intervals each number is part of, and for each interval pick the number in [l,r] that intersects the least intervals. This number must be the split point, as all other numbers in [l,r] will appear at least once more in the resulting intervals after splitting.

Bringing this to $$$O(NlogN)$$$ can be done by doing the first phase on its finite differences (so +1 at l and -1 at r+1), then calculating the prefix sum of the array to get the real counts. The second phase can then use a segment tree on top of the array to get the position of the minimum

I think the description in problem A has a little difficulty in reading

I will also use EvErYoNe'S fAvOrItE lAnGuAgE: Pascal.

Ahhh yes, here he is, the classic darkkcyan.

O(1) solution of problem A is cool~

DP solution for problem D: Let's define the state: dp[i][j][di][dj] means that we area at the (i, j) cell and our direction is (di, dj).
It matters which direction we will go rather than which direction we are from when we are at some cell. So we use the direction we will go as (di, dj) when we are at (i, d) cell. For each state, its next state is very clear, such as (1, 1, 1, 1) -> (2, 2, 1, 1). Let f(s) be the next state to state s. Therefore, dp[s] = (100 - p)/100 (1 + dp[f(s)]), in which p is the probability the cell of s can clear the target.
We want to get f(r, c, 0, 0), but there's a cycle. So we represent every dp[s] with the coefficient of f(r, c, 0, 0) and a constant. After that, it only remains to solve a linear equation of one variable.
refer to: 140973956

There's another way to solve problem E, but it's pretty complex :)
We find which node should be duplicated as the tutorial said. We can do DFS on the tree using the order this problem mentioned. And then check whether duplicate nodes one by one.
We define cost(x) means if we duplicate this node, how many nodes(its ancestors(includes itself) that have not been duplicated) will be duplicated.
We use some data structure maintain the cost(x), such as "heavy path decomposition".
But there remains a special case: if a previous node shouldn't be duplicated, every node in its subtree shouldn't be duplicated. So we have to use some data structure maintain this information, such as "Fenwick Tree". This solution is quite straight forward, but it needs many data structure.
140929530

This Editorial says that there is an O(nlogn) solution of problem B. Can anybody tell that if my submission to this problem is O(nlogn)? I think mine is O(logn). I would be thankful if anybody clears my confusion.
1623B - Игра на отрезках
140929468

How problem C is reversed ? Thing is say i index, you get d from i+1 index and 2*d_ from i+2 index. Now in optimal case say in total if i index got x stones. now x = d + 2*d_. When the problem is reversed, d must be equal to d_. Which is not always the case. darkkcyan

I have a question. In problem B, I don't understand. Is the test case 1 5 1 1 1 2 5 5 3 3 1 5 valid?

can anybody pl tell why this code is giving TLE.

include include <bits/stdc++.h> using namespace std; define Code ios_base::sync_with_stdio(false); define By cin.tie(NULL); define Shubh cout.tie(NULL); define ll long long define fl(i,n) for(int i=0;i<n;i++) define rl(i,m,n) for(int i=n;i>=m;i--) define ff first define ss second define pb push_back define mp make_pair define pi 3.141592653589793238 define vr(v) v.begin(),v.end() define rsv(v) v.end(),v.begin() ll mod=1000000007; define vec vector define endl "\n" // Robot Cleaner void solve(){ int n,m,rb,cb,rd,cd,cnt=0,dr=1,dc=1,d=-1,c=-1; cin>>n>>m>>rb>>cb>>rd>>cd; bool got=true; while(got){

if(rb==rd || cb==cd) break;

        else if(rb=n ){
            dr=-1;
        }
        else if(cb=m ){
            dc=-1;
        }
        rb+=dr;
        cb+=dc;
        cnt++;
    }
    cout<<cnt<<endl;

}

int main(){ Code By Shubh int t;cin>>t; while(t--){ solve(); } return 0; }

include

include <bits/stdc++.h>

using namespace std;

define Code ios_base::sync_with_stdio(false);

define By cin.tie(NULL);

define Shubh cout.tie(NULL);

define ll long long

define fl(i,n) for(int i=0;i<n;i++)

define rl(i,m,n) for(int i=n;i>=m;i--)

define ff first

define ss second

define pb push_back

define mp make_pair

define pi 3.141592653589793238

define vr(v) v.begin(),v.end()

define rsv(v) v.end(),v.begin()

ll mod=1000000007;

define vec vector

//Game on Ranges ll power(ll a, ll b){ // a raised to power b ll res=1; while(b){ if(b&1) res=(res*a)%mod; b>>=1; a=(a*a)%mod; } return res; }

int main(){ Code By Shubh int t;cin>>t; while(t--){

}
return 0;

}

Regarding problem D, I have two doubts -

1. How do we claim the maximum length of the cycle is 4*n*m? Is it because there are 4 directions to leave every cell? Can someone share a sample testcase where this maximum cycle length is observed?

2. Per the editorial, how do we claim that 4*(n-1)*(m-1) guaranteed to be a multiple of the longest cycle length?

Please correct me if my doubts themselves reflect any incorrect understanding.

Problem D : let call time(i) is i-th time the robot have same col or row with dirt. ip=(100-p)/100; P=p/100; therefor i think answer is : ans+=time(i)*(ip^(i-1))*P with i from 1 to k. but if i increase k answer is change. what wrong ?? i need help !

can someone please tell me what is wrong with this check function of problem c?

bool check(vector<ll> stones, ll d, ll n) {
 for (ll i = 2; i < n; i++) {
    ll req = 0;
    if (min(stones[i - 1], stones[i - 2]) >= d)
        continue;
    if (stones[i - 1] < stones[i - 2]) {
        req = (d - stones[i - 1]);
    } else {
        req = ceil((d - stones[i - 2]) / 2.0);
    }
    if (stones[i] < 3 * req) {
        req=stones[i]/3;
    }
    stones[i] -= 3 * req;
    stones[i - 1] += req;
    stones[i - 2] += req * 2;
}
for (ll i = 0; i < n; i++) {
    if (stones[i] < d)
        return false;
}
return true;

}

Here is the submission

In problem C's editorial, why they are making cur_h array? I mean what's the intuition. I think it's just a copy of original array. Please anyone clear.

Very nice editorial. Had fun reading it :)

Hey darkkcyan in the editorial of C I think it should be d = $$$\dfrac{h_i - x}{3}$$$ instead of d = $$$\dfrac{h_i}{3}$$$ .

Can anyone pls tell me whether my derived formula for problem D is right or wrong as i am getting wrong answer so i want to know whether there is any implementation error or my formula is wrong.

The O(1) solution explanation for the first one — Robot cleaner is awesome! Also in the pascal solution, I appreciate the usage of the function solve_single.

The solution of problem C uses

int mid = l + (r - l + 1) / 2;

to get mid. I know l + (r — l) / 2 can avoid crossing the boundary (also it is no need, because 2e9 is inside of int) but I cant understand why +1.

Moreover, what this problem bother me except how to know to consider the reversed problem is how to find the max value in desc array...

This contest was unrated?

Very nice editorial. Learning a lot from it

I don't understand why to take (hi'-x) in C and how we know that binary search used here ?? Can anyone explain

darkkcyan Thank you for such interesting problem set!

Can anyone please explain the example from D.

This is clear: 10 10 1 1 10 10 75

We do 9 steps from (1, 1) to (10, 10) so get 75/100.

So logically for me it's mean that we need to check how many steps we need to do clean the dirty once more. And it's 18. Since we have probability 75/100 and we have reminder 25/100.

We can answer: 9 + 18 * 25 / 75 = 15

And in case the fraction is reducible. So the number is understandable.

This is not clear at all: 5 5 1 3 2 2 10

How come we get: 332103349 and not 25?

If probability is 10/100, so I expected that 10 "clears" will do the answer for me.

Please explain if you understand why this don't work.

Note: I know what is reverse element modulo. I hope the answer will be helpful not only for me :)

Although my solution to E was different from the editorial's when upsolving, I thought the problem was super beautiful nonetheless! idk if anyone will care, but here is my proof for the editorial's solution:

Suppose that there exists a lexicographically smaller string $$$s$$$ than the one which our algorithm came up with. Consider some set $$$S \subseteq \{ 1, 2, ..., n \}$$$ of duplicated vertices which yield $$$s$$$. Let $$$u$$$ be the earliest vertex in the tree's inorder traversal such that our algorithm duplicated $$$u$$$, but $$$u \not \in S$$$. Suppose that $$$S$$$ is a set which makes $$$u$$$ as late in the inorder traversal as possible.

Lemma: If there exists a $$$v \in S$$$ such that $$$v$$$ was not selected by our algorithm, $$$v > u$$$.

Let $$$P \subseteq S$$$ be the set of all duplicated vertices selected by our algorithm, which came before $$$u$$$. Let $$$Q \subseteq \{1, 2, ..., n \}$$$ be the set of vertices with labels corresponding to $$$u$$$'s segment of characters. It must be true that $$$(S - P) \cap Q \neq \emptyset$$$, or else our algorithm's string would be lexicographically smaller than $$$s$$$. Consider any $$$v$$$ in this set. Let $$$p = LCA(u, v)$$$. It follows that $$$v$$$ must be in $$$p$$$'s right subtree (and $$$u$$$ in the left), since otherwise from the above lemma, $$$v \in P$$$ (oops, forgot the case when $$$p = v$$$ but w/e things still work). Since all vertices lying along the path from $$$p$$$ to $$$u$$$ are in between $$$p$$$ and $$$v$$$ in the inorder traversal, they all must be in $$$Q$$$. Let $$$x > 0$$$ be the number of vertices along the path from $$$p$$$ to $$$u$$$ which are not in $$$S$$$.

There now exists a simple construction which produces a set of duplications which yields a string at least as good as $$$s$$$: take $$$S$$$, and repeatedly remove vertices $$$w$$$ such that $$$w \in S - P$$$ until $$$\#(S) + x \leq k$$$. Then add those $$$x$$$ vertices to $$$S$$$. Let the newly formed set be $$$S'$$$. Now, $$$P \cup \{u\} \subseteq S'$$$, which contradicts our supposition.

In Stone Heap Question’s solution, why is d written as

Int d = min( h[i],cur_h[i]-x )/3; ? Why do we need h[i]? And why not just

Int d = (cur_h[i]-x )/3;

Also why do we need a global h[i] and cur_h[i] arrays

Thanks in advance!!

why 4(n-1)(m-1)is k — the cycle? help! lengthsince 4(n−1)(m−1) will always be the multiple of k — the cycle length.

For problem D, is there any solid proof that the robot's path form a cycle and the starting point belongs to that cycle. I think the editorial takes this observation for granted.

Note: sorry it should answered by the above comment.

For problem c in editorial it is given that we binary search on x where a condition "every heap can be of size greater than or equal to x" is checked .

Is it necessary that, We can do binary search on x if and only if x continuously takes integer values from 1 to its maximum value(obeying the condition) and after the maximum value it should not obey condition ?.

If so does x takes integer values continuously from one to its maximum value (satisfying above condition) in this question??

Is there anything that we should note about x to do binary search on it?

I cannot for the life of me figure out why my solution to C is timing out:

https://codeforces.net/contest/1623/submission/141359231

it is definitely an NLogN solution

For problem D,I can't understand the reason of 141635448(I copy other's code),I hope someone can help me explain. Thank you very much,I'm using arithmetic summation and dislocation subtraction,so I don't understand how this neat algorithm works.

Why do you need to reverse the heaps for problem C. Why can't you just greedily do it from left to right? Would that greedy not work?

Hello, I guess solution of B has an error--->>>> "vector mark" This is leading to compilation error. Correct me if I am wrong. Thank you

in the problem B i didn't understand how this line "vector mark(n + 1, vector(n + 1));" worked, can somebody please help me with this

Thanks for the adaptive dark theme explanation on problem E! :)