### vovuh's blog

By vovuh, history, 23 months ago, , Tutorial
Solution (Vovuh)

1006B - Polycarp's Practice

Tutorial
Solution (Vovuh)

1006C - Three Parts of the Array

Tutorial
Solution (Vovuh, set)
Solution (ivan100sic, two pointers)

1006D - Two Strings Swaps

Tutorial
Solution (Ne0n25)

1006E - Military Problem

Tutorial
Solution (mareksom)

1006F - Xor-Paths

Tutorial
Solution (Vovuh) 498, Comments (65)
 » Nice problems, btw in C I binary searched each value of the prefix sum on suffix sum where there is no overlap between sum1 & sum3 code#include using namespace std; typedef long long ll; #define rep(i,n) for(int(i)=0;(i)<(int)n;(i)++) #define vi vector #define vll vector int main() { ll n;cin>>n; vll prefix(n),suffix(n); rep(i,n) cin>>prefix[i],suffix[n-i-1]=prefix[i]; rep(i,n-1) prefix[i+1]+=prefix[i], suffix[i+1]+=suffix[i]; ll mx=0,s,e,mid; rep(i,n){ s=0,e=n; while(s<=e){ mid=s+(e-s+1)/2; if(suffix[mid]==prefix[i] && i+mid
 » I'm not sure why this hacking attempt was successful: http://codeforces.com/contest/1006/submission/40420960Can someone please tell me what went wrong?
•  » » May the hacker explains jhonber
•  » » Try with this test case: 5 4 3 1 1 4 5 Your output 13 1 1 1 2 You have a problem with repeated numbers in this part of the code: for(int j = 0; j < n; j++) { if(arr[j] == indexx) { // *** HERE ind.push_back(j); arr[j] = -1; } } Good luck! :P
 » Please anyone explain the problem F. Thanks!!!
•  » » Read code :) that's easier to understand.You use a structure, v[x][y][c] = number of way to go to cell x, y, have c at xor value. This is the key of solution.
•  » » » Thanks, after viewing the code it becomes easier.
 » Complexity of problem F: We run 2 recursive backtracking. So why is not it O( 2^((n+m-2)/2) ) instead of your complexity ?Maybe because I don't understand how to complete path with 2 child-paths.
•  » » For everyone that has same question with me,Because we use a map, complexity is O( n log n ) with n = number of recursion ( 2^((n+m-2)/2) ).
•  » » » The complexity is because each backtracking will made moves and summary size of maps will be so if we take logarithm of this value we will obtain just .
•  » » This is because n,m can take maximum value upto 20. So you have to compute all 2^20 paths. This will exceed the time limit because time limit is generally upto 2^12 . So it is wiser to break problems into two sets of 10, so computations will become 2^10+2^10= 2^11 which fits our time limit.You can try this problem too Codechef Problem
•  » » » I ask a question about the complexity. I don't think you answer right question. :)
 » In the problem F,because we can only move to the bottom or to the right,we don't need "cnt" to record the number of moves.x+y is just the "cnt";
 » Vovuh In problem F: meet in the middlewas used. Can you suggest any tutorials and problems for this technique? I don't really understand it. Thanks!
•  » » In basis, instead of finding the solution to go from the initial state to the final state, you find the solution to go from each of those states to some mid-states (which has half the moves/resources required to be done). The final work will be merging path — one from the initial, one from the final, to get the answer.You can search for problems with tags "meet-in-the-middle" on Codeforces problemsets. There are enough for you to practice, I suppose.
•  » » » 23 months ago, # ^ | ← Rev. 2 →   Thank you Akikaze. I have a small doubt, it may seem silly but anyway I ask, what are the main differences between this and divide and conquer technique? I went through this geeksforgeeks article, which says Meet in the middle is a search technique which is used when the input is small but not as small that brute force can be used. Like divide and conquer it splits the problem into two, solves them individually and then merge them. But we can’t apply meet in the middle like divide and conquer because we don’t have the same structure as the original problem. What does it mean by — having the same structure as the original problem? And how to decide which one to use?
•  » » » » Well think of native algorithm for this task.You would call (i+1,j) or (i,j+1) until you get to (n,m). But let's see now meet in the middle approach: Go until (i+j)-1==(n+m)/2 (until you reach the middle). Store how many same results for coordinates (i,j) exist (use map because result may be 10^18). And after you went to middle, go backwards from (n,m) to middle and when you reach check if result is k. All I'm saying is just to tell that when you come to middle, you store result count in map, and then you look for results going backwards. Storing result in map and searching answer in map means that don’t have the same structure as the original problem. At least I see it that way, maybe I'm wrong. Hope it helps :D
•  » » » » 23 months ago, # ^ | ← Rev. 3 →   Let's take the classic merge sort algorithm as an example. The problem is to sort the array. If we cut the problem in half, our goal is still to sort the two halves of the array. So we can solve each half by dividing them into two more halves, again.Another example would be the closest pair of points problem. If we divide the set of points in half, we would still need to find closest pair of points in each half. More dividing, yay.Now, let's look at the xor-paths problem. Our original problem is to find a path from one corner to the opposite, with xor exactly k. When we divide the grid in half, our problem for each half is not limited to finding xor exactly k anymore, thus we can't solve each half in the same manner.An easy (but I'm not sure if correct) way to distinguish them is that meet-in-the-middle is typically used to optimize a complete search. When you split the problem, ask yourself: "If the problem is the same for the two halves, and I can solve those halves by brute force, can I use those results to solve the full problem?". If the answer is yes, then it is DnC.
•  » » » » » Thanks for the explanation with examples neko_nyaa. It makes sense now :D
»

# ?detaR tI sI

 » 23 months ago, # | ← Rev. 2 →   I don't quite understand in D why in first exampleabacababacabaaWhen we look at 3-rd line containing characters 'a','c','a','b' result is 2. Why can't we just turn 'c' to 'b', swap (a,b) and then swap(a,a)?
•  » » You can only preprocess in the first string (in this case, abacaba).
•  » » It's because we cannot preprocess moves after the first change is made.
 » #include #define ll long long #define INF 20000000000 #define EPS 0.000001 #define f first #define s second using namespace std; ll arr; ll n,m,k; ll ans; void solve(ll i,ll j,ll cum){ if(i<0||j<0||i>=m||j>=n) return ; // cout<>n>>m>>k; for(ll i=0;i>arr[i][j]; } } solve(0,0,0); cout<
•  » » 23 months ago, # ^ | ← Rev. 2 →   Well,algorithm isn't good. You're going from beginning to end. It will give TLE. Read editorial or try to see how others managed to do meet in the middle.
•  » » » I am using Meet in the Middle technique, can someone please point out why I am getting time out on 6 test case?This is my code.
•  » » You need meet in the middle to solve this problem, because your algorithm will cost too much time.
 » My submission for D: http://codeforces.com/contest/1006/submission/40508497 Can someone give me a small test case where this fails?
•  » » 2 bc aa
 » 23 months ago, # | ← Rev. 2 →   If F problem if n+m is not so small how to find the time complexity of the recursive solution. How it is O((n+m-2Cm-1)*(n+m-2))
•  » » About O( ·(n + m - 2)) — exists the method which allows us to iterate over all binary masks of length n with exactly k ones with the time complexity O( ). And, of course, for each mask we need to iterate over all its bits and spend n + m - 2 operations to do this
•  » » » 22 months ago, # ^ | ← Rev. 2 →   I may be missing something, but let me ask: In a 3x3 grid, for example, won't we have 6 possible moves (m+n) ?EDIT:nevermind, I was confused. Moves != #Paths
•  » » » But how the complexity is O((n+m-2)C(m-1)·(n + m - 2))?? because to iterate all mask of size n+m-2 you need a for loop which complexity is 2^(n+m-2)
•  » » » » Not necessary. In one of the previous comments I noticed that exists a method which allows us to iterate over all binary masks of length n with exactly k ones with the complexity written above. If you are very interested, there is a code on C++. Unfortunately, now I cannot describe how it works. Codefor(int mask = (1 << k) - 1; mask < (1 << n); ) { if (mask == 0) break; int x = mask & -mask, y = mask + x; mask = (( (mask & ~y) / x ) >> 1) | y; } But with such a cycle we need to check where ones are placed in the current mask. So overall complexity is O( ·(n + m - 2)).
 » My submission for E: http://codeforces.com/contest/1006/submission/40523424 Can someone help optimise this code? The logic seems simpler than the one in the editorial.
•  » » Well, for every vertex you are storing whole subtree. Off course it will give memory limit exceeded, because you are using O(n^2) memory. And your logic may be simpler, but that doesn't matter since solution is wrong — program:int main { return 0; }will be simpler than the one in tutorial, even simpler than yours, but it won't give correct answer either :)If you want to get AC you have to understand what's going on in editorial, why it is done like that and then code it in similar way.
 » This is my submission for the Problem D : http://codeforces.com/contest/1006/submission/40525793These are the steps that I followed while writing the solution : 1.segregate all the four characters, whose positions can be changed after the preprocess, I named them a , b (from the first string ) and c,d (from the second string) 2.i created a set to count the number of unique characters in these four elements. 3.If the set size is 4 , which means all the characters are unique , then ans = ans + 2; 4.If the set size is 3 , in this case there are two possible arrangements, either the ans = ans + 1 or ans = ans + 2 , if a==b or c==d ( the pair containing same character is present in the first string or in the second string ) 5.If the set size is 2, then ans = ans + 1 , only if there are three same characters 6.If the string size is odd, check whether the middle element is equal in both the strings. Can you tell me what I am missing from this.
•  » » 23 months ago, # ^ | ← Rev. 3 →   I got where I am mistaken , in the step 4 , if c==d , then ans = ans + 1 , instead of ans = ans + 2.Correct solution : http://codeforces.com/contest/1006/submission/40542519
 » Polycarp sounds like poly-crap. I don't like these puns in problem statement.
 » why do you always give solutions in cpp . please try python for once .
•  » » C++ is more understandable for a lot of participants. My Python solutions are as short as possible and not so clear as C++ solutions. And one more reason is that for the last 2-3 problems we don't guarantee that Python solutions will pass.
•  » » » oh then I should slowly turn to cpp for good
 » Can I solve problem F using BFS ?
 » this was the first editorial till now that i understood completely , i hope tutorials in future will also be so great , then only novice programmers can learn. thanks.
 » Can anyone explain problem B. The code in the editorial is confusing
•  » » Did you read explanation? What part in it you don't understand?
•  » » » The whole implementation part means how it is implemented.
 » I cant understand solution of F, please explain me if n = 10 and m = 10? with O (2 ^ (n + m — 2))
•  » » understood...
 » Problem C — Three Parts of the Array Can someone find the problem here? http://codeforces.com/contest/1006/submission/40760589 I find it exactly the same as tutorial's solution with two pointers, but Test Case #12 fails. Thanks.
•  » » Test case on which your code is wrong:32 1 3
•  » » » Thanks mate.
 » Can someone explain problem D? What is the difference if s[i]= s[n-i+1] and t[i] = t[n-i+1]? It's really confusing to me.
 » 21 month(s) ago, # | ← Rev. 2 →   Can anyone explain to me why my solution for problem C get's WA In testcase 13 ? 42740594
 » If someone want to try a variation of Problem F (n*n matrix rather than n*m matrix) go and solve https://www.codechef.com/problems/XORGRIDMy code for problem F:https://codeforces.com/contest/1006/submission/53013382
 » Could someone explain Problem E a bit more elaborately ? I have been stuck on it for quite a while and can't figure out a way to solve it. :/ I know that the editorial is very well — written, but could someone explain it in a Div — 4 way ? Also, a better written code would be of great help in understanding the solution. :)
•  » » well.. yr wish has come true...there is officially a DIV-4 now
 » https://codeforces.com/contest/1006/submission/54741899 the output of 20th test case is same as my answer yet it shows wrong answer....can someone help please
 » What is wrong in this code? Is this an implementation problem or a logic problem?I binary searched on indices such that we split the first part at mid, and then I ran a loop backwards finding whether a sum3 exists for the corresponding sum1 upto mid.https://codeforces.com/contest/1006/submission/56046778I am getting WA on test 6.
•  » » 11 months ago, # ^ | ← Rev. 2 →   Your code has a wrong answer in this test case: 4 4 5 10 4 Your output: 0 Answer : 4 Good luck!
•  » » » Still getting WA on test 6 :( https://codeforces.com/contest/1006/submission/56071670