vovuh's blog

By vovuh, history, 7 years ago, In English

1095A - Repeating Cipher

Tutorial
Solution

1095B - Array Stabilization

Tutorial
Solution

1095C - Powers Of Two

Tutorial
Solution

1095D - Circular Dance

Tutorial
Solution

1095E - Almost Regular Bracket Sequence

Tutorial
Solution

1095F - Make It Connected

Tutorial
Solution
  • Vote: I like it
  • +31
  • Vote: I do not like it

| Write comment?
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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 !

  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    since in worstcase you need to print k numbers... there is no way... if we change the output format to print tuples (2^x, count) it is possible

»
7 years ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

I would like to know if my AC algorithm for problem D could actually be hacked somehow

https://mirror.codeforces.com/contest/1095/submission/47607217

What the program does is:

  1. If the I kid remembers kids A and B in front of him, that means I is before A and B, so we draw two directed edges I->A, I->B.

  2. There is an order to be decided between A and B that we don't know of yet, so we also draw a pointed line A---B between them.

  3. When all the lines have been drawn, we iterate over each directed edge U->V, and if there was a pointed line U---V, then i assume the order U->V is indeed correct, so we add this directed edge U->V to an answer graph G. Note that there might be multiple solutions, so U->V and V->U might end up existing at the same time.

  4. When we finished generating this answer graph G, visit all the nodes, starting from 0 and going to a any non-visited neighbor that we can go to through an edge

I think the go to any part might actually be hackable

»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    230 = 1073741824. You don't even need 30 in this cycle, 29 is pretty enough, because for numbers up to 109 the maximum power of two in their representation is 229 = 536870912.

»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Where is editorial for problem 1095C - Powers Of Two?

P.S: "Unable to parse markup [type=CF_MATHJAX]" in spoiler.

»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

anyone please explain Problem E..I am unable to understand "if conditions in loop" especially.

»
7 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Problem E can also be solved easily using a segment tree+lazy updates

»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is there any easy explanation of problem E.

»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In E, can you explain your choice of indices for this part:

for (int i = 0; i < n; ++i) {
    pref[i + 1] = pref[i] + (s[i] == '(' ? +1 : -1);
    okp[i + 1] = okp[i] & (pref[i + 1] >= 0);
    suf[n - i - 1] = suf[n - i] + (rs[i] == '(' ? +1 : -1);
    oks[n - i - 1] = oks[n - i] & (suf[n - i - 1] >= 0);
}

It seems arbitrary to me whether you'd do that or do something like pref[i] = pref[i-1] + (s[i] == '(') : 1 : -1). The code is actually different, but I don't understand the difference.

»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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?

»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In problem C what is the function of map<int,int> ? and what it is doing in program i don't understand

»
7 years ago, hide # |
Rev. 3  
Vote: I like it 0 Vote: I do not like it

In problem E, in the first example, why the answer can't be ()(())? this is a regular bracket sequence

  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    It can. You can flip positions $$$2$$$, $$$3$$$, and $$$4$$$ (1-indexed) while being valid in that test case, and your answer is a result of flipping the position $$$2$$$.

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

In Problem D, why is the counter clockwise not acceptable?

»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Question F , came directly in the online assessment of BNY Mellon on my campus