### awoo's blog

By awoo, history, 5 weeks ago, translation, 1499A - Domino on Windowsill

Idea: adedalic

Tutorial
Solution (adedalic)

1499B - Binary Removals

Idea: BledDest

Tutorial
Solution (Neon)

1499C - Minimum Grid Path

Idea: adedalic

Tutorial
Solution (adedalic)

1499D - The Number of Pairs

Idea: Neon

Tutorial
Solution (Neon)

1499E - Chaotic Merge

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1499F - Diameter Cuts

Idea: BledDest

Tutorial
Solution (awoo)

1499G - Graph Coloring

Idea: BledDest

Tutorial
Solution (BledDest)  Comments (62)
 » Atlast THE EDITORIAL
 » Why no best hackers :(
•  » » Nice hacking bro
•  » » In problem D, why there are 2^(the number of prime divisors of k) such pairs. Any proof for that please explain!
•  » » » You have two options for each prime factor, either it is the part of x or it is the part of y. So the total number of pairs = 2^(number of prime divisors).
•  » » » Consider each prime factor $p$ of $k$. Assume that the prime $p$ appears $x$ time(s) in the factorization of $k$ ($p^x | k, p^{x + 1} \not| k$), appears $y$ time(s) in $A$'s and $z$ time(s) in $B$'s.Since $\gcd(A, B) = 1$, either $y$ or $z$ must be equal to $0$ (otherwise $p|A, p|B, p|\gcd(A, B)$). Also we have $y + z = x$ for $AB = k$.So there are just $2$ possibilities: $y = 0, z = x$ or $y = x, z = 0$. Because $p$ is one of the prime factors of $k$, $x > 0$ holds. Therefore, the $2$ situations are definitely different.For each prime factor there are $2$ possibilities to "assign" it to $A$ or $B$. Apparently the situation of one prime factor is independent of others. So simply multiply them all and the answer is $2^{\text{number of prime divisors of k}}$.
•  » » » » What's the matter of low prime, i am not getting it. Please explain it.
•  » » » For each prime divisors, we can allocate to either A or B. So for every new prime divisor we have, we can multiply the ans by 2. Hence 2 to the power of the number of prime divisors.
 » Problem C was tricky
•  » » can you explain me C problem pls?
•  » » » Yes please, the editorial for problem C was not very clear.
•  » » » » I didn't solve it too, that's why I am saying it was tricky)
•  » » » » i have solved using this approach... 1. we treat every index i in range [0,n) as the last segment and compute the total cost such that we reach [n,n] and we have used i segments to reach here, and take minimum of all total costs. 2. here, all even indices segments will be for y-axis or x-axis but not both similarly for odd indices segments. 3. now we calculate minimum value in even indices and minimum in odd indices till i. 4. lets say we travel y axis using even indices and x axis using odd indices. 5. To travel n in Y direction it will be ideal if we move by length 1 in all even indices segments and remaining length by minimum value even segment. As we are using all segments up to i, because our assumption is that i is our last segment. because any way we need to use all even segments for travelling y axis. 6. similarly for x axis 7. we take minimum of all values.
•  » » » » You can refer to this video for detailed solution as well as explanation. Link to Explanation
•  » » » The most important thing for problem $C$ is to realise that in any solution of length $k$ you are obliged to move at least $1$ in all the $k$ movements. Therefore, if you iterate over $k$ you know every single $c_i$ for $1 \leq i \leq k$ is added at least once to the cost. This means we can accumulate sum of $c_i$ up to current $k$, we will call this $accum_k$.If $k$ is even we moved $cntUp = k/2$ times up and $cntRight = k/2$ times right. If $k$ is odd then it's floor($\frac{k}{2}$) $+ 1$ in one direction and floor($\frac{k}{2}$) in the other, just try both possibilities of assigning this to $cntUp$ and $cntRight$. Since we have already taken into account moving at least 1 every time, we just have to calculate the cost of moving $n - cntUp$ units up and $n - cntRight$ times right considering only $c_i$ with $1 \leq i \leq k$.Actually, you can only use $c_i$ with odd $i$ for the direction you start with and only $c_i$ with even $i$ for the other direction. Also, you can easily see the optimal way to traverse the remaining units is to do so at the step with minimum $c_i$. This is why we compute a $minOdd$ and $minEven$ while we iterate over $k$.So to get the optimal answer for a given $k$:If $k$ is even $cntUp == cntRight$, so it doesn't matter if we start up or right and the answer is $accum_k + (n - cntUp)*minOdd + (n - cntRight)*minEven$If $k$ is odd we try both possibilities of starting up or right, so we choose the minimum between $accum_k + (n - cntUp)*minOdd + (n - cntRight)*minEven$ where $cntUp =$ floor($\frac{k}{2}$) $+ 1$ and $cntRight =$ floor($\frac{k}{2}$) and $accum_k + (n - cntUp)*minEven + (n - cntRight)*minOdd$ with $cntUp$ and $cntRight$ from the previous case swapped.We do this for every $k$, not forgetting to update $minEven$ and $minOdd$ in the corresponding iterations, and take the minimum from all possible $k$.
•  » » » 5 weeks ago, # ^ | ← Rev. 5 →   This is what i think: In order to go from (0, 0) to (n, n), we move both up and right exactly n times. So the sum of length of segment of each direction is equal to n. Ex: n = 3 R1 U R2 (R1 + R2 = U = 3) 1 3 2 is right 3 3 0 is right // zero(s) don't appear in front of any positive number 3 0 3 -> wrong ! ____> (n, n) | | (0, 0)>__| The formula above can be explained: consider i (0i th the length 1 and one minimal cost the length (n - cnt + 1) (length i+1->n-1 = 0) So the answer is the minimal result of all i = 1->n-1 
•  » » » This is what my approach to problem C was: We are to go from origin(0,0) to a point (n,n),using no more than (n-1) turns. We can either go up or go right.It is important to realize that whichever direction we may start(up or right),it doesn't matter as in both the directions,we need to cover a distance equivalent to 'n' because going from (0,0) to (n,n) implies going 'n' units along x-axis and going 'n' units along y-axis. Now,we may realize that the "costs" given to us can be seen as 2different options,i.e. costs at even positions may be used to traverse along x-axis,and costs at odd positions maybe used to traverse along y-axis(you may even say that even positioned costs are used to traverse along y-axis and so on.As I said earlier,it doesn't matter whether you start from right or up as your first step)Just make sure that going right or up means that you can only use alternate "cost" values. Now,we may try a greedy approach by saying that let our answer be : n*(cost)+n*(cost) And we may say that in the above expression,there are (n-1) steps that we may remove and take those steps with another cost value,if we get a better alternative in future. WHY?because in the worst case,we at least need to take '1' step for cost and '1' step for cost,to even reach in a position to use value of cost. Now,we traverse along the cost vector,and at every alternate position,we see that if the current cost is less than the cost that we used before,it means that we can take away the "removable steps" from the previous "higher" cost,and consider them from the current "lower" cost. Alternatively,if we find that the current cost is greater than the previous cost,we can just take one step and look for future values to see,if the final cost comes out to be less. Finally,we store all the cost values as we go along computing the cost,and in the end, print the minimum value of cost. Here's a link to my implementation of the above logic: https://codeforces.com/contest/1499/submission/110359103
 » In problem F, we can merge subtrees in $O(k)$ time by computing prefix sums but the only problem is that we might need to calculate inverses which TLE'd for me :( then i just iterated upto max height which worked well (along with calculating inverses).
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   We can merge all subtrees of a node $u$ in $O(deg(u)\cdot k)$ with prefix sums, which leads to a $O(n\cdot k)$ solution, I did it without any divisions.
•  » » » Can you explain how you merged the subtrees without calculating mod inverses?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   Let's denote $dp_{u,x}$ as the number of ways to partition the subtree of $u$, having a diameter equal or smaller than $k$, and the longest path starting from $u$ having a length of exactly $x$, and $ac_{u,x}$ as the number of ways to partition the subtree of $u$, having a diameter equal or smaller than $k$, and the longest path starting from $u$ having a length of at most $x$.Now the transitions: If $2\cdot(x + 1) \leq k$ then $ac_{u,x+1}$ is equal to $\prod_{v \in children(u)} ac_{v,x}$. Else, $dp_{v,x+1}$ is equal to $\sum_{v \in children(u)} f_{v,x}$ where $f_{v,x} = dp_{v,x} \cdot \prod_{w \in children(u), w \neq v} ac_{v,k-x-2}$ Having at least one of $dp_{u,x}$ or $ac_{u,x}$ we can get the other easily, then the first case can be computed naively, and for the second one, it's possible to precompute for each prefix of childrens $\prod ac_{v,k-x-2}$, and also for each suffix, with this we can get all the things we need from some node $u$ in $O(deg_u*k)$
•  » » How did you get a way around with the inverses?
•  » » » I suppose that is similar to the solution that I described above, but instead of precompute for each prefix and suffix of childrens $\prod{ac_{v,k-x-2}}$ maintaining the multiplication of that for all childrens, and dividing by the current one.
 » There are several cases where the logic provided for problem C fails. Like how can someone be so sure that choosing the minimum cost will give the right answer? It might happen that in order to reach the min cost, we might end up adding a lot of highly expensive cost when we could have just used a 2nd lowest or 3rd lowest cost to cover the entire up/right distance.I really thought I needed to use dynamic programming here.
•  » » Trick is you iterate over number of turns you make, and when you fix number of turns , it is always optimal to use the minimum cost in given prefix.
 » please any one clarify Problem — B edutorial (method-1)notice that, in the sorted string, there is a prefix of zeroes and a suffix of ones. It means that we can iterate on the prefix (from which we remove all ones), and remove all zeroes from the suffix we obtain. If we try to remove two adjacent characters, then we cannot use this prefix;
•  » » If I'm not mistaken, method 1 is $O(n^2)$ where n is the lenght of s.If you iterate $i$ from $0$ to $n$, at iteration $i$ you consider first $i$ characters to be part of "the prefix" of the solution(where you can only have $0$'s or nothing) and all next characters to be part of "the suffix" of the solution(where you can only have $1$'s or nothing).Now, you can remove the $1$'s from the prefix if and only if it doesn't contain the sequence $11$ and you can remove the $0$'s from the suffix if and only if it doesn't contain the sequence $00$. You just traverse them linearly to check this. If for some $i$ you meet both conditions, the answer is YES.The optimized method comes from realising that if you have a $00$ sequence at most you can remove one of the zeroes. Therefore, you can't leave any $1$ before the last occurrence of $00$, and you can only remove all $1$'s that appear before if there isn't a $11$ sequence.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   I interpreted it exactly as you just did here. Maybe I misunderstood the editorial, but it seems to be missing some additional conditions. Take "10100" with "00011" as sorted, for example, it has "00" in the suffix part which does not satisfy the condition mentioned and will therefore return a NO. Even though it is perfectly fine to only remove ones in the prefix.Anybody could help?
 » Can someone please tell the 56th query of 2nd test case in Problem C
•  » » ++
•  » » paste it here
•  » » it's n=4;c[] is [1,2,2,1] you can get it by letting your program simply output it i failed it here too
 » 5 weeks ago, # | ← Rev. 2 →   I guess in problem C the formula should have been sumOdd+minOdd⋅(n−cntOdd+1)+ sumEven+minEven⋅(n−cntEven+1) instead of sumOdd+minOdd⋅(n−cntOdd) + sumEven+minEven⋅(n−cntEven). Isn't it?
•  » » yeah, My formula comes similar to this. current_ans = odd_sum + odd_min*(n-odd_cnt) + even_sum + even_min*(n-even_cnt).You can refer to this video for detailed explanation:- Link to Explanation
•  » » » ok thanx!!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   if you do it using your formula, minOdd and minEven would be counted twice since they are already being considered once in sumOdd and sumEven
 » Why is maximum of value of k=(x/g+d)/c = 2*10^7 in Problem C?
•  » » Let $x = 10^7$, $g = 1$, $d = 10^7$, $c = 1$. It is the bounding values for this task.
 » In F's solution code, d is not even calculated?
•  » » Whoops, turns out it works as is. Removed it, thanks.
 » why in problem D the numbers A and B must be mutually simple?
•  » » After you divide two numbers by their GCD, the resulting numbers are coprime. They don't share any common factor greater than 1.
•  » » » I still do not understand, please explain in more detail, thanks)
•  » » » » If you could be more precise about it maybe we can be more helpful, but right now I can only rephrase the editorial. We are considering two numbers $a$ and $b$ and their $GCD$. If $gcd(a,b) = g$ by definition $g$ is the GREATEST number that divides $a$ and $b$.So if we look at $A = \frac{a}{g}$ and $B = \frac{b}{g}$, there can't be any number $n > 1$ that divides both $A$ and $B$ because then $g*n$ would divide $a$ and $b$. Since $g*n > g$ it would have been false that $g$ is the $GCD$ of $a$ and $b$. This is the same as saying $gcd(A, B) = 1$, which also means they are coprime.
•  » » » » » Thank you, now I understand everything
 » 4 weeks ago, # | ← Rev. 3 →   Why in problem C, we can suppose to make exactly k−1 turns?
•  » » Finally, we should iterate over all k from 2 to n and find the minimum answer among all variants. It's easy to recalculate sums and minimums when we make transition form k to k+1.
 » In the tutorial for problem C, what does cntOdds mean?
•  » » you will be going right and up alternatively. Let's say you decide to go right first, so you will be going right on 1st move, 3rd move, 5th move and so on. so in this case cntOdds becomes the numbers of times you went right and cntEven will be number of time you went up.
•  » » » cool!
 » Any explanation/solution for D(div 2) other than editorial?
•  » »
 » Please invest some time to make editorial good for everyone. Many newbies and pupils are not able to understand C.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   Take a look at this explanation.Let's try solving this problem: Given $c_1, c_2, c_3 \dots, c_k$, find $a_1, a_2, a_3, \dots, a_k \ \ (a_i > 0)$ such that $a_1 + a_2 + a_3 +\dots + a_k = n$ and the sum $c_1 \cdot a_1 + c_2\cdot a_2 + c_3\cdot a_3 + \dots + c_k\cdot a_k$ is minimum.Let's analyze the case when $k = 2$; we have $c_1, c_2$. Obviously $a_2 = n - a_1$, and the cost would be $c_1\cdot a_1 + c_2 \cdot (n - a_1) = c_2\cdot n + a_1\cdot (c_1 - c_2)$. If we consider $c_1 \ge c_2$, then in order to minimize $c_2\cdot n + a_1\cdot (c_1 - c_2)$, $a_1$ has to minimum. Also, since $a_i > 0$, $a_1 = 1$.Now, let's generalize that for arbirtrary $k \ge 2$. Let's build any assignment. Now, suppose there's a pair $a_i, a_j$ with $a_i + a_j = m$ ($m$ is just a constant), and without lossing generality, $c_i \ge c_j$; then from what we did above, it's optimal to choose $a_i = 1, a_j = m - 1$, this preserves $a_i + a_j = m$. We can do that as long as there're still two or more $a_i > 1$. This proves that for any $k \ge 2$, it's optimal to match the minimum $c_i$ with $a_i = n - k + 1$, and all the others with $a_i = 1$. Thus, summarizing, the cost would be $\left(\sum_{i = 1}^k c_i\right) + (n-k)\cdot \min{c_i, \ \forall i \in[1, k]}$Now, how to solve the real problem? Consider every prefix $k\ (k > 1)$ of the sequence $c_1, c_2, \dots, c_n$, and let's get the optimal solution with that prefix; we stay with minium solution among all prefixes. For a fixed $k$, the odd indexes are independent of the even indexes (we can consider odd indexes for UP movements, and even indexes for RIGHT movements), so for a fixed $k$, we have the subsequence of even indexes until k: $e_1, e_2, e_3, \dots, e_r$ and the subsequence of odd indexes $o_1, o_2, o_3, \dots, o_s$, and basically we want to solve the above problem for each of these two sequences.Now, since we go moving $k$ to the right, we need to keep track the sum of all $c_{2i}$ and the sum of all $c_{2i + 1}$, and also the minimum all $c_{2i}$ and the minimum of all $c_{2i + 1}$.These things can be updated easily when we go increasing $k$.
•  » » » Oh thanks for the effort! but I got it already
 » The editorial states that storing the min prime factor using sieve and calculating the ans in $\mathcal{O}\left(\sqrt{x} log x \right)$ is not fast enough , I did precisely that and it passed the test cases . $\newline$ Solution Link : https://codeforces.com/contest/1499/submission/110701050
•  » » I have a similar situation
 » Thanks for the editorial.. was waiting for it. I was asking for help for problem D from my friends, but no one was responding correctly , and that made me feel down... life is hard, when you are fart :(
 » » Why are we adding +13 to const int N in problem d?1499D - The Number of Pairs
»

can someone please tell whats wrong in this for problem b

# define testcase() int t; cin>>t; while(t--)

using namespace std; int main() { fio() testcase(){ int i,t1=1,t0=1,pos=0; string s; cin>>s; if(is_sorted(s.begin(),s.end())) { cout<<"YES\n"; continue;} rep(pos,0,s.size()){ if(s[pos]=='1') break;} rep(i,pos+1,s.size()){ if(s[i]=='1'&&s[i-1]=='1') t1=0; if(s[i]=='0'&&s[i-1]=='0') t0=0; }if(t1==1||t0==1) cout<<"YES\n"; else cout<<"NO\n"; } return 0; }

»

why does my DP solution not show right answer of all cases, can someone explain it to me? This is my first attempt for a DP problem

# include <bits/stdc++.h>

using namespace std;

minimumgridpath() { int n; cin>>n; int a[n],b[n]; for(int i=0;i<n;i++) cin>>a[i];

for(int i=0;i<n;i++)
b[i]=1;

if(n%2==0){
b[n-1]+=n/2;
b[n-2]+=n/2;
}
else
{
b[n-1]+=n/2;
b[n-2]+=n/2+1;
}
int mcost=0;

for(int i=0;i<n;i++)
mcost+=a[i]*b[i];
int cost=mcost;
cout<<cost<<" ";
for(int i=n-2;i>=1;i--)
{
cost=cost-(a[i+1]*b[i+1]);
b[i-1]=b[i-1]+b[i+1];
cost=cost+(a[i-1]*b[i+1]);
if(cost<mcost)
mcost=cost;
cout<<cost<<" ";
}
cout<<"\n";
cout<<mcost<<"\n";


} int main() { int n; cin>>n; while(n--) minimumgridpath(); }