rng_58's blog

Japanese Student Championship 2019 Qualification Announcement
By rng_58, history, 5 years ago, In English

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!

  • Vote: I like it
  • +96
  • Vote: I do not like it

Comments Comments (36)
| Write comment?
»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

The Atcoder's problems usually have a very High Quality

I think the contest is the same as before

Wish everybody good luck

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

[Offtopic] Is it possible to participate in Virtual contest for previous Atcoder contests ?

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

20 mins before the contest start)

→ Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

10 minutes left.And then the contest will begin.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope to become blue in AtCoder

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

5 more minutes!!! all the best guys!!!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C,I have no Idea about it...

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://img.atcoder.jp/jsc2019-qual/editorial.pdf

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    editorials are already up, check out there

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    since number of intervals that we will invert it is $$$N$$$ and all intervals must be different

    so 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

    → Reply
»
5 years ago, # |
  Vote: I like it -34 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    But there wasn't much typing required. Way more thinking than typing, at least.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

MFW I read F as "N elements are sorted in non-decreasing order,"

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    After the contest I spent at least an hour wondering why my brutetester wasn't finding any bugs before realizing the same thing :/

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve problem D?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

in problem C

changing the order of operations does not affect the result

How to prove ?

Someone explain C in simple word?Didn't get editorial!!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

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}}$$$.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry but I don't understand how this works, can you elaborate? (I got solution similar to editorial I think).

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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}$$$.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +33 Vote: I do not like it

D = IMO Shortlist 1983 Problem lol (see P1 here)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've done the exact same problem before in IMO training.

      → Reply
»
5 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Problem B: Can someone explain me, please, how we get k*(k-1)/2? What is it? Why exactly k*(k-1)/2?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    For each element, we have two types of inversions,

    1) Inversions among it's own sequence

    2) 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}$$$

    → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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."

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thx.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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) :'(

      → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 )

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply