### darkkcyan's blog

By darkkcyan, 5 months ago,

In my opinion, all of the problems have a very simple solution and actually require no special data structure at all. To demonstrate the point, I will also use EvErYoNe'S fAvOrItE lAnGuAgE: Pascal.

I will also include some notes, which are not related to the solution at all, but I find them interesting, so I will also include them in.

## A. Robot Cleaner

Obviously, the problem is solvable using simulation. But it is solvable in $O(1)$ time as well, and I will discuss it.

Tutorial
Problem note

Pascal solution: 140968868. C++ solution: 140968900

## B. Game On Ranges

There are a lot of solutions to this problem. The solution I described below might be the simplest in my opinion.

Tutorial
Problem note

Pascal solution: 140968967. C++ solution: 140968942

## C. Balanced Stone Heaps

Tutorial

Pascal solution: 140968985 C++ solution: 140969004

## D. Robot Cleaner Revisit

Tutorial
Problem note

Pascal solution: 140969014 C++ solution: 140969025

## E. Middle Duplication

Tutorial
Problem note

Pascal solution: 140969053 C++ solution: 140969037

• +221

 » 5 months ago, # | ← Rev. 2 →   +19 Problem C was very niceFunny 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
•  » » 5 months ago, # ^ |   0 I choose the smallest element in the range that has not yet been picked.And I got runtimeerror.
•  » » » 5 months ago, # ^ |   0 Had the same problem, basically I had a bug in the compare function that I gave to sort() (my idea was to sort by increasing range "length" (r-l+1) and then select for each range the first number in it that I haven't used in a previous range). vector used(n+1, false); for (auto it : v) { int res = 0; rep (i, it.x, it.y+1) { if (!used[i]) { res = i; used[i] = true; break; } } printf("%d %d %d\n", it.x, it.y, res); } The bug was in : sort( ITER(v), [](const ipair &a, const ipair &b) -> bool { return (a.y - a.x) <= (b.y - b.x); }); This worked : sort( ITER(v), [](const ipair &a, const ipair &b) -> bool { return (a.y - a.x) < (b.y - b.x); }); 
•  » » » 4 months ago, # ^ |   0 My solution got accepted doing that
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 I almost did the same, but I first assigned the values to those range whose start and end values are same and then I sorted them in increasing order of end of ranges. bool comp(vector& a, vector& b) { return a[1] < b[1]; } void solve() { int n; cin >> n; vector> v; vector> temp; for(int i = 0; i < n; i++) { int a, b; cin >> a >> b; v.pb({ a, b }); } vector ans(n, 0); set st; for(int i = 1; i <= n; i++) st.insert(i); for(int i = 0; i < n; i++) { // cout << v[i].fi << " " << v[i].se << "\n"; if(v[i].fi == v[i].se) { ans[i] = v[i].fi; st.erase(v[i].fi); } else { temp.pb({ v[i].fi, v[i].se, i }); } } sort(begin(temp), end(temp), comp); for(auto x: temp) { int ind = x[2]; auto val = st.lower_bound(x[0]); if(val != st.end()) { ans[ind] = *val; st.erase(val); } } for(int i = 0; i < n; i++) cout << v[i].fi << " " << v[i].se << " " << ans[i] << "\n"; cout << endl; } 
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 My solution for B was completely different from other solutions. My solution was to sort the ranges based in ascending order for first element and descending order for second element. If both numbers in the range were the same, then obviously we have to pick that number as d. Otherwise, for every adjacent pair of ranges, if both of the first element are same, we take min of second element + 1 as $d$, if both of the second element are same we take max of first element-1. Complexity is $O(NLogN)$ I think.Here is my solution — 141339457
•  » » 4 months ago, # ^ |   0 Can you please explain why your approach for Problem B is working, I am not able to prove it myself
 » 5 months ago, # |   +3 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
•  » » 5 months ago, # ^ |   0 Hey, I referred to a solution in this video — https://www.youtube.com/watch?v=FI8p-DEglxU&t=1s, I understood the solution easily but is the solution in this video also a O(NlogN) solution. Can somebody clarify the same.
•  » » » 5 months ago, # ^ |   0 Yeah that looks like an $O(NlogN)$ solution as well
 » 5 months ago, # | ← Rev. 3 →   +37 I think the description in problem A has a little difficulty in reading
•  » » 5 months ago, # ^ | ← Rev. 3 →   +21 I am sorry for long statement. Everything written in the statement are just for formality. The parts of the statement are: Definition of a floor. Definition of a position. Moving rule explaination. Cleaning rule explaination. The actual problem. Without the parts above I think it is also hard to understand the statement. Maybe you have some suggestions?
 » 5 months ago, # |   +24 I will also use EvErYoNe'S fAvOrItE lAnGuAgE: Pascal. Ahhh yes, here he is, the classic darkkcyan.
 » 5 months ago, # |   +8 O(1) solution of problem A is cool~
 » 5 months ago, # |   +4 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
 » 5 months ago, # |   0 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
 » 5 months ago, # |   0 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 - Game on Ranges 140929468
•  » » 5 months ago, # ^ |   0 I think your solution is O(n^2). It seems like you have to go through every cell of matrix n*n, and your output is clearly n * n loop.
•  » » » 5 months ago, # ^ |   0 Your solution is $O(N^2)$, the $O(NlogN)$ solution uses sorting.
•  » » 5 months ago, # ^ |   0 nope. yours one is not $O(log n)$. it is $O(n^2)$. the loop in foo() function can run n times in worst case. also you are printing answers by $O(n^2)$ operations (as two nested loops).
•  » » 5 months ago, # ^ |   0 You can refer to this solution, easily explained here https://www.youtube.com/watch?v=FI8p-DEglxU&t=1s
 » 5 months ago, # |   0 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
•  » » 5 months ago, # ^ |   0 Did you see the code? I was also not very sure about editorial solution after reading it but once I saw the code, it made complete sense. Please see the implementation once.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 yes mister_bull d & d_ will be different.way you can look at when moving from 0 to n-3, index i gets d from i+1 and 2*d_ from i+2but when we look at the same problem moving in reverse order from n-1 to 2 we can try moving maximum stones to i-1 and i-2 after leaving atleast x at index. so max that can be moved is min( original_hi/3, (rolling_hi-x)/3 )
 » 5 months ago, # |   0 O(n^2 *logn) solution should also pass for B. Why am getting TLE (BFS type sol,) Link : https://codeforces.com/contest/1623/submission/140934881
 » 5 months ago, # | ← Rev. 4 →   0 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?
•  » » 5 months ago, # ^ |   0 no bro. i think its invalid
•  » » » 5 months ago, # ^ |   0 I found that in range 1 1, I choose 1. In range 1 2, I have to choose 2. 3 3 I choose 3. And 5 5 I chosse 5. So finally, I have to choose 4 in range 1 5. It's the only way. So why?
•  » » » » 5 months ago, # ^ |   0 When you choose 4 in the range 1-5 then two new ranges (1-3) and (5-5) are formed. I don't see the range 1-3 anywhere in the testcase.
»
5 months ago, # |
Rev. 2   -48

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 <bits/stdc++.h>

using namespace std;

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

}

•  » » 5 months ago, # ^ |   0 fix you comment plz
•  » » 5 months ago, # ^ |   0 You can refer to the solution here, the code is well explained https://www.youtube.com/watch?v=FI8p-DEglxU&t=1s
•  » » » 5 months ago, # ^ |   0 thank you
 » 5 months ago, # |   +3 Regarding problem D, I have two doubts - 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? 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.
•  » » 5 months ago, # ^ |   +6 I don't think that there will be a case where all of the states can be visited. This can be proven as follows. If there is a cycle containing all states, it should also contain 4 corners. But the maximum number of corners that can be contained will be at most 2. Without loss of generality, let's just start at one corner. Once we meet another corner, our path is tracing back, therefore we can only visit the cells that we have already visited, and when we came back to the started corner, the robot bounces back as well. So no, there is no configuration that the robot can visit all of the possible states.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +15 And for the second question. Rather than proving that $4 (n - 1) (m -1)$ is the multiple of the cycle length, let's just prove that after $4 (n - 1)(m - 1)$, the robot came back to the initial position.Let's first think about why there is $-1$ in the formula. It is because from $1$ to $n$ the robot can move exactly $n - 1$ steps, and similarly, $m - 1$ steps for $1$ to $m$.We can see that after each $2 (n - 1)$ steps, the robot can go back to its original row with the original vertical direction, and after $2 (m - 1)$ steps, the robot can go back to its original column with the original horizontal direction. So after $4 (n - 1) (m - 1)$ steps, the robot must have the same row, the same column, and the same direction as it initially has.
•  » » » 5 months ago, # ^ |   0 Your reply has been very helpful to me.
 » 5 months ago, # | ← Rev. 3 →   0 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 !
 » 5 months ago, # | ← Rev. 3 →   0 can someone please tell me what is wrong with this check function of problem c? bool check(vector 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
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 You should iterate from back to front of the vector because if you go from front to back you won't know how much the next element will give you.
•  » » » 5 months ago, # ^ |   0 can you please give me a sample test case?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 This case 4 18 2 19 100 You code output is 25, but the solution is 28.
•  » » » » » 5 months ago, # ^ |   0 thanks buddy
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   0 cur_h is the array we are working on, and we will modify it while we are doing the process, in the editorial, that is the $h'[]$ array. The h array, on the other hand, will remain unchanged, since I also wanted its original value while doing calculation, as well as using it for the future call of the function.
•  » » » 5 months ago, # ^ |   0 Yeah got it, thank you very much. Can you please once tell me how we're finding d? "int d = min(h[i], cur_h[i] — x) / 3", why we're subtracting x?
•  » » » » 5 months ago, # ^ |   0 What we want is to make every heap not less than $x$. So when $cur_h[i]\ge x$, we can say that we have $cur_h[i]-x$ stones to spare, and we should just give away those stones.
•  » » » » » 5 months ago, # ^ |   +8 Ohh yes, got it thank you.
 » 5 months ago, # |   +15 Very nice editorial. Had fun reading it :)
•  » » 5 months ago, # ^ |   +10 Thank you so much! I really appreciate it.
 » 5 months ago, # |   0 I have tried to use 2 functions for problem C, one gives WA and other passes , can some1 explain why https://codeforces.com/contest/1623/submission/140962174
 » 5 months ago, # |   +8 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}$ .
•  » » 5 months ago, # ^ |   +3 You are right! My bad. I will fix it.Thank you for your report!
 » 5 months ago, # |   0 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. Formula
•  » » 5 months ago, # ^ |   0 That looks good, if t_n is the length of the cycle. You can then simplify that expression to get a closed form:)
•  » » » 5 months ago, # ^ |   0 n is length of cycle and t_n is the time to reach to the last cell in a cycle from where the dirty cell can be cleaned.
•  » » » » 5 months ago, # ^ |   0 oh ok, I think you need to replace t_n in your formula with the time it takes to reach the starting position again. Imagine that we are in the second round of the cycle, then the time t_n * x + t_i will not be right since you have skipped the interval from t_n to the time it takes to reach the starting position.
•  » » » » » 5 months ago, # ^ |   0 Thanks now i found the mistake thanks for your reply :)
•  » » » » » » 5 months ago, # ^ |   0 You're welcome:)
 » 5 months ago, # |   +8 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.
 » 5 months ago, # | ← Rev. 2 →   0 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...
 » 5 months ago, # |   +5 This contest was unrated?
 » 5 months ago, # | ← Rev. 2 →   +8 Very nice editorial. Learning a lot from it
 » 5 months ago, # | ← Rev. 2 →   0 I don't understand why to take (hi'-x) in C and how we know that binary search used here ?? Can anyone explain
•  » » 5 months ago, # ^ |   0 For binary search, the question that needs to be asked in this problem is If we have a number $x$, can we, somehow, make all the heap not less than $x$? And we can see that, if the answer to this question is true for a number $x$, then for all number $y \le x$, the answer for that question is true as well, since we can use the same moving plan as if you are trying to make all the heap $\le$ x.In other words, the "question" is a boolean function, which must be monotone for us to be able to do binary searching. For more details, I think you should read other articles about this topic.For the question "why should we take $h'[i] - x$", I have answered one question above it. You can scroll up, or click the link here to jump to the answer https://codeforces.com/blog/entry/98463?#comment-872704
 » 5 months ago, # |   0 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 75We 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 = 15And in case the fraction is reducible. So the number is understandable.This is not clear at all: 5 5 1 3 2 2 10How 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 :)
•  » » 5 months ago, # ^ |   0 Well, I purposely put that test there just to test the code, since that test is complicated enough. So, statistically, if you passed 2 last example test cases, then you have very high chance of being AC.
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 Everything I will do below will be the same as the "hand solving algorithm", described in the editorial. Let's see the animation.If it is not playing for some reason, you can click here https://gifyu.com/image/SSFPlThe probability of cleaning is $10\%$, so the probability of not cleaning $\overline p$ is $0.9$.The cycle length is 8. Let answer for each state be $x_1, x_2, x_3, \ldots, x_8$. The system of equations will be: $\begin{cases} x_1 = 1 + x_2 \\ x_2 = 0.9 \times (1 + x_3) \\ x_3 = 1 + x_4 \\ x_4 = 1 + x_5 \\ x_5 = 1 + x_6 \\ x_6 = 0.9 \times (1 + x_7) \\ x_7 = 1 + x_8 \\ x_8 = 0.9 \times (1 + x_1) \end{cases}$Substituting them back to back, we will have the equation for $x_1$. $x_1 = x = 1 + 0.9 \times (1 + 1 + 1 + 1 + 0.9 \times (1 + 1 + 0.9 \times (1 + x_1)))$You can solve this equation by hand, or slap it into WolframAlpha, and it will solve for you like this https://www.wolframalpha.com/input/?i=x+%3D+1+%2B+9+%2F+10+*+%281+%2B+1+%2B+1+%2B+1++%2B+9%2F+10+*+%281+%2B+1+%2B+9%2F10+*+%281+%2B+x%29%29%29The answer for $x_1$ will be $\frac {6949} {271}$. And this is indeed $332103349$ modulo $10^9 + 7$.P.S: I feel like you don't really read the editorial. Please read it first. It literally contains two examples of hand calculation. I did spend a little amount of time just for this answer, but I really feel like it is not worth it.
•  » » » 5 months ago, # ^ |   0 Hi, I understand that the formulas are very cool, but if you check the animation, you will see that each circle clears a dirty cell 3 times. One circle contains 8 seconds. And I agree with the previous statement. It need 25 seconds. May be i was rude (i know English very bad)
•  » » » » 5 months ago, # ^ |   0 The animation (or rather, the cycle) is 8 seconds but it is not guaranteed that after 1 cycle the robot is going to clean the dirty cell. That is because of the probability. If it could not clean the cell in one cycle, it must of course continue its journey until the dirty cell is cleaned.If you calculate the value of $\frac {6949} {271}$, you will get $25.6420664207$, which is IMO close to your intuition.
•  » » » » » 5 months ago, # ^ |   -8 Do I understand correctly that if we have a 10% chance, then the mathematical expectation of cleaning will be in ten tries? If yes, then the correct answer is 25, because one circle is 8 seconds and 3 clears. 24 seconds — 3 circles and 9 cleanups, and at 25 seconds the required 10 iteration will occur.
•  » » » » » » 5 months ago, # ^ |   0 No, that is the totally wrong way to understand it.Simply put, for this concrete example, the process is the following:When you have an opportunity to clean the cell (that is, either the robot's row position is the same as the dirty cell's row position, or their column position are the same), you will roll a dice with 10 faces. If you rolled on $1$, you can clean the dirty cell and stop the process. Otherwise, if you rolled on on $9$ other faces, you must continue the clean up journey. And this process can actually take forever.It will be better to write down the probability branch as follows. You go from the initial position to the cell $(2, 4)$. There, you got a opportunity to clean the dirty cell, and the chance is $10\%$. So you can expect, $1$ out of $10$ time running the robot, it will cleans the dirty cell. Otherwise, the robot continues its journey. When it is at the position $(4, 2)$, it has another opportunity to clean the dirty cell. The chance is the same, it is $10\%$. So you can, again, expect $1$ out of $10$ time running the robot that has failed to clean the dirty cell from the step 1 (or, in other word, $10\%$ of $90\%$, or $9\%$ of the running time), the robot can clean the dirty cell at this step. Otherwise, the robot continues its journey to the position $(2, 2)$. The reasoning is the same, $1$ out of $10$ time running the robot that has failed to clean the dirty cell from the step 2 (or $90\% \times 90\% \times 10\%$ chance), the robot can clean the dirty cell at this step. Otherwise, it continue its journey to the cell $(2, 4)$, where it has another opportunity to clean the dirty cell, .... $5.$ and so on, ...$69.$ and so on, ...$420.$ and so on, ...$\infty$. forever...
•  » » » » » » 5 months ago, # ^ |   0 Your reasoning only works with geometric distribution. In other word, if the duration between 2 events are the same, then you can safely use your intuition. In the second to last example, the duration between the starting moment and the first cleanup moment, the duration between the first and the second clean up moment, and the duration between the second and the third clean up moment, are different, so you cannot use geometric distribution.The formula that I used in the tutorial are actually one way to prove geometric distribution's mean formula, but in the case it is used in more general sense.
•  » » » » » » » 5 months ago, # ^ |   0 Thank you for answer, but i have one more questions. How i can get 332103349 from 25.6420664207 at c++. Operator % doesn't work.
•  » » » » » » » » 5 months ago, # ^ |   0 Well you should read the problem more careful. It said that the answer can be described as an irreducible faction $\frac x y$, and in this case $x = 6949$, $y = 271$. You need to print out the value $x \times y^{-1}$, modulo $10^9+7$, and here $y^{-1}$ is the modulo inversion of $y$. You can search it up on Google, or simply put, you must print $x \times y^{-1} \equiv x\times y^{10^9 + 7 - 2} \pmod {10^9 + 7}$.
•  » » » » » » » » » 5 months ago, # ^ | ← Rev. 3 →   0 look, if we take x * y1 ^ -1 and mod this 1e9 + 7, then we have 25.6421 cout<< fmod (pow((double) 271, -1) * (double)6949, (double) 1e9+7);
•  » » » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 I think you still don't understand the modulo arithmetic, as well as the purpose of asking the answer under a modulo.Why the hell a lot of problems ask to print the answer under a certain modulo?First of all, the real answer might be hard to compute, as well as to check. If the answer is too big, the computing it requires a number with bigger precision, and it will take a factor of $O(|ans|)$ to $O(|ans|^2)$, based on implementation, where $|ans|$ is the length of the answer (in decimal presentation). This is also true when the answer is not an integer. Sure, we might ask to print, for example, $25.6412$, but that is imprecise, and there might be solution that actually use that imprecision fact to calculate the answer. solution for imprecise answerSimulate the process, for example, $10^6$ steps. Each step we will jump to the next clean up position, using $O(1)$ solution from A. You can calculate the probability of clean up there, multiply it by the distance from the start, then add it to the result. There is no reason to go furthur, since the probability of not clean up after that many iterations is too small, therefore their contribution to the result is insignificant.But, what if, we want the true answer?One of the solutions for this imprecise problem is to use modulo arithmetic. In modulo arithmetic, the answer of the contestant might not also be correctly compute (since lots of number yield the same modulo), but we are now working with small integers, and this time, the imprecise answer can be compensated with doing a lot of tests.Addition, subtraction and multiplication are the same, but not really for division. But mathematician came up with another solution, called modulo inversion, multiply a number by with yield the same result as doing the real number (not under modulo). This inversion thing can be found really fast and easily, using another algorithm called binary exponentiation, if the modulo is prime.So we have all operations, as well as a "fast" way for doing calculation and checking, therefore this is currently the way of doing thing in CP cometitions.So, TL;DR: look up the modulo arithmetic and modulo inversion, as I already told you to do in the last comment.This comment is only for the case, where people said that "oh no he wont explain. What a ratist!". I know you would not say that, but you understand my point.No. Everything you need to learn is up there, on the internet. Please search them up before asking. And I would like to actually not reply anymore.
•  » » » 5 months ago, # ^ |   +8 Thank you for such detailed description! I appreciate your comment(s).I found why my approach is wrong thanks to you. I just needed to read about different distributions. (never heard about Geometric for example)
•  » » » 4 months ago, # ^ | ← Rev. 3 →   +15 I think I am missing something, but why did you initialise $dr$ and $dc$ as $-1$ in your model solution (140969025)? The only reason I can think of currently is that the equation needs to be computed from the inside (so last to first), but I'm not really certain about the intuition behind. Can you briefly explain the idea behind why it has to be reversed? Thank you.Also, is there a way to compute the answer after knowing the expected value after the 1st round and the probability that the dirty cell still hasn't been cleaned? It might be more annoying to compute, but it is more intuitive to me. Currently I have $\sum_{k=0}^{\infty} (Q^i)(x+(4(n-1)(m-1))k)$, where $Q$ is the probability that the cell still hasn't been cleaned ($=(1-\frac{1}{p})^{4(n-1)(m-1)}$) and $x$ is the expected value after the 1st round. Is it possible to use geometric sequences to solve this equation?P.S. The round was very well-prepared! The animations definitely made it easier for me to understand the problem.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +8 For the first question. Yes, your reason is the whole point. You can see the equation again. It has the form of lots of brackets wrapping around the only variable $x$, and here I want to break those brackets out, so the final form of the equation can be $x = a + bx$.For the second question. I think there might be one such solution, and I think the other participants have done so. But that solution I think is really annoying. Maybe you can rewatch Geothermal's stream on the round for more insight (I'm not tagging him here). Here is the link https://codeforces.com/stream/363. But that being said, I do think my solution is really, really simple :)And I'm very glad that you like the round! :)
 » 5 months ago, # | ← Rev. 5 →   +11 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.
 » 5 months ago, # |   0 In Stone Heap Question’s solution, why is d written asInt 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] arraysThanks in advance!!
•  » » 5 months ago, # ^ |   0 You can actually try implementing that and that will not work with the example.I already wrote about this in the editorial, but I will repeat it. The process we are doing is not backward. It is forward. By moving forward, the true limit for the number of moving stones is not cur_h[i], but h[i]. Therefore h[i] must limit the number of moved stones.cur_h[] array does not need to be global. It can be local. The only reason that we need 2 arrays, is because we need both of them to calculate d, as you have written above.
 » 5 months ago, # |   -8 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.
•  » » 5 months ago, # ^ |   0 You should have read the other comments firsthttps://codeforces.com/blog/entry/98463?#comment-872602
 » 5 months ago, # | ← Rev. 2 →   0 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.
 » 5 months ago, # |   0 Gotta hand it to codeforces community... seeing these comments trying to do their best inspires so much.
 » 5 months ago, # |   0 In C according to the tutorial  for (int i = n - 1; i >= 2; --i) { if (cur_h[i] < x) return false; int d = min(h[i], cur_h[i] - x) / 3; cur_h[i - 1] += d; cur_h[i - 2] += 2 * d; // we don't need to fix cur_h[i] since we are not going back } int d = min(h[i], cur_h[i] — x) / 3; Whenever d is taking value (cur_h[i] — x) / 3, it is ok as we know that even after subtracting, we will be left with atleast x there but when d is h[i]/3, how are we dealing with that case can someone explain ? I think I am missing something, I know we are doing that because we don't have that much stones in it but how are we so sure that doing so will guarentee us atleast x stones in curr_h[i].
 » 5 months ago, # |   0 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?
•  » » 5 months ago, # ^ |   0 The condition you have described is called monotone. Yes, the function is monotone, because if there is such a maximum number $x$ that the condition is satisfied, then for all numbers $y \le x$, the condition is also satisfied for them. That is because, we know that we can somehow make the condition satisfies for $x$, we can do the same so the condition is satisfied for $y$.Based on the definition of the function described in the editorial, the function is obviously continuous on the positive integer domain, since it is monotone.I'm not sure about the last question. Well, you should just do it in the value range of the heaps, and make sure that your calculation is not overflowing.
 » 5 months ago, # |   -8 I cannot for the life of me figure out why my solution to C is timing out:https://codeforces.com/contest/1623/submission/141359231it is definitely an NLogN solution
•  » » 5 months ago, # ^ |   0 In your code you are using accumulate(H.begin(), H.end(), 0). The thing is, the type of the value for storing the answer will be the same as the type of the 3rd argument, and in your code, it is int, therefore it will be overflow! One fix is to change it to 0ll, or, you just take the max value instead of the average.
•  » » » 5 months ago, # ^ |   0 Ah that’s definitely it, thank you!
 » 5 months ago, # |   0 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.
 » 4 months ago, # |   0 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?
•  » » 4 months ago, # ^ |   0 For the first question. We do it in the reverse order since we have enough information to confidently determine the number of stones so that all the stones from the current position till the first position must satisfy our condition. If you still wonder why I think some of the comments above will give you some insight.For the second question. What kind of strategy are you suggesting for the greedy approach? I mean, only "greedy" is not enough to tell how exactly we should determine the number of stones to move. A short answer to this question will be similar to the above: we don't have enough information to determine. But if you have another solution, that you can prove, I would like to hear it.
•  » » » 4 months ago, # ^ |   0 Thanks for responding so quickly! What I was thinking was the exact same approach you used, but going from 2 to n — 1. But I don't think I can prove it.
•  » » » » 4 months ago, # ^ |   0 A small first step for proving is to find a counter-example. If there is none then you can say that your greedy approach might work, at least with random cases.To find such an example, you can implement your own algorithm, and you also need a correct solution. Correct here means that you can take an AC code, or if you doubt those solutions, you can do brute-force. And the test cases can be randomly generated. You can run your algorithm against the correct one to see if they matched. This tip is actually implemented by problem setters for checking their solution, as well as in real contests for the same purpose.But I will tell you that going from left to right is hard.
•  » » » » » 4 months ago, # ^ |   0 Thanks. I think I found a case where my algorithm broke.
•  » » » » » » 2 months ago, # ^ |   0 Can you tell me(an example) exactly where left to right traversal fails ?
•  » » » » » » » 2 months ago, # ^ |   0 I'm not sure I remember, but I'm pretty sure it was something about not having enough stones to move.
•  » » » » » » » » 2 months ago, # ^ |   0 Thanks anyway! I got it
 » 4 months ago, # | ← Rev. 2 →   -10 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
•  » » 4 months ago, # ^ |   0 You must compile that solution with C++17. See the below comment (https://codeforces.com/blog/entry/98463?#comment-881218) for more details, since his question is more direct.
 » 4 months ago, # |   0 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
•  » » 4 months ago, # ^ |   0 That is C++17 features called "type deduction". One of the constructors of vector accepts the size and the initial value of the elements. Here the compiler actually knows the type of the second argument, so in C++17, it can deduce the type for the template parameter, therefore there is no need to declare the template parameter (again). This is huge compared to the previous versions of C++ since you can write multi-dimensional vectors more easily.
•  » » » 4 months ago, # ^ |   +10 That is so helpful. Thank you!
 » 3 months ago, # |   +10 Thanks for the adaptive dark theme explanation on problem E! :)
 » 2 months ago, # |   0 This is a very good editorial , orz to the author! Well written explanations + liked the idea of "problem note".
 » 4 weeks ago, # |   0 There is nothing much in B is it overrated or is there any other way to do more efficently than using maps by bruteforce