Fefer_Ivan's blog

Codeforces Round #197 — Tutorial
By Fefer_Ivan, 11 years ago, translation, In English

339A - Helpful Maths

Tutorial by Fefer_Ivan

To solve this problem we can count the number of digits 1, 2 and 3 in the input. If there are c1 digits 1, c2 digits 2 and c3 digits 3. Then we must print the sequence of c1 digits 1, c2 digits 2 and c3 digits 3. Digits must be separated by + sign.

339B - Xenia and Ringroad

Tutorial by Fefer_Ivan

To solve this problem we must learn how to calculate fast enought the time, needed to travel between houses a and b. Let's consider the case when a ≤ b. Than Xenia needs b - a seconds to get from a to b. Otherwise a > b, Xenia will have to go thought house number 1. So she will need n - a + b seconds.

339C - Xenia and Weights

Tutorial by Fefer_Ivan

Let's consider the definition of balance. Balance is the difference between sum of all weights on the left pan and sum of all weights on the right pan. At the beginning balance is equal to 0. Att each step Xenia puts one weight on the pan. It means she adds to or substracts from balance integer from 1 to 10. In each odd step, the integer is added and in each even step the integer is subtracted. From the statement we know, that after each step, balance must change it sign and must not be equal to 0. So if after some step the absolute value of balance is greater than 10, Xenia can not continue. Also, it is said in the statement that we can not use two equal weigths in a row. To solve the problem, let's consider a graph, where vertices are tuples of three numbers (i, j, k), where i is a current balance, j is a weight, used in the previous step, and k is the number of the current step. Arcs of the graph must correspond to Xenias actions, described in the statement. The solution of the problme is a path from vertex (0, 0, 1) to some vertex (x, y, m), where x, y are any numbers, and m is the requared number of steps.

339D - Xenia and Bit Operations

Tutorial by Gerald

The problem could be solved by using a typical data structure (segment tree).

The leafs of the segment tree will store the values of ai. At the vertices, the distance from which to the leafs is 1, we will store OR of the numbers from the leafs, which are the sons of this node in the segment tree. Similarly, vertices, the distance from which to the leafs is 2, we will store Xor of the numbers stored in their immediate sons. And so on. Then, the root of the tree will contain the required value v.

There is no need to rebuild all the tree to perform an update operation. To do update, we should find a path from the root to the corresponding leaf and recalculate the values only at the tree vertices that are lying on that path. If everything is done correctly, then each update query will be executed in O(n) time. Also we need O(2n) memory.

339E - Three Swaps

Tutorial by Gerald

We will call the command l, r a reverse, also we will call the row of horses an array. Suddenly, right?

The problem can be solved with clever bruteforcing all possible ways to reverse an array. To begin with, assume that the reverse with l = r is ok. Our solution can find an answer with such kind of reverses. It is clear that this thing doesn't affect the solution. Because such reverses can simply be erased from the answer.

The key idea: reverses split an array into no more than seven segments of the original array. In other words, imagine that the array elements was originally glued together, and each reverse cuts a segment from the array. Then the array would be cut into not more than 7 pieces.

Now you can come up with the wrong solution to the problem, and then come up with optimization that turns it into right. So, bruteforce all ways to cut array into 7 or less pieces. Then bruteforce reverse operations, but each reverse operation should contain only whole pieces. It is clear that this solution is correct, One thing it does not fit the TL.

How to improve it? Note that the previous solution requires the exact partition of the array only at the very end of the bruteforce. It needed to check whether it is possible to get the given array a. So, let's assume that the array was originally somehow divided into 7 parts (we don't know the exact partition), the parts can be empty. Now try to bruteforce reverses as in naive solution. One thing, in the very end of bruteforce try to find such a partition of the array to get (with fixed reverses) the given array a.

The search for such a partition can be done greedily (the reader has an opportunity to come up with it himself). Author's solution does this in time proportional to the number of parts, that is, 7 operations. However, this can be done for O(n) — this should fit in TL, if you write bruteforce carefully.

  • Vote: I like it
  • +46
  • Vote: I do not like it

Comments Comments (55)
| Write comment?
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

That was quick!!! One of the things I like about codeforces contest setters are quick tutorials!!! Thank you and keep it up!!!

→ Reply
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

My solution to E: http://codeforces.me/blog/entry/8721#comment-144522

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

This Contest's Problem C, i came up with a interesting greedy algorithm. we try the first valiable operation from 1 to 10. then we start greedy algorithm. if (l > r) then we need to get the minimum weigh that is strictly greater l — r. if (r > l) then we need to get the minimum weigh that is strictly greater r — l; if there is one operation we can't find that suitable weigh, then it will be "NO";

My code got AC with this algorithm, but i can't prove its right or wrong. can you prove it ? thx.

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

    I can see your code?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 5   Vote: I like it -11 Vote: I do not like it

      That's a correct solution.

      Suppose you have 3 possible weights 2,3,4. You start using this in suggested greedy way:

      Weight used               Difference in weights
      1. 0
      2. 2 2
      3. 3 1
      4. 2 1
      5. 3 2
      6. 4 2
      7. 3 1 (Now you have reached step 2, so you can continue infinitely)

      Tried with different weights. Solution looks correct

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

        but i can't prove it strictly.. sometimes most of the greedy algorithms seems right, but they are not really right.. ,maybe i can pass the final tests because of the final tests is quite weak to make my program wrong.. but thank you all the same :)

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

      Well, see it in my submission.

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

        I see, I forgot trying all viable cases from 1 to 10, instead I took the smallest case >.<

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

          ...it seems that this greedy algorithms is also wrong... maybe if i used this algorithm during the contest, it would be hack and fail to pass the final tests.. maybe it can pass the final tests because of there is nobody use this test to hack during the contest :) the following reply is give the test case to make my program wrong.. the test case is so great!

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

    This is a nice idea but unfortunately it's not correct.

    Consider the following input:

    0110010001
9

    The output should be "YES" but your solution produces "NO".

    Weights for this input: 2, 3, 2, 6, 10, 6, 2, 3, 6

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

      Well.. i see. this greedy algorithm is completey wrong...Oh~. nice test case! thx!

      → Reply
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

My solution to E is a little different. I find the first place where a[i]!=i,then there must be an operation (i,x),also with the last i that a[i]!=i. Enumerating x,and do the operator,then there is only two operator we can do, as before ,find the first and the last place where a[i]!=i,notice that the second operator must change one of them, and we could find what the second operator is！Then only one step there which is very easy to check, and we can finish the algorithm in O(n^2). sorry for my bad English.

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

    Sorry, I didn't understand. For example, 1 2 3 4 5, 3 operations like this: (1, 5) ---> 5 4 3 2 1 (3, 5) ---> 5 4 1 2 3 (1, 3) ---> 1 4 5 2 3 first i satisfies a[i] != i is 2, but there is no operations like (2, x). However, last i that a[i] != i is 3, there is an operation (3, 5). So, how can I know when should I choose the first, and last. Please, explain more. Thanks.

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

      I think that the reason is that we can only do three operations, the situation wouldn't be complex. Then the shorter sequence, the less operations, this is why I choose the first and the last i!=a[i]. In your example, I can do the operation (2,3)->(4,5)->(1,5),have the same effect. I think once there is a way, there must be a way that include the first or the last i that a[i]!=i. I didn't prove it, but I think it's true. And welcome the counter example.

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

        I think you are right. However, there maybe something wrong with the test. My solution got WA on test 7, but it is easy to check in person that my answer is a valid one. test 7 is 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 70 71 72 73 74 26 25 24 23 22 98 99 100 my answer is 3 22 97 45 92 65 87 T^T....... MY SUBMITION Any one help.

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

          How is this solution O(n^2). Can you explain ?

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

          I got the same problem as you.Output of my code for test 7 is same as yours.I print the array with the each swap.After the 3rd swap array is in correct order.Here is my output. I don't why it says wrong answer. Swap 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 74 73 72 71 70 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 Swap 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 Swap 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 3 22 97 27 74 47 69

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

            I think we're wrong, we should output our operations in the reverse order.

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

Hi guys Can you help me whats wrong with my code for problem B? i used 2 diffrent ways and i dont know whats wrong with them yet http://paste.ubuntu.com/6031387/ http://paste.ubuntu.com/6031388/

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

    you start from position 1. your code sets your starting position where the first mission is.

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

    The second method(http://paste.ubuntu.com/6031388/) is right. The only problem is that you must assign "long long t=0" instead of "unsigned long int t=0"(because there is possibility of integer (long int) overflow)

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

      I used unsigned long long int too! But there still was wrong answer oj pretest 7. But I think the answer for test 7 wasn't as much that cause overflow. Is there anything else or my thinking is wrong?

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

        I've search that on the Internet. "long==int",so the range of "unsigned long int" is 0 ~ 4294967295 (4 Bytes),while in the test 7 the answer is"4996767587" ,which is greater than 4294967295,obviously overflow.(n=100000,m=100000,the total num can be reached to 10^10.) maybe I think "long long int"=="int",because I never see such expression before.

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

    The first method's problem is also "int t=0". this is the two results what i have adapted from your two codes.

    [submission:4359884][submission:4359849]

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

    use unsigned long long int t = 0;

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

C was much easier than that. Simplest backtracking worked fine, even with passing of a vector by value to recursive function — see 4347646 :) But I too tried hard to make it harder :)

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

    I used a brute force kind of approach in order to solve C (unfortunately after the contest).

    My submission during the contest followed the logic that, the left player (where player = scalepan) chooses initially the first smallest weight available. Then the right player chooses the first smallest weight available which satisfies the conditions, then the left player does the same until we have a result.

    This approach is wrong, because it assumes that initially, choosing the first smallest weight available for the left player will always yield to a final result, which is why I failed on test case 34.

    For input

    1110000000 4

    the left player will initially choose weight 1. Then the right will choose weight 2. So

    totalLeftWeight = 1

    totalRightWeight = 2

    then the left player will choose weight 3 so

    totalLeftWeight = 4

    totalRightWeight = 2

    then the right player can't choose weight 3, and he can't choose either of weights 1 or 2 because the conditions won't satisfy.

    However, if the left player initially chooses the weight 2, the right player will choose 3, then the left player 2 and so on.

    Because the whole process depends on which weight the left player initially chooses, I simply added a for loop that searches for potential solutions when the left player chooses initially either of the weights available. If during a loop process we find a result, that is "YES", then we print the output and that's it. Otherwise, if we don't find a result, we restart the process by choosing the next smallest weight available for the left player.

    The logic of this approach is hopefully very easy to follow, however my problem is that I have no idea what's the time complexity of this algorithm.

    Here is my accepted submission.

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

      More tests have been added, this greedy approach doesn't work. Try this case: 0110010001 9 Here's my submission with the same approach failing on test 39.

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

wow, i didnt know that the tutorial is already been posted,

i think you should put this blog link in http://codeforces.me/blog/entry/8721

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

Is there any proved greedy solution for C?

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

339D — Xenia and Bit Operations Why my solution using segment tree has the running time as long as naive implementation. Could anybody help clarify?

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

For problem E, a wrong solution like 4350288 got AC, the key point in this solution is that every step, reverse a section which make the first and the last a[i] != i closer. Which is definitely wrong.

A counter example is

9
5 6 7 8 1 2 3 9 4

The answer to this example is 

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

Can anyone explain how to generate (or create) graph (i.e. which nodes gets connected to which nodes) for problem C???

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

    There is no need to generate the graph.

    bool dfs(int x,int y,int k){
	if(k>m)return 1;
	int f=0;
	FOR(i,1,10){
		if(c[i]&&x>=0&&y!=i&&x-i<0){
			f=dfs(x-i,i,k+1);
		}
		else if(c[i]&&x<0&&y!=i&&x+i>0){
			f=dfs(x+i,i,k+1);
		}
		if(f){
			v.PB(i);
			return 1;
		}
	}
	return 0;
}
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow..!!! Thanks.

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

      The complexity is O(9^1000) right then how is it not getting a TLE? Seniors/experienced people please clear this doubt.

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

//Wrong answer on test case 7. Please check my code. https://codeforces.me/contest/339/submission/39847306

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

Here is my code for Problem C (https://hastebin.com/opudegumer.cpp) I've done pure Brute and it passed... Is it because of weak tests or does the problem solution itself not let it become exponential?

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

Hi guys, Can you help me with my solution to Problem D : https://codeforces.me/contest/339/submission/43628907 ?

Thanks

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

******** I solved Problem D without using typical data structure segment Tree..

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

I did the D solution without using segment tree. The idea is simple, used a 2d array to store states after ith iteration, used an array of a[n][pow(2,n)]. But the judge is showing TLE on 7th test case. I feel my code has just a complexity of O(n*32*pow(2,n)) but still throwing tle on test case 7. here is the link to my code:https://codeforces.me/contest/339/submission/62312472 Correct me if i am wrong. thanks

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

Please help getting WA in test case 7 of problem D. here is my solution: https://codeforces.me/contest/339/submission/76421347

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

    I think your segment tree is incorrect The actual operations that have to be made is -> or operation on pairs of size (2^(n-1)); then xor on 2^(n-2); and loop till the size is one. So you have to create a tree of height n and update the sequence periodically. one level for OR of a range and one level for XOR of the range. Your segment tree is not following the order as described in question. the first 6 test cases might be.

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

Anyone with DP solution for Question C? The tag says that it can be done using DP. (Although they also say it can be done using greedy while is not true).

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

    Suppose we're trying to create a sequence of weights of length l, with current difference of pans being d, previously selected weight being p and the weight we choose now being cur.

    dp[l][d][p][cur] stores whether such a sequence can be completed (true/false).

    dp[l][d][p][cur] is true if all of the following are satisified:

    1. cur is available
    2. cur > d
    3. cur != p
    4. for some 1 <= nextval <= 10, dp[l-1][cur-d][cur][nextval] is true.

    My submission.

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

what will be time complexity in problem c, nothing mentioned in editorial!!

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

Hi — I'm continuing to get TLE on test 7, despite having set the problem up in a segment tree. Is anyone able to help me understand why my solution doesn't run in time?

https://codeforces.me/contest/339/submission/92976386

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to understand the TLE ON TEST CASE 53 in my code for problem e. Here is the link to my solution https://codeforces.me/contest/339/submission/209584469 please help !!! stuckkkk

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

    import java.util.Scanner;

    public class XeniaAndBitOperation {

    public static void main(String[] args) {
    Scanner scan  = new Scanner(System.in);
    int n , m , updateIndex , updateValue ; 
     n = scan.nextInt();
     m = scan.nextInt();

    int elements = 1<<n;
    int[] arr = new int[elements+1];
    for(int i = 1; i<=elements; i++){
        arr[i] = scan.nextInt();
     }

    // System.out.println(Arrays.toString(arr)); int[] tree = new int[ 1<<(n+1) ];

    boolean or = n%2 == 0 ? false : true;
    buildSegmentTree(tree, arr, 1, 1, elements, or);

    // System.out.println(Arrays.toString(tree)); while (m-- != 0){ updateIndex = scan.nextInt(); updateValue = scan.nextInt(); // or = elements%2 == 0 ? false : true; updateQuery(tree, 1, 1, elements, updateIndex, updateValue, or); // System.out.println(Arrays.toString(tree));

    System.out.print(tree[1]+"\n");
    }
}

private static void buildSegmentTree(int[] tree, int[] arr, int index, int left, int right, boolean or ){
    if(left == right){
        tree[index] = arr[left];
    }else{
        int mid = left + (right-left)/2;
        buildSegmentTree(tree, arr, 2*index, left, mid, !or);
        buildSegmentTree(tree, arr, 2*index+1, mid+1, right, !or);

        if(or){
            tree[index] = tree[2*index] | tree[2*index+1];
        }else {
            tree[index] = tree[2*index] ^ tree[2*index+1];
        }

    // System.out.println(or+"index : "+ index +" "+ tree[index]); } }

    private static void updateQuery(int[] tree ,  int currentNode, int left, int right, int updateIndex, int value, boolean or){

    if(left == right ){
        tree[currentNode] =  value;
        return;
    }

    int mid = left + (right-left)/2;

    if(updateIndex>= left && updateIndex<=mid){
        updateQuery(tree,  2*currentNode, left, mid, updateIndex, value, !or);
    }else
    {
        updateQuery(tree, 2*currentNode+1, mid+1, right, updateIndex, value, !or);
    }

    if(or){
        tree[currentNode] = tree[2*currentNode] | tree[2*currentNode+1];
    }else {
        tree[currentNode] = tree[2*currentNode] ^ tree[2*currentNode+1];
    }
}

    }

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very helpful hints.

→ Reply