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 *c*_{1} digits 1, *c*_{2} digits 2 and *c*_{3} digits 3. Then we must print the sequence of *c*_{1} digits 1, *c*_{2} digits 2 and *c*_{3} digits 3. Digits must be separated by + sign.

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.

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 *a*_{i}. 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*(2^{n}) memory.

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.

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

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

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.

I can see your code?

That's a correct solution.

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

Tried with different weights. Solution looks correct

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

Well, see it in my submission.

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

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

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

Consider the following input:

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

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

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

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.

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.

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.

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.

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

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

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

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/

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

No. I think in both I start from first home. I got wrong answer on test 7 and it passed 6 test cases

http://paste.ubuntu.com/6031871/ here's my AC code~i don't see differnce between them @A@ apology for being stupid :P

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)

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?

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.

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;

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

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

finalresult, 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.

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.

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

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

Is there any proved greedy solution for C?

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

getting the same problem with my python 48857376

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

The answer to this example is

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

There is no need to generate the graph.

Wow..!!! Thanks.

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

Did you find out the reason ? My dp approach also have 9^m compexity.I don't know how it is accepted.

My submission

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

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?

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

Thanks

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

how?

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://mirror.codeforces.com/contest/339/submission/62312472 Correct me if i am wrong. thanks

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

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.

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

Suppose we're trying to create a sequence of weights of length

l, with current difference of pans beingd, previously selected weight beingpand the weight we choose now beingcur.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:curis availablecur>dcur!=pnextval<= 10,dp[l-1][cur-d][cur][nextval] is true.My submission.

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

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

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://mirror.codeforces.com/contest/339/submission/209584469 please help !!! stuckkkk

import java.util.Scanner;

public class XeniaAndBitOperation {

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

// 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.println(or+"index : "+ index +" "+ tree[index]); } }

}

Very helpful hints.