### rng_58's blog

By rng_58, history, 5 years ago,

We will hold Japanese Student Championship 2019 Qualification. (Despite its name, the contest is open for all international participants.)

The point values will be announced later.

We are looking forward to your participation!

• +96

| Write comment?
 » 5 years ago, # |   +33 The Atcoder's problems usually have a very High QualityI think the contest is the same as beforeWish everybody good luck
 » 5 years ago, # |   +3 [Offtopic] Is it possible to participate in Virtual contest for previous Atcoder contests ?
•  » » 5 years ago, # ^ |   +13 You should definitely check out — https://vjudge.net
 » 5 years ago, # |   +14 20 mins before the contest start)
 » 5 years ago, # |   -10 10 minutes left.And then the contest will begin.
 » 5 years ago, # |   0 I hope to become blue in AtCoder
 » 5 years ago, # |   0 5 more minutes!!! all the best guys!!!
 » 5 years ago, # |   0 How to solve C,I have no Idea about it...
•  » » 5 years ago, # ^ |   0
•  » » » 5 years ago, # ^ |   0 I see.
•  » » 5 years ago, # ^ |   0 editorials are already up, check out there
•  » » » 5 years ago, # ^ |   0 English editorials ??
•  » » » » 5 years ago, # ^ |   0 yes
•  » » 5 years ago, # ^ | ← Rev. 3 →   +6 since number of intervals that we will invert it is $N$ and all intervals must be differentso we know every cell will be starting cell of interval or ending cell of interval let's make the value of all cells that have white color $0$ and black color $1$. so for every cell number of intervals that cell is inside it $mod 2$ must equal to its value so it will be white.first we will solve it when order doesn't matter : we will loop on every cell and have variable that denotes the number of intervals that started and didn't end and denote it as $cnt$ so if ($cnt$ + $arr[i]$) $mod$ $2$ $!=$ $0$ then we need to start new interval to make this cell white else we will close interval, to find number of ways to make all cells white in every time that we will close interval we will make $ways * (opened intervals)$ and $ways$ will represent number of ways if order doesn't matter. since order matters then ans will be equal to $ways * N!$. and in cases like if the first cell is white or number of opened intervals $< 0$ or number of opened intervals $> n$ or after ending of loop number of opened intervals $> 0$ then their answer will be $0$.my submission
•  » » » 5 years ago, # ^ |   +5 Thank you very much
 » 5 years ago, # |   -34 Of course the atcoder contest turns into a typing race the one time I almost cut my finger off while cooking right before the contest. I could have done so much better if I didn't have to write without my left forefinger :Dd
•  » » 5 years ago, # ^ |   +3 But there wasn't much typing required. Way more thinking than typing, at least.
 » 5 years ago, # |   0 MFW I read F as "N elements are sorted in non-decreasing order,"
•  » » 5 years ago, # ^ |   +3 After the contest I spent at least an hour wondering why my brutetester wasn't finding any bugs before realizing the same thing :/
 » 5 years ago, # |   +3 How to solve problem D?
 » 5 years ago, # | ← Rev. 2 →   0 in problem Cchanging the order of operations does not affect the resultHow to prove ?Someone explain C in simple word?Didn't get editorial!!
•  » » 5 years ago, # ^ |   0 changing the order of operations does not affect the result because what matters is the number of times we flip the color of a square(in fact just the parity of number of flips). Assume the i index is flipped even number of times then the color remains preserved. Example: S="BWWB". We flip in order (1,3) and then (2,4) the index 2 is flipped twice. Even if we change the order of operation i.e (2,4) and then (1,3) we flip index 2 twice. When we flip a color even number of times, we get the same color back irrespective of the order of operations. Similar argument for odd flips. The color is inverted irrespective of order of operations.
 » 5 years ago, # | ← Rev. 4 →   +5 Again, author has a way other than GF to get formula for F. But it is solvable through generating function. Don't need to be creative just do like a farmer :)Assuming the $(m + 1)$-th largest element is $k$. We need to compute the coefficient of each term $x^i$ in $\sum_{k = 1}^{r}{(1 - x^{k})^{n - m}x^{km}}$.
•  » » 5 years ago, # ^ |   0 Sorry but I don't understand how this works, can you elaborate? (I got solution similar to editorial I think).
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Let count the number of sequences that $m$-th $= k >$ $(m + 1)$-th.There are $C(n, m)$ ways to choose places for $m$ largest elements.GF for $m$ largest elements: $x^{km}\frac{1}{(1 - x)^m} - x^{km + m}\frac{1}{(1 - x)^m}$. (note that at least one element is $k$)GF for remaining $(n - m)$ elements: $\frac{(1 - x^k)^{n - m}}{(1 - x)^{n - m}}$.GF for the one more element to ensure the sum of them are fixed: $\frac{1}{1 - x}$.
 » 5 years ago, # | ← Rev. 2 →   +33 D = IMO Shortlist 1983 Problem lol (see P1 here)
•  » » 5 years ago, # ^ |   0 lol. atcoder does same most of time. but this time they went back too much.. 1983 haha..btw how do u find the hidden treasure
•  » » » 5 years ago, # ^ |   0 I've done the exact same problem before in IMO training.
 » 5 years ago, # |   -16 Problem B: Can someone explain me, please, how we get k*(k-1)/2? What is it? Why exactly k*(k-1)/2?
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 For each element, we have two types of inversions, 1) Inversions among it's own sequence2) Inversions among other sequences that are concatenated.For type 1), we just calculate in given sequence, in $O(n^2)$.For type 2), in given sequence of $N$ elements, you need to find for each element how many elements are smaller (or larger) than it ( strictly ). So if there are $x$ numbers smaller than some element, then in first copy of the sequence the other $(k-1)$ copies on the right will each have those x numbers. So we add $(k-1)*x$ inversions, then for the second copy of the sequence, we have $(k-2)$ copies on the right. So, this way, you will add $x$, $(k-1) + (k-2) + (k-3) + ... + (1) + (0)$ times.[ $0$ is for the last copy that you concatenate ]. And $\sum_{i=1}^{k-1}i$ = $\frac{k*(k-1)}{2}$
 » 5 years ago, # |   +11 I can't understand the Editorial of D. Why it is correct when the edges of same level form a bipartite graph? If there's a circle with even number of nodes,it's still a bipartite graph,but we can go back with each edge traveled exactly once.
•  » » 5 years ago, # ^ |   0 We need the length of any cycle to be even, not the number of times each edge is used. I had to read the note at the end to understand this part:"For example, if we leave Room 2 , traverse the path 2 → 3 → 2 → 3 → 2 → 1 → 2 while only passing passages of level 1 and get back to Room 2 , we pass through a passage six times."
•  » » » 5 years ago, # ^ |   0 thx.
•  » » » 5 years ago, # ^ |   0 It's QUITE badly phrased then. I thought it'll be a tree because only then will each edge be used exactly even number of times.(Not to mention that the example also IS a tree) :'(
 » 5 years ago, # |   +3 In question D, I have seen many solutions and most of them first calculated xor of the node numbers and then printed least significant active bit(LSAB) as the color between those edges, can someone help me why we did this? (why we took xor & LSAB and how is it related to bipartite graph )
•  » » 5 years ago, # ^ |   0 Finding the LSAB of XOR directly translates to finding the maximum number of bits from the right which are the same. Basically, an edge in level i connects two nodes with labels such that the least significant i-1 bits are the same but the least significant ith bit is different.Now think about travelling edges only in level i. This means everytime you travel an edge in level i, the ith bit will keep on changing. This will never contain any odd cycles as if there were odd cycles, the first and the last element of the cycle will not be the same, which is a contradiction. Edges of level i form a bipartite graph, which is what is required.