Можно вообще не строить никаких графов. Сохраним в массиве f[i][j][k] (i — баланс, j — последняя гирька, k — номер шага) номер гирьки использованной в состоянии, откуда мы пришли(что-то вроде массива предков). Тогда предыдущее состояние есть f[abs(i — j)][f[i][j][k]][k — 1]. То есть, если найдется ненулевое f[i][j][m], то просто пройдем в обратном направлении до m == 0, сохраняя номера гирек в вектор ans. Вот код 4355573

I can see your code?

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

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.

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

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)

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]

use unsigned long long int t = 0;

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.

Если чисел 2^N, то запрос обновления будет выполняться за O(N)

Странно, у меня такое решение завалилось на 34 тесте.

Ваше решение падает на тесте

0100010100
6

Ответ

YES
6 8 6 8 6 8

getting the same problem with my python 48857376

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

how?

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.

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.

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];
    }
}

}