vovuh's blog

Codeforces Round #498 (Div. 3) Editorial
By vovuh, history, 6 years ago, In English

1006A - Adjacent Replacements

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)
  • Vote: I like it
  • +59
  • Vote: I do not like it

Comments Comments (52)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not sure why this hacking attempt was successful: http://mirror.codeforces.com/contest/1006/submission/40420960

Can someone please tell me what went wrong?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please anyone explain the problem F. Thanks!!!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, after viewing the code it becomes easier.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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) ).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 .

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I ask a question about the complexity. I don't think you answer right question. :)

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it +27 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it -25 Vote: I do not like it

?detaR tI sI

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't quite understand in D why in first example

abacaba

bacabaa

When 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])?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can only preprocess in the first string (in this case, abacaba).

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
#include<bits/stdc++.h>
#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<<cum<<" DF "<<endl;
	if(i==m-1&&j==n-1){
		if((cum^arr[i][j])==k){
			cout<<(cum^arr[i][j])<<"GG"<<endl;
			ans++;
		}
	}
//	cout<<"DD"<<endl;
	solve(i+1,j,cum^arr[i][j]);
	solve(i,j+1,cum^arr[i][j]);
	
}

int main(){
	cin>>n>>m>>k;
	for(ll i=0;i<n;i++){
		for(ll j=0;j<m;j++){
			cin>>arr[i][j];
		}
	}
	solve(0,0,0);
	cout<<ans<<endl;
	return 0;
}

Can someone help me debug this code.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You need meet in the middle to solve this problem, because your algorithm will cost too much time.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission for D: http://mirror.codeforces.com/contest/1006/submission/40508497 Can someone give me a small test case where this fails?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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))

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        Code

        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)).

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission for E: http://mirror.codeforces.com/contest/1006/submission/40523424 Can someone help optimise this code? The logic seems simpler than the one in the editorial.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my submission for the Problem D : http://mirror.codeforces.com/contest/1006/submission/40525793

These 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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Polycarp sounds like poly-crap. I don't like these puns in problem statement.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why do you always give solutions in cpp . please try python for once .

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem B. The code in the editorial is confusing

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you read explanation? What part in it you don't understand?

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I cant understand solution of F, please explain me if n = 10 and m = 10? with O (2 ^ (n + m — 2))

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C — Three Parts of the Array Can someone find the problem here? http://mirror.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.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone explain to me why my solution for problem C get's WA In testcase 13 ? 42740594

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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/XORGRID

My code for problem F:https://mirror.codeforces.com/contest/1006/submission/53013382

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/1006/submission/56046778

I am getting WA on test 6.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

tutorial for problem E, I forgot to mention the question.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me why this solution fail? Solution

→ Reply