Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Vovuh's blog

By Vovuh, history, 5 months 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  

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Can someone please tell me what went wrong?

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

    May the hacker explains jhonber

  • »
    »
    5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please anyone explain the problem F. Thanks!!!

  • »
    »
    5 months 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.

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

      Thanks, after viewing the code it becomes easier.

»
5 months 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.

  • »
    »
    5 months 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) ).

    • »
      »
      »
      5 months 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 .

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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. :)

»
5 months 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";

»
5 months 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!

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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?

      • »
        »
        »
        »
        5 months 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

      • »
        »
        »
        »
        5 months 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.

»
5 months ago, # |
  Vote: I like it -25 Vote: I do not like it

?detaR tI sI

»
5 months 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])?

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

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

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

    It's because we cannot preprocess moves after the first change is made.

»
5 months 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.

  • »
    »
    5 months 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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    4 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months 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))

  • »
    »
    5 months 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

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

    • »
      »
      »
      5 months 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)

      • »
        »
        »
        »
        5 months 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)).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my submission for the Problem D : http://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.

»
5 months 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.

»
5 months 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 .

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I solve problem F using BFS ?

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

      The whole implementation part means how it is implemented.

»
5 months 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))

»
5 months 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://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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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