**Div 2 A**

**Div 2 B**

**Div 2 C = Div 1 A**

**Div 2 D = Div 1 B**

**Div 2 E = Div 1 C**

**Div 1 D**

**Div 1 E**

# | User | Rating |
---|---|---|

1 | Petr | 3325 |

2 | OO0OOO00O0OOO0O0…O | 3289 |

3 | Um_nik | 3278 |

4 | Syloviaely | 3274 |

5 | tourist | 3206 |

6 | Radewoosh | 3197 |

7 | V--o_o--V | 3167 |

8 | mnbvmar | 3096 |

9 | dotorya | 3086 |

10 | FizzyDavid | 3023 |

# | User | Contrib. |
---|---|---|

1 | tourist | 183 |

2 | rng_58 | 168 |

3 | csacademy | 161 |

4 | Petr | 160 |

5 | lewin | 151 |

6 | Swistakk | 150 |

7 | matthew99 | 142 |

8 | BledDest | 141 |

9 | Errichto | 140 |

10 | adamant | 139 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round #443 (Div. 1)

Tutorial of Codeforces Round #443 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/27/2018 01:59:09 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

Auto comment: topic has been translated by khadaev (original revision, translated revision, compare)I have learned SCC(strongly connected components) recently. But I can't figure out the solution of div1 C/ div2 E. After I understand the solution of choice (id: 31775120), I think it is so simple and beautiful!

Then I consider why I can't get the solution? Maybe it requires kind of mathematical intuition.

I think the solution of DIV2 D can be easier when i saw this solution 31763303

Div 2 C / Div 1 A Bonus solution :

Approach 1. Don't use AND operation at all. All four cases can be handled with just OR and XOR operations. For example , if (0,1) and (1,0) are the (input,output) pairs you can do OR 0 , XOR 1.

Approach 2. Say X is the output you get when the input is 0 and Y is the output you get when the input is 1023. We can just do these two operations : AND (X ^ Y) , XOR X.

Can you please explain why the second approach works? Thank you.

1023 = ten1's, 0 = ten0's. so when we apply all operations to these two numbers we can determine what operation(flip, nochange, set0, set1) is happening to a certain bit.

Now we can choose either ^and| as our two operations or ^and&. My solution uses ^and|.

Concretely, let op0 be output of all operations applied on 0, and op1 be the output when applied to 1023.Consider what should the ith bit of number_to_be_xor'red_with and number_to_be_or'ed_with be, for a given ith bit of op0 and op1.

now observe that xornum is 1 when op0 is 0, so xornum=~op0 and ornum is 1 for ~(op0^op1). Now since these are bitwise operators, applying on the bits 1 by 1 is the same as applying on whole number.

Therefore, xornum=~op0, ornum=~(op0^op1)

Implementation Detail: We need to consider first 10 bits only(0<=xornum,,ornum<=1023), so & xornum and ornum with 1023(bits greater than the 10th one will be set to 0).

The solution given here has the simplification with ^and| instead of ^and&, but the concept is same.

Accepted Solution: http://codeforces.com/contest/879/submission/31857500

Thank you original author for the idea!

Can you please explain this for a single bit? I still do not understand how this compacts and, xor, and or.

lets assume we have only 1 bit numbers. so op0 op1 xornum and ornum are all 1 bit. Applying all operations on 1 and 0, we can have 4 possible cases ->

op0 is 0 and op1 is 0, in this case, we have set 1 to a 0, and 0 remains as it is, hence we can say that no matter the value of the bit we have made it 0, to do that, first or with 1(set1) and xor with 1(flip).

op0 is 0 and op1 is 1, hence we have just passed the number as it is (i.e. 1->1 and 0->0). Hence do nothing, i.e. xor with 0 and or with 0.

op0 is 1 and op 1 is 1, this is set 1 operation(like case 1 but now we set it to 1). To do that or with 1 and xor with 0.

op0 is 1 and op1 is 0, clearly we have just flipped the input bit, i.e. or with 0 and xor with 1.

Ultimately you just have to figure what should each bit turn to after the operations and how to achieve that using xor and or (and adjust that bit accordingly)

Maybe the time of Soluton of Div1 C is wrong?I think if we use balance binary search tree(what's "a some search tree",I can't understand),the time will be O(klogn) once?Because once comparing is O(k),not O(1).

You are completely right. Thanks!

I suppose I have an

O(n) ONLINE solution for 878E - Numbers on the blackboard. Please correct me if I have made a mistake. Here it is:We call the action mentioned in the problem statement "

mergex,y".Define

f(i,j) (i< =j) as: Consider subarraya[i...j] and each timemergetwo last elements until one number is left.f(i,j) is that number. LetL[j] be the maximumi(i< =j) thatf(i,j) < = 0. If there is no suchithenL[j] = 1. Now for each indexjdefinepar[j] =L[j] - 1. Build a tree using arraypar[].Now we are going to answer query

l_{i},r_{i}inO(1). First find the lowest ancestor ofr_{i}in the tree which is inside the query and name itg. You can prove:answer=A+ 2 *B.B= 2 * (f(L[r_{i}],r_{i}) +f(L[par[r_{i}]],par[r_{i}]) + ... +f(g+ 1, ...))A=f(l_{i},g)For better understanding take a look at the picture below.

If we can find

gin efficient time, the rest is not very hard: We calculateBusing a partial-sum on tree and calculateAusing another simple partial sum on suffixes of the array.First sort children of each vertex in increasing order of difference between their index and their father index. Let

D=lca(l_{i},r_{i}).gis a direct descendant ofD. Now for calculatinglcainO(1) we use the approach explained in this post (Advanced RMQ). BE CAREFUL to modify RMQ in a way that gives us the rightmost index with minimum value.Let

ind= index of rightmostDobtained by RMQ. You can provegis located atind+ 1.This approach solves the problem using

O(n) preprocess (for building the tree and reduction of LCA to RMQ) andO(1) for each query.Nice implementation for Div1A / Div2C: 31777939.

Edit: I didn't notice an even simpler solution here.

Div 1 D:

Is this solution supposed to get AC?

I don't think so. It's clearly O(q^2).

For Div2 E/ Div1 C, does the statement

`condensation is a path`

mean that it'll be a chain and not a general DAG ? If we have 3 components C1,C2,C3 , why can't we have a DAG like`C1 -> C2`

,`C2->C3`

,`C1->C3`

?Indeed, we can have that situation. The important thing to see, is that the partially ordered set induced by the condensation is in fact a total order. We can call that a chain (or path, as he did).

Yes, i convince myself of that too, but mostly because i couldn't build any counterexample, so can you prove this interesting fact. I think the most important property of the graph is that every game forms a total order.

Well, yes. It is mentioned in the editorial as well. For any two components

AandB, take any vertexes and . Since it is always true thatucan beatv, orvcan beatu, there are no incomparable components.In Div1 D, can anyone explain why there are at most 2

^{k}different characteristics? I can't understand it since there are two kinds of spells......If two characteristics are equal for all initial creatures, they are equal for all creatures. So, the characteristic is completely determined by the sequence of

kzeroes or ones.Sorry, but I still not understand this. Lets say: n = 4, k = 3. The characteristics of these 3 creatures are:

Now we can create the following other mixtures:

This are already more than 2^k = 8.

Do I completely misunderstand the problem?

he means to say that there are at most 2

^{K}distinct columns , any repeated column can be discarded and all instances of it from the queries can be replaced with the first occurrence of that column.As I understood, it makes at most 2

^{k + 1}different sequences. Because same columns can get 0 or 1, that is why you got more then 8Why at most 2 ^ (k + 1) I still can't understand!

In

Div2 D / Div1 Bcan you please explain the criteria of two participants being in the same the team?I can't understand your greedy approach in div1E. Indeed, if you the last value is negative, you'd like its coefficient to be as small as possible (thus, equal to k[n-1]). If it's non-negative, yes we could double its coefficient (k[n] = k[n — 1] + 1), even though I'm not sure what it's supposed to be done if it is 0. The problem is the follow-up: now let's say we add some other number, a[n + 1] > 0. And we had a[n] < 0 and, therefore, decided to have k[n] = k[n — 1]. And now we obviously would choose to have k[n + 1] = k[n] + 1. The problem is: if 2 * a[n + 1] + a[n] > 0, then we might prefer to have k[n] = k[n — 1] + 1 as well. Could you try to better explain your solution? (maybe with an example) I'm not sure what you mean through block, but honestly, I just care about the greedy behind it, right now (to get an O(N) time complexity per query) and I'm not sure whether the blocks are meant to help me improve a solution that I supposedly already have or are meant to explain that solution (in linear time per query)

I have a solution that I think it's like editorial solution.

define

sum[l,r) =a_{l}* 2^{0}+a_{l + 1}* 2^{1}+ .... +a_{r - 1}* 2^{r - l - 1}lets define

f(i) as the maximallsuch thatsum[l,i) < 0 and if suchldoesn't exist putf(i) = 0.you can see that if you want to answer the query [

l,r) you should return the value ofsum[f[r],r) +sum[f[f[r]],f[r]) + .... +sum[l,x) whichxis the index wheref(x) is less thanl.now for solving question , when you add

i_{th}number you shouldf(i) .if it's negative , the

f(i) =i- 1 _ so it's a new Block!otherwise these indexes are candidate to being as

f(i) :f(i- 1),f(f(i- 1)),f(f(f(i- 1))), ... _ so this element makes a new block by merging some of the previous blocks!you can iterate over them and find the value of

f(i) .after that you have the value of

f(i) and you know the blocks and you can answer the queries!so I think word

Blockin editorial means the segment [f(i),i) !for checking details! 31832716

At first, if the last value is negative, k[n] = 1, not k[n-1].

Of course, some k[i] can change when we add a number to the end. But I don't really understand where is the problem for the linear solution. In this case you can just re-find all k[i].

Blocks are needed to implicitly store k[i]. Navick has already explained about them.

Yes, you ‘re right but I Think editorial is not very useful,

Because it does’nt say the meaning of Block!

For div2 C:

I do not understand the process stated in the editorial clearly.Can someone explain it to me?

Here is my code:31798101 i tried to merge all XOR operation in one number, all OR operation in one number and all AND operation in one number, then put according to the order they first appear in input, but it gave me WA. Any explanation will be very helpful.

Div1B really has a good set of test cases, which tortured me long enough. Mean nothing bad.

How to go for div2 C :( using at most 2 operations

I have a question in the editorial for 1C, Tournament, about the part

"We need to find the weakest of those components that he can lose, and the strongest of those components that he can defeat. If the first component is stronger than the second, the new sportsman forms a new component. Otherwise, all the components between the first and the second merge into one, and the new sportsman joins it."

Why do we merge the components between the first and second? I have some intuition that it is because they are "equal", so they can beat each other with bidirectional edge, but I still am not sure exactly how this works. If anyone could explain, it would be much appreciated. Thank you.

Hey can anyone please tell me the idea behind Div.2 C problem.

I am still not getting what is provided in the tutorial.