### vovuh's blog

By vovuh, history, 3 years 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)

• +59

 » 3 years ago, # |   0 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
 » 3 years ago, # |   0 I'm not sure why this hacking attempt was successful: http://codeforces.com/contest/1006/submission/40420960Can someone please tell me what went wrong?
•  » » 3 years ago, # ^ |   0 May the hacker explains jhonber
•  » » 3 years ago, # ^ |   +4 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
 » 3 years ago, # |   0 Please anyone explain the problem F. Thanks!!!
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 Thanks, after viewing the code it becomes easier.
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   0 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) ).
•  » » » 3 years ago, # ^ |   +3 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 .
•  » » 3 years ago, # ^ |   0 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
•  » » » 3 years ago, # ^ |   0 I ask a question about the complexity. I don't think you answer right question. :)
 » 3 years ago, # |   0 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";
 » 3 years ago, # |   0 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!
•  » » 3 years ago, # ^ |   +1 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +1 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?
•  » » » » 3 years ago, # ^ |   0 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
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +27 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.
•  » » » » » 3 years ago, # ^ |   +9 Thanks for the explanation with examples neko_nyaaaaaaaaaaaaaaaaa. It makes sense now :D
»
3 years ago, # |
-25

# ?detaR tI sI

 » 3 years ago, # | ← Rev. 2 →   0 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[3],b[3]) and then swap(a[3],a[5])?
•  » » 3 years ago, # ^ |   0 You can only preprocess in the first string (in this case, abacaba).
•  » » 3 years ago, # ^ |   0 It's because we cannot preprocess moves after the first change is made.
 » 3 years ago, # |   0 #include #define ll long long #define INF 20000000000 #define EPS 0.000001 #define f first #define s second using namespace std; ll arr[20][20]; 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<
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 3 years ago, # ^ |   0 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.
•  » » 3 years ago, # ^ |   +1 You need meet in the middle to solve this problem, because your algorithm will cost too much time.
 » 3 years ago, # |   0 My submission for D: http://codeforces.com/contest/1006/submission/40508497 Can someone give me a small test case where this fails?
•  » » 3 years ago, # ^ |   0 2 bc aa
 » 3 years ago, # | ← Rev. 2 →   0 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))
•  » » 3 years ago, # ^ |   0 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
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » 3 years ago, # ^ |   0 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)
•  » » » » 3 years ago, # ^ |   0 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)).
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 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
 » 3 years ago, # |   0 Polycarp sounds like poly-crap. I don't like these puns in problem statement.
 » 3 years ago, # |   0 why do you always give solutions in cpp . please try python for once .
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 oh then I should slowly turn to cpp for good
 » 3 years ago, # |   0 Can I solve problem F using BFS ?
 » 3 years ago, # |   0 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.
 » 3 years ago, # |   0 Can anyone explain problem B. The code in the editorial is confusing
•  » » 3 years ago, # ^ |   0 Did you read explanation? What part in it you don't understand?
•  » » » 3 years ago, # ^ |   0 The whole implementation part means how it is implemented.
 » 3 years ago, # |   0 I cant understand solution of F, please explain me if n = 10 and m = 10? with O (2 ^ (n + m — 2))
•  » » 3 years ago, # ^ |   0 understood...
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   +1 Test case on which your code is wrong:32 1 3
•  » » » 3 years ago, # ^ |   0 Thanks mate.
 » 3 years ago, # |   0 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.
 » 3 years ago, # | ← Rev. 2 →   0 Can anyone explain to me why my solution for problem C get's WA In testcase 13 ? 42740594
 » 2 years ago, # |   0 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
 » 23 months ago, # |   0 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. :)
•  » » 10 months ago, # ^ |   0 well.. yr wish has come true...there is officially a DIV-4 now
 » 23 months ago, # |   0 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
 » 22 months ago, # |   0 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.
•  » » 22 months ago, # ^ | ← Rev. 2 →   +1 Your code has a wrong answer in this test case: 4 4 5 10 4 Your output: 0 Answer : 4 Good luck!
•  » » » 22 months ago, # ^ |   0 Still getting WA on test 6 :( https://codeforces.com/contest/1006/submission/56071670
 » 18 months ago, # |   0 could anyone please explain the editorial in more simpler way , I am not able to understand the problem.please help.
 » 18 months ago, # |   0 tutorial for problem E, I forgot to mention the question.
•  » » 12 months ago, # ^ |   0 The solution in the tutorial is based on dividing them into sub trees.For the given sample,from normal dfs traverse starting from source 1, we get, 1,2,3,5,6,8,7,9,4. We just need to divide this array into continuous sub arrays like [3,5,6,8,7,9] or [7,9] .To make this happen,we just need to find, "after how many vertexes popped, the vertex pushed first was popped." Like, when '3' was pushed,then after pushing 5 vertex, '3' was popped. So this gives us the subarray from array1 which is from (index of 3) to ((index of 3)+5 which is the subarray [3,5,6,8,7,9].So in the dfs code,we'll compute the array1 along with the index of the vertexes in array one and also the "after how many vertexes popped, the vertex pushed first was popped." Then we'll just simply calculate if the given K in query is smaller than that number or not and if smaller, we'll print array1[index+k-1] otherwise -1 .
 » 13 months ago, # |   0 I don't understand this line"Since the given array consists of positive integers, for each value of a, there can be at most one value of c such that sum1=sum3. "in problem C
 » 4 months ago, # |   0 Can someone explain me why this solution fail? Solution
•  » » 6 weeks ago, # ^ |   0 Case 2 ab cc requires 1 preprocessing.