Codeforces Round #529 (Div. 3) Editorial
source link: https://codeforces.com/blog/entry/64130
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
5 years ago, # | In problem C, what if the constraints for n and k are 1018 ? Is there any other better solution possible since the given one will run out of space and time ! |
I would like to know if my AC algorithm for problem D could actually be hacked somehow https://codeforces.com/contest/1095/submission/47607217 What the program does is:
I think the go to any part might actually be hackable |
5 years ago, # | In problem C, the for loop is from i=0 to i=30. As we know that 'int' is of 32 bytes,so I am unable to understand as to why the loop is not from i=0 to 31. Also I saw the codes of many programmers for the problem C and nearly everybody has done it from 0 to 30. So please explain the reason for this. |
5 years ago, # | Where is editorial for problem 1095C - Powers Of Two? P.S: "Unable to parse markup [type=CF_MATHJAX]" in spoiler. |
5 years ago, # | So my solution for D was completely different... I created a matrix in which placed the 2 neighbors for each kid. But how? Well, for example, if the next 2 kids after the first one are 3 and 5, 3 will be a neighbor for 5 and vice versa. Now i could just pick a number, go through this matrix and find the next one. But one more problem.. Sometimes the result was counter-clockwise, so i just added an extra condition : so for the first kid, i would go through that matrix and see which one of those is a 3 or a 5 (one of them), then pick it and do the same thing for it and so on. It was such a rushed solution, yet it worked and i am really please with it ;) |
5 years ago, # | anyone please explain Problem E..I am unable to understand "if conditions in loop" especially. |
5 years ago, # | Problem E can also be solved easily using a segment tree+lazy updates |
-
Then i wonder how it is implemented
-
we convert the string to +1 and -1 (+1 when opening parens, -1 when closing parens) then we compute the cumulative sum array, and then we put the cumulative sum array in a segment tree.
To check if changing the i-th parens "fixes" the sequence we do the following: if the i-th element in the string is opening parens we subtract 2 from me segment [i,n] and if its a closing parens we add 2. (this simbolizes changing the parens to the oposite one) then we do rmq(0,n) and rmq(n,n) if rmq(0,n)<0 or rmq(n,n)!=0 then its an invalid sequence
-
the way i did it was in each node of the segment tree, I stored
- i>The number of valid pairs in the range
- ii>The number of unpaired opening brackets
- iii>The number of unpaired closing brackets
While merging the nodes, observe that the unpaired opening brackets in the left can be paired with unpaired closing brackets in the right child.
In the end, just check whether the root has any unpaired opening or closing brackets.
The problem is similar to https://www.spoj.com/problems/BRCKTS/
-
-
5 years ago, # | Is there any easy explanation of problem E. |
-
The problem is similar to this one SPOJ/BRACKETS
5 years ago, # | In E, can you explain your choice of indices for this part:
It seems arbitrary to me whether you'd do that or do something like |
5 years ago, # | For Problem E with test case 8 )))((((( why is the answer 0? Can't I change it to ()()()() with modifications at positions 1, 3, 4, 6 and 8? |
-
Because you can and only can change exactly one bracket according to the problem description
4 years ago, # | In problem C what is the function of map<int,int> ? and what it is doing in program i don't understand |
-
The map stores the number of occurrences of various powers of 2. It comes in handy when we want to split a set-bit ( a power of 2 ) into two lesser powers of 2.
-
jatinmunjal2k, Resonite here, big fan bro....
-
In problem E, in the first example, why the answer can't be |
4 years ago, # | In Problem D, why is the counter clockwise not acceptable? |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK