### rng_58's blog

By rng_58, history, 22 months 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!  Comments (38)
 » The Atcoder's problems usually have a very High QualityI think the contest is the same as beforeWish everybody good luck
 » [Offtopic] Is it possible to participate in Virtual contest for previous Atcoder contests ?
•  » » You should definitely check out — https://vjudge.net
 » 20 mins before the contest start)
 » 10 minutes left.And then the contest will begin.
 » I hope to become blue in AtCoder
 » 5 more minutes!!! all the best guys!!!
 » How to solve C,I have no Idea about it...
•  » »
•  » » » I see.
•  » » editorials are already up, check out there
•  » » » English editorials ??
•  » » » » yes
•  » » 22 months ago, # ^ | ← Rev. 3 →   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
•  » » » Thank you very much
 » 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
•  » » But there wasn't much typing required. Way more thinking than typing, at least.
 » MFW I read F as "N elements are sorted in non-decreasing order,"
•  » » After the contest I spent at least an hour wondering why my brutetester wasn't finding any bugs before realizing the same thing :/
 » How to solve problem D?
 » 22 months ago, # | ← Rev. 2 →   in problem Cchanging the order of operations does not affect the resultHow to prove ?Someone explain C in simple word?Didn't get editorial!!
•  » » 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.
 » 22 months ago, # | ← Rev. 4 →   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}}$.
•  » » Sorry but I don't understand how this works, can you elaborate? (I got solution similar to editorial I think).
•  » » » 22 months ago, # ^ | ← Rev. 3 →   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}$.
 » 22 months ago, # | ← Rev. 2 →   D = IMO Shortlist 1983 Problem lol (see P1 here)
•  » » 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
•  » » » I've done the exact same problem before in IMO training.
•  » » » » hmm.. awesome.
 » Problem B: Can someone explain me, please, how we get k*(k-1)/2? What is it? Why exactly k*(k-1)/2?
•  » » 22 months ago, # ^ | ← Rev. 3 →   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}$
 » 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.
•  » » 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."
•  » » » thx.
•  » » » 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) :'(
 » The editorial of problem C is just offering a way to solve the problem,but why?
 » 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 )
•  » » 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.