### Fefer_Ivan's blog

By Fefer_Ivan, 7 years ago, translation,

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.

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.

• +46

 » 7 years ago, # |   +2 That was quick!!! One of the things I like about codeforces contest setters are quick tutorials!!! Thank you and keep it up!!!
 » 7 years ago, # |   +13 My solution to E: http://codeforces.com/blog/entry/8721#comment-144522
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   0 I can see your code?
•  » » » 7 years ago, # ^ | ← Rev. 5 →   -11 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 0 2 2 3 1 2 1 3 2 4 2 3 1 (Now you have reached step 2, so you can continue infinitely) Tried with different weights. Solution looks correct
•  » » » » 7 years ago, # ^ |   +2 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 :)
•  » » » 7 years ago, # ^ |   0 Well, see it in my submission.
•  » » » » 7 years ago, # ^ |   0 I see, I forgot trying all viable cases from 1 to 10, instead I took the smallest cases >.<
•  » » » » 7 years ago, # ^ |   0 I see, I forgot trying all viable cases from 1 to 10, instead I took the smallest case >.<
•  » » » » » 7 years ago, # ^ |   0 ...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!
•  » » 7 years ago, # ^ |   +4 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
•  » » » 7 years ago, # ^ |   0 Well.. i see. this greedy algorithm is completey wrong...Oh~. nice test case! thx!
•  » » » » 7 years ago, # ^ |   0 I don't like the way to solve this problem.
•  » » » 7 years ago, # ^ |   0 tks so much, nice test!
 » 7 years ago, # |   +13 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.
•  » » 7 years ago, # ^ |   0 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.
•  » » » 7 years ago, # ^ |   +1 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.
•  » » » » 7 years ago, # ^ |   0 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.
•  » » » » » 7 years ago, # ^ |   0 How is this solution O(n^2). Can you explain ?
•  » » » » » 7 years ago, # ^ |   0 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
•  » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 I think we're wrong, we should output our operations in the reverse order.
•  » » » » » » » 7 years ago, # ^ |   0 thnx for the answer.
•  » » 7 years ago, # ^ |   0 if we only use the first place where a[i] != i (from left side) to generate (don't use the right side), won't it be wrong?
 » 7 years ago, # |   0 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/
•  » » 7 years ago, # ^ |   0 you start from position 1. your code sets your starting position where the first mission is.
•  » » » 7 years ago, # ^ |   0 No. I think in both I start from first home. I got wrong answer on test 7 and it passed 6 test cases
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 http://paste.ubuntu.com/6031871/ here's my AC code~i don't see differnce between them @A@ apology for being stupid :P
•  » » 7 years ago, # ^ |   0 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)
•  » » » 7 years ago, # ^ |   0 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?
•  » » » » 7 years ago, # ^ |   0 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.
•  » » 7 years ago, # ^ |   0 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]
•  » » 2 years ago, # ^ |   0 use unsigned long long int t = 0;
 » 7 years ago, # |   +3 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 :)
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 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 4the left player will initially choose weight 1. Then the right will choose weight 2. SototalLeftWeight = 1totalRightWeight = 2then the left player will choose weight 3 sototalLeftWeight = 4totalRightWeight = 2then 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 4 years ago, # ^ |   0 How do you know that the same state wont be visited again?
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 Can you please explain your code/logic.TOMLAU
 » 7 years ago, # |   0 wow, i didnt know that the tutorial is already been posted,i think you should put this blog link in http://codeforces.com/blog/entry/8721
 » 7 years ago, # |   -6 problem A can easily solved by sorting.No need to take the '+'.Just only take the number and sort them.Then print them including a condition like this if(i!=n-1)printf("+"); code will be AC :)
 » 7 years ago, # |   0 Hi everyone, can you help me with problem E ? I'm getting WA at test case 7 and I don't understand why ... here's my submission link
 » 5 years ago, # |   0 Is there any proved greedy solution for C?
 » 4 years ago, # |   0 339D — Xenia and Bit Operations Why my solution using segment tree has the running time as long as naive implementation. Could anybody help clarify?
•  » » 4 years ago, # ^ |   0 Use scanf,printf instead of cin,cout.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 getting the same problem with my python 48857376
•  » » » 5 months ago, # ^ |   0 Yes for me also getting timeLimit on test case 7. How did u overcome that??
 » 4 years ago, # |   0 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 
 » 4 years ago, # |   0 Can anyone explain how to generate (or create) graph (i.e. which nodes gets connected to which nodes) for problem C???
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 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; } 
•  » » » 4 years ago, # ^ |   0 Wow..!!! Thanks.
•  » » » 4 years ago, # ^ |   0 Can you explain the complexity of this solution and prove the same? Since in the worst case it looks to give a complexity of 10^m but intuitively it seems that it will not reach the worst case. But still not convinced by my intuition.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I have written a blog about it . the complexity seems 9^m.
•  » » » 4 years ago, # ^ |   0 Can you explain the complexity please .
•  » » » 3 years ago, # ^ |   0 The complexity is O(9^1000) right then how is it not getting a TLE? Seniors/experienced people please clear this doubt.
•  » » » » 2 months ago, # ^ |   0 Did you find out the reason ? My dp approach also have 9^m compexity.I don't know how it is accepted.My submission
 » 4 years ago, # |   0 My solution for 339D - Xenia and Bit Operations using segment tree is still getting TLE. Any help!!
•  » » 4 years ago, # ^ |   0 Use int instead of long long int .
 » 3 years ago, # |   0 what is wrong with my code , Im getting WA at 7th test caseimport java.util.*; import java.io.*;public class XeniaAndBit { static void construct(int[] arr, int[] seg, int lo, int hi, int pos, int level) { if (lo == hi) { seg[pos] = arr[lo]; return; } int mid = (lo + hi) / 2; construct(arr, seg, lo, mid, 2 * pos + 1, level + 1); construct(arr, seg, mid + 1, hi, 2 * pos + 2, level + 1); if (level % 2 != 0) { seg[pos] = seg[2 * pos + 1] | seg[2 * pos + 2]; } else { seg[pos] = seg[2 * pos + 1] ^ seg[2 * pos + 2]; } } static void update(int[] segTree, int lo, int hi, int ind, int pos, int val, int level) { if(lo>hi) { return; } if (lo == hi) { segTree[pos] = val; } else { int mid = (lo + hi) / 2; if(lo<=ind && ind <=mid) update(segTree, lo, mid,ind , 2 * pos + 1, val, level + 1); else update(segTree, mid + 1, hi, ind, 2 * pos + 2, val, level + 1); if (level % 2 != 0) { segTree[pos] = segTree[2 * pos + 1] | segTree[2 * pos + 2]; } else { segTree[pos] = segTree[2 * pos + 1] ^ segTree[2 * pos + 2]; } } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[] arr = new int[(int) Math.pow(2, n)]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < Math.pow(2, n); i++) { arr[i] = Integer.parseInt(st.nextToken()); } if(n==1) { int x = arr[0]; int y = arr[1]; for(int i=0;i
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 if (lvl % 2 == n % 2) seg[x] = seg[2 * x] | seg[2 * x + 1]; else seg[x] = seg[2 * x] ^ seg[2 * x + 1]; 
 » 3 years ago, # |   0 I was solving problem C . But i am confused with the complexity. I think the complexity will be O(a^m) where max(a)=10 and max(m)=1000. So wouldnot it time out??someone please explain it to me.
 » 3 years ago, # |   0 please help me with my code....i got wrong answer on 339B test case 7....i tried solving for 2 hour but still was not able to find mistake in it.....please help me...below is url to my code in C++...
 » 3 years ago, # |   0 plzz help me in D problem!!I m getting runtime error in test case 14here is my submission :--36719388
»
3 years ago, # |
0

# include

int main() { int a[101],n,i; while(cin>>a[n++]);

sort(a,a+n);

std::cout<<a[1];

for(i=2;i<n;i++)
{
std::cout<<'+'<<a[i]"\n";
}
return 0;

}

 » 3 years ago, # |   -8 //Wrong answer on test case 7. Please check my code. https://codeforces.com/contest/339/submission/39847306
 » 2 years ago, # |   0 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?
 » 2 years ago, # |   0 Hi guys, Can you help me with my solution to Problem D : https://codeforces.com/contest/339/submission/43628907 ?Thanks
 » 2 years ago, # |   0 can anybody will provide any help for problem d..i solved it using segment tree ..here is my code http://codeforces.com/contest/339/my ..thanks in advance .. i tried it for more than 3 hour but always get wa..so please help
 » 22 months ago, # |   0 ******** I solved Problem D without using typical data structure segment Tree..
•  » » 18 months ago, # ^ |   0 how?
 » 16 months ago, # | ← Rev. 2 →   0 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.com/contest/339/submission/62312472 Correct me if i am wrong. thanks
 » 15 months ago, # |   0
 » 9 months ago, # |   0 Please help getting WA in test case 7 of problem D. here is my solution: https://codeforces.com/contest/339/submission/76421347
•  » » 7 months ago, # ^ |   0 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.
 » 9 months ago, # |   0 What is "Signed integer overflow"?
•  » » 9 months ago, # ^ |   0 In c++, signed integers can store value from [-2^31, 2^31 -1], so if your value is out of this range, the exceptions generated is "signed integer overflow". You can solve this problem by using "long long int" [-2^63, 2^63 -1] which has greater range than signed integer. https://www.geeksforgeeks.org/c-data-types/ refer this link for range of various data types.
 » 8 months ago, # |   0 339B — Xenia and RingroadTo 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.may one explain me a and b here means house or seconds if secondsthen i am ok with case if(a
 » 8 months ago, # |   +3 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).
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 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: cur is available cur > d cur != p for some 1 <= nextval <= 10, dp[l-1][cur-d][cur][nextval] is true. My submission.
 » 7 months ago, # |   0 i am solving d using segment tree but, i am unable to understand how i build a tree can anyone help me plz.
 » 6 months ago, # |   0 what will be time complexity in problem c, nothing mentioned in editorial!!
 » 4 months ago, # |   0 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.com/contest/339/submission/92976386