yutaka1999's blog

By yutaka1999, history, 4 years ago, In English

Hello Everyone!

Japanese Olympiad in Informatics Spring Camp 2020 will be held from Mar. 19 to Mar. 23.

There will be four online mirror contests during the camp.

The contest duration is 5 hours and there are 3 or 4 problems in each day. Problem statements will be provided both in Japanese and English.

There might be unusual tasks such as output-only tasks, optimization tasks, reactive tasks and communication tasks, just like International Olympiad in Informatics (IOI).

The contest site and registration form will be announced about 30 minutes before the contest.

Details are available in the contest information page.

We welcome all participants. Good luck and have fun!

UPD: The timezone of the latter mirror contest is modified.

UPD2: The timezone of the latter mirror contest is again modified.

UPD3: Now, you can play mirror contests during any contiguous 5 hours until 12:30 GMT.

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Just curious but will the judge be opened for analysis mode after the contest?

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

When I click the contest information page link, I see that Round 2 is 16:00 JST but that does not seems to match ur 08:00 GMT timing. Maybe there was a mistake with the timing?

Update: I have noticed that the contest information page has changed the timing to 07:00 GMT, which now matches the 16:00 JST, but the timing at this cf blog still indicates 08:00 GMT? ._.

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

Will there be an English editorial after the contest?

I have heard a lot about the high quality and difficult of JOISC. Hoping for a nice contest and solving non-zero problems

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Can you explain why there are two time ranges each day? Does that mean two contests per day?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    From the contest information page:

    "The duration of the contest is 5 hours. The same contests are held twice (Round 1 and Round 2). Contestants can participate in one of Round 1 or Round 2 according to their time zone."

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

Auto comment: topic has been updated by yutaka1999 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Why was the starting time of the second contests shifted to an hour earlier? Now it starts at the exact time when kickstart round A ends.

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

    At least you can ak kickstart in 30m unlike me :sob:

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

    It was't actually shifted, just a mistake from OP.

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Why does it say mirror contest starts at 7 GMT, but analysis mode ends in 20 minutes?

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

Auto comment: topic has been updated by yutaka1999 (previous revision, new revision, compare).

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

when can we get the solution?

»
4 years ago, # |
Rev. 7   Vote: I like it +115 Vote: I do not like it
My problem C solution.
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would you please show us why we need $$$y_i \le y_{i+1}$$$ hold for each group, instead of $$$y_i \ge y_{i+1}$$$ as Subtask 3?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      With this constraint, the set of changed elements is the prefix.

      When I add a new element, I create a new group with only one element.

      Actually, the sign does not matter, because in each group one of the coordinates is always the same.

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

    Thank you very much and can you please show the code?

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

    Maybe I didn't understand anything, but is it true that your statement about groups didn't use structure at all? For example, if we have sizes of groups 1,2,.., n, you can spent O(n) time in every iteration.

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

    Note that we will spend ≤ ( size of the group + 1 ) operations now, and also in the future, we will spend ≤ ( size of the group ) new operations because of the merged parts from the current group.

    Why is the number of future operations <= (size of the group)?

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

    I have implemented your idea but it got TLE. Do u have your own implementation?

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

Hamburger was such a pain to code xddd. I have completely no idea how, but I managed to code it without any bug xddd

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    What was your solution?

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

      In fact there is a correlation between being pain to code and being pain to describe xD.

      Assume max(L) > min(R) and max(D) > min(U) for simplicity. I will put skewers only on 4 lines determined by these values. First thing to even get started, I consider (in my mind only) k! cases relative positions of skewers. If k<=3 then one of them is "in the corner" and I can branch (wow, only 15 pts for this? this seems really rough even in comparison to what is left). If k=4 and some skewer happens to be in corner as well, branching works as well, so I am left with the hard case when every skewer is in the interior of its side.

      I iterate over positions of skewer on line x = min(R) and consider two cases. Whether the top point is on the left of the bottom point, or whether it is the other way around. In each of these cases I greedily maximize x values of bottom and top point. If top point is on the left, I first decide its coordinate and then decide the coordinate of the bottom one taking into account it can't be on the right of the leftmost right side of rectangles which intersect with exactly top and bottom side. In the second case — the other way around. And I just check whether I can put point on the right side in some place. All checks and decisions are made in constant time based on a ton of arrays with prefix/suffix minimums/maximums.

      Here is my code: https://ideone.com/RNJXof Is your solution similar to mine?

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        I have a question about the conclusion:

        "Assume max(L) > min(R) and max(D) > min(U) for simplicity. I will put skewers only on 4 lines determined by these values."

        As shown in the picture above, the rectangle in the middle isn't crossed by any straight lines, but it's necessary to put skewers on this rectangle.

        I may have got it wrong.

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

          The conclusion is a bit premature. In fact, either one of the skewers needs to be put in one of the corners of the rectangle determined by these 4 lines (and the remaining rectangles/skewers are considered recursively after purging the rectangles we already covered), or all skewers will lie on the sides of this rectangle.

          In your case, you'd put one skewer in the upper left corner of such a rectangle. When you recurse, you only need to cover two lower rectangles (and the straight lines you drew will change).

»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    What would be the expected time complexity of this?

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

    It actually passes all tests except one if you never shuffle, and if you shuffle only once in the beginning it gets 100 with the same run-time.

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

    Done, and every submission for this problem is rejudged.

    According to the stats page, the number of accepted solutions became 8 (from 28!)

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve A, somebody please.

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve Prob A building?

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +52 Vote: I do not like it

    First, I think the 11-point subtask 1 ($$$N \leq 2000$$$) is not very difficult. We let $$$dp[pos][cnt][plan]$$$ the boolean value which records if "when deciding how to decorate for building $$$1, 2, 3, ..., pos$$$, we can decorate exactly $$$cnt$$$ building in plan B, and the decoration of building $$$pos$$$ is $$$plan$$$ (A or B)." The dynamic programming works in $$$O(N^2)$$$.

    But, if we notice one good property, we can drastically improve the computing time to $$$O(N)$$$.

    The Solution to O(N)
    • »
      »
      »
      4 years ago, # ^ |
      Rev. 4   Vote: I like it +30 Vote: I do not like it

      I have a different solution to A that was not motivated by the $$$O(N^2)$$$ DP solution, but I feel is much more natural and motivatable. Call a sequence of $$$2N$$$ positive integers $$$X_1,X_2,\cdots,X_{2N}$$$ valid if each $$$X_i$$$ is equal to either $$$A_i$$$ or $$$B_i$$$ and the sequence $$$X$$$ is non-decreasing (note the lack of the "exactly" $$$N$$$ As and $$$N$$$ Bs).

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

      What are the highest official results in Japan? Who passed to IOI?

»
4 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Can we solve Day1C in $$$\Theta((M+Q)\log (M+Q))$$$?

Here is my $$$\Theta((M+Q)\log^2 (M+Q))$$$ solution and it could be optimized to $$$\Theta((M+Q)\log(M+Q) \log\log (M+Q))$$$:

Spoiler
»
4 years ago, # |
Rev. 3   Vote: I like it -24 Vote: I do not like it
hints for solving problem A
»
4 years ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

How to solve B(Hamburg Steak)?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +28 Vote: I do not like it

    Here's an extremely brief explanation.

    Let $$$maxR$$$ be the rightmost end of any rectangle. Lemma: there will be a point with exactly $$$x = minR$$$. Similarly, compute $$$maxL$$$, $$$maxD$$$, $$$minU$$$ (corrected, thanks to Elegia).

    You got a special rectangle-area and you need to put a point on each of its sides. If $$$k = 3$$$, there will be at least one point in corner. Iterate over corner, put a point there, branch with $$$k = 2$$$.

    If $$$k = 4$$$, there is also a case where there is no point in any corner of our rectangle-area. Instead, there is exactly one point on each of 4 sides. Analyze what is required by each of $$$n$$$ input rectangles. Then you can iterate over position of point on left side of the rectangle-area and greedily choose positions on remaining sides (starting with top side). It might help to assume that point from top side is on the left from point on bottom side.

    EDIT: I'm refering to solution by Swistakk and he described it some more here https://codeforces.com/blog/entry/74871?#comment-590866

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

      I think it should be minR, maxL etc.

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Insight Errichto had to problem Building4 actually allows to count number of required sequences in $$$O(n \ polylog(n))$$$ which is not doable with typical solution.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Insight: for two consecutive houses $$$(i, i+1)$$$ we can almost always deduce that something is taken. For example, if $$$i: (5, 8), i+1: (3, 10)$$$ then $$$10$$$ must be taken. Also, if $$$i: (5, 8), i+1: (9, 10)$$$ then $$$i$$$ and $$$i+1$$$ are independent and we can split the input into two parts.

    This way we can split the input into parts such that each part consists of slowly increasing pairs like $$$(1, 5), (2, 6), (5, 8), (7, 10)$$$. In the input of such sequence of pairs, the smaller value must be taken, and then the bigger value in each pair in the remaining suffix. This gives linear number of possibilities for the number of A in this part. Considering prefix shorter by 1 changes the number of A by 1, so the possible numbers of A are an interval. The sum of possible intervals like $$$[5, 10]$$$ and $$$[2, 4]$$$ are also an interval, here it would be $$$[7, 14]$$$. You can determine how many A you need from each interval then in some greedy way.

    This logic both gives a non-dp solution and provides a proof why the possible total numbers of A's are an interval. And you can use FFT and count ways too.

»
4 years ago, # |
  Vote: I like it +91 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How we can see results of the second online mirror which is going now?

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

How to solve day2 B and C?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I tried to solve B by storing all cliques using DSU, but failed to implement it:(

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +26 Vote: I do not like it

    B:

    Assume we have a vertex $$$v$$$ and a clique $$$c$$$. If there is an edge between $$$v$$$ and any vertex in $$$c$$$, then the social exchange will create all possible edges originated in $$$v$$$ and ending in every vertex from $$$c$$$.

    Suppose we have two cliques $$$A$$$ and $$$B$$$. If we have an edge that goes from some vertex in $$$A$$$ to some vertex in $$$B$$$ and an edge that goes from some vertex in $$$B$$$ to some vertex in $$$A$$$, then after the social exchange these two cliques merge into one clique.

    With these observations we can maintain a set of cliques and edges between them. When we have to merge two cliques, we can use small to large technique to do it effectively.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +50 Vote: I do not like it

    For Ruins 3 (problem 3), it's just a 2-dimensional dynamic programming and we can solve in $$$O(N^3)$$$. However, despite I said "just a 2-dimensional dynamic programming", it's very difficult.

    Let the DP table $$$dp[x][y]$$$. Of course, we will let $$$x$$$ the current position. So, what the $$$y$$$ stand for? It's quite non-obvious.

    The Brief Sketch of Solution
    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it +10 Vote: I do not like it

      My implementation. Similar to the above, except I run DP in the order $$$2N\ldots 1$$$. $$$dp[j]$$$ corresponds to $$$level=j+1$$$ as described above, meaning that we currently have pillars with final height $$$1\ldots j$$$ but none with $$$j+1$$$.

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

        What's your thought process to calculate $$$ways[i]$$$ in your code? I have a different way of calculating it though both ways end up as $$$\binom{2n}{n} \cdot (n-1)!$$$, so I think there should be a simple combinatorial proof that I missed.

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

          It's similar to calculating the number of correct bracket sequences. There's probably some rotation argument that shows that only one out of every $$$n$$$ of the $$$2n\cdot (2n-1)\cdots (n+1)$$$ candidates is okay.

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

        Hi Benq, I have been trying to understand your implementation for hours and have failed to understand the solution. I am wondering if you could explain what specifically is the ways array calculating the number of ways of (number of ways to number pillars that stay up that have not been numbered?), and how you were motivated to calculate it as such.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          (roughly the following)

          For each of $$$k$$$ pillars assign them one of the heights $$$1,1,2,2,3,3,\ldots,k,k$$$ such that no two are assigned the same version of the same height. After placing a pillar, while two pillars have the same height decrease one of their heights. How many ways are there to do this such that the first time when there is a pillar of height $$$1$$$ is when the $$$k$$$-th pillar is placed? $$$precalc[k-1][k-1]\cdot fac[k-1]$$$ calculates the number of ways to place the first $$$k-1$$$ pillars. Do you see why this is then multiplied by $$$k+1$$$?

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

            I finally figured it out! (that took way to long oops). I see that you multiply by 2 for single elements as you're calculating the ways array so that when you divide by 2 ^ n later it correctly divides out pairs of two so they are not counted twice, and k + 1 can really be thought of as (k — 1) + 2 to account for adding the single 1. Thank you for your help! Just curious is this what inspired USACO Open p1, or is it just a coincidence they use this same technique?

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

              Just a coincidence. (Personally, I didn't notice the similarity at all.)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I've finally managed to understand the solution. Very beautiful problem!

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve A and B day2 please.

»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

How to solve day 2 A? I could only get 64...

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    (Why the downvotes?)

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

      Can someone further explain how the edges were generated with < 20 000 operations, as that was the hardest step for me.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        There are at most $$$3N$$$ edges and each should take about $$$\log_2 N$$$ queries.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      first split vertices 1…i−1 into two parts such that each part is an independent set (this must be possible since the graph is bipartite)

      I agree that two parts are possible but how to obtain such a split? When we have a new vertex $$$i$$$ and it's independent with each of two existing parts, how do you know where to put it?

      (I split into four parts instead because degrees don't exceed 3)

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +18 Vote: I do not like it

        You only need to consider the edges that are present in the graph up to that point when splitting it into two parts (see the code).

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

If you participated Day1 Round2 but not Round1, then your account disappeared! That's bad!!

My account and 300iq's are gone (and 300iq has 300points in Day1 and Day2!!)

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve A and C day3? please

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    For A, maintain a dp for each "connected component" from bottom to top. The dp for each cell denotes the maximum sum of stars you can remain if you forcefully pick the cell. Note that even if a cell is empty, we also consider it possible to pick the cell. To deal with stars in the same column, note that a higher star with lower value is useless, and after removing them, each column's star values are monotonic. Replace each star value with the difference between its value and the value of the star below it. Now, it is straightforward to update the dp when you go to the next row and merge components. You can optimize the dp with a lazy segment tree.

    Sorry for the terrible explanation, maybe my code explains it better.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Day3C:
    for $$$A \ge 3$$$, let y[i] = min(dis[u[i]], dis[v[i]]) % 3, then you can easily get to a nearer vertex through the color of the edge.
    otherwise ($$$A = 2$$$, $$$B\ge 6$$$ and $$$M = N - 1$$$), you should paint a chain with a period of 100110, then you can spend at most 3 steps to determine the direction you are walking so you will waste at most 6 steps. For a general tree, you should let the color of the child edge different from the father when there are branches. Then you can determine the direction at a vertex with $$$deg \ge 3$$$ and straightly go through the path to the root.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Thank you very much!

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it
      • well, how will you differentiate between
      • "100---" from right to left going toward 0
      • "-001--" from left to right going opposite 0
      • in both ways you will have "001" ?
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        Noticed that the information also contained the adjacency, so you actually got the color of 5 edges, not 3.

»
4 years ago, # |
Rev. 3   Vote: I like it +24 Vote: I do not like it

Day 3 tasks here: https://oj.uz/problems/source/496

Note that the interactor of stray is incomplete (it chooses roads randomly), and all submissions will be rejudged after the grader is fixed.

UPD: Now the interactor of stray is the same as in JOI.

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

    Currently, there is a problem in submitting the code on oj.uz I think.

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

    i submitted the code in oj.uz for problem C and i got 100 points but when i submit the same code in JOI submit i got 20 points + 2 wrong test cases in the last 2 subtasks , strange

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

      Currently, the interactor chooses the roads randomly as in the sample grader. JOI's grader should have some complicated strategy.

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

How can I submit the code after the contest?

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve day 3 B (Harvest)?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Solution to Harvest
»
4 years ago, # |
  Vote: I like it +60 Vote: I do not like it

Dango is the easiest local search ever, it was trivial to get 100 pts here, yet very few managed to do this. Why :|?

What I've done is:

while (something improved in last C steps) {
take random dango
if there are >=2 dangos blocking it then continue
if there is 1 dango blocking it then remove it
put this dango
}

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Lol, I removed everything in $$$5\times5$$$ square and put the best combination of dangos. Only got 60 :D

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

    Why should we replace a dango if it is blocked only by 1 dango?

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

      To get another solution with the same number of dangos.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      As Tutis said, it doesn't make our solution worse. However it makes your search space much bigger, so it will be possible to find improvements by some sequences of consecutive changes. Without that line, it gets 0 pts :P.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Local searches are not very known, especially within the high school students community. Please note that the output only tasks are very rare too. I think I have never seen them in other places except for JOI and IOI.

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

      "I think I have never seen them in other places except for JOI and IOI." — said by guy who I teamed up with in Reply Code Challenge a Week ago and coming from a country that is home to Deadline24 and Marathon24 xD

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

        I was still describing contests aimed for the high-school students. When I was in high-school I participated in Deadline24 and Marathon24 and never used any hill climbing nor annealing.

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

    I spent 3 hours and got 39 pts :(

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It’s an output only, you don’t want to do it unless they offer a plane ticket to Dublin

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Fair point. But maybe you can put there some data structures to help you out?

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        No, OO is a much worser joke :(

        Even those DS with +20 queries are at least science, isn’t it?

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

          I believe that all the local searches and the whole discrete optimization field are still more scientific than the data structures with dozens of types of queries.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            I didn’t mentioned discrete optimization at all. Local searches can be science with provable guarantees, but OO doesn’t work like that. And they give dozens of huge TC to analyze instead of dozens of queries that can at least be described in natural word.

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

    Can you please provide your code for this solution. I am interested in your implementation as this is the first time i hear about local search algorithms. Thank you.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it

      Here you go: https://ideone.com/K3nyE4

      Key part is within lines 142-172. All the other things are kinda boring boilerplate like reading the input, generating valid positions of dangos, putting/removing dangos and printing result. I'm quite sure lines 127-141 are completely useless and can be removed.

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

How to solve A please.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +34 Vote: I do not like it

    We can use centroid decomposition.

    Root the tree at the centroid, and keep track of previous centroids (these vertices will be "blocked" in the tree).

    We will consider a city, such that the current centroid is included in this city, and all "blocked" vertices and vertices below them must not be included.

    To construct this city, we take all vertices that have the same color as the centroid, check their parents in the tree, and if the parent has a different color, we will repeat the same proccess with that color. This can be done efficiently with a queue.

    After this proccess terminates (there are no more colors that we must add), we will check if none of the added colors have vertices under "blocked" vertices, and if this is true we will minimize the answer with $$$amountOfColorsAdded - 1$$$.

    After that, mark the current centroid as "blocked" and recursively solve for the subtrees.

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    An alternative solution using LCA and DSU.

    Root the tree arbitrarily and color the cities. Two colors are connected in the DSU if any capital city including one of them also includes the other. We mark a vertex as visited if it's been completely processed.

    The LCA of a capital city is necessarily the LCA of some color, so we push all of them in a queue. For each candidate LCA starting from the bottom most and going up, we try to construct a capital city rooted at that LCA. We will use a queue to store necessary vertices for the capital city, initially it contains unvisited vertices with the same color as the candidate LCA.

    For each vertex in the queue, we connect its color with the color of the candidate LCA in the DSU, then if the LCA of its color is below the candidate LCA, we mark it as visited and push unvisited vertices of its same color to the queue, then redo the same thing for its nearest unvisited ancestor that is below the candidate LCA (it can be done efficiently with another DSU).

    Once this process is finished, we check if all vertices of the colors connected to the color of the candidate LCA are visited and try to minimize the answer with sizeofcomponent-1 if it's the case.

    UPD: I realized this should've given a 0 instead of 100, it fails on a small test like this (tree rooted at 1)

    6 3

    1 2

    1 3

    3 4

    4 5

    5 6

    1 2 3 1 2 3

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    did anyone use the following idea to solve the problem(capital city)

    find lca of all nodes of each colour.
    for example if nodes a1,a2........am are coloured with colour x
    their lca is y and we add paths from y to each ai (i>=1 and i<=m)

    now we repeat this algorithm:
    1.choose path such that depth of the lower vertex is minimum.
    2.take all paths such that they intersect with it and keep extending till possible(using dfs and path compression)
    (this solution is an extension of the solution of subtask 3)
    remove these paths and repeat the algorithm till the set of paths is not empty.

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

    I have another possible soln. Haven't coded it yet.

    The idea is to create a directed graph where an edge X->Y means that there is an edge between a town of city X to a town of city Y and that to connect all towns of city X, we will be required to merge city Y to it. The answer will be the smallest size strongly connected component in such a graph.

    To create the graph, I do the following.
    Let k be a constant. For all cities with no. of towns >= k, run a linear O(n) scan to create the edges.
    Else, check all (no. of towns)^2 pairs in O(logn) time for edges.

»
4 years ago, # |
Rev. 6   Vote: I like it +19 Vote: I do not like it

Dango is a very cool problem! And the awesome visualizer is the coolest for sure!

I used Simulated Annealing to solve this problem. For now, my solutions are better than the given $$$Z$$$ (the grading values) $$$2, 6, 5, 8, 7, 8$$$, respectively.

What are your scores? And how to achieve them?

UPD: My Simulated Annealing program on Ubuntu Pastebin.

UPD2: My submission on oj.uz.

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

    And the awesome visualizer is the coolest for sure!

    Indeed it looks great, works very fast and is really readable. However it is kinda useless. I don't imagine how you can get anything useful from it except for cases when your code clearly doesn't work as intended and you can see it on very small testcases.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      Yeah, it just looks great, and indeed didn't help me. (but it looks great, that's neat to me)

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

    Seams very complicated. Especially when i've never heard about annealing xd

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      But actually it's very simple, relatively.

      Because in general, Output Only Problems are very complicated and need participants to find each input file's special properties and solve them separately.

      For this problem I just used a single program and easily got full points, that's why it's relatively simple.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Will analysis be avalibe for Day 4?

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

    Are there any available analysis at all?

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

      Analysis as in analysis mode, not an editorial. It was open after every day for about 7~8 hours.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -29 Vote: I do not like it

        Sooo, analysis for you means ... upsolving xd? Analysis==editorial for me xd

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          It is stated as "Analysis Mode" in the CMS server previously so I guess that's why the word analysis is used here.

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve day 4 C (Treatment project)?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +84 Vote: I do not like it

    I've solved this problem during the contest. It was really a good problem! I was so impressed when I got the solution. Note that in this editorial $$$L_i$$$ is decreased by $$$1$$$, so that treatment project will process half-open interval.

    First, to recover all citizens, we need to treat all people at least once. It is not an exception for person $$$1$$$ and $$$N$$$. So, we need to at least process treatment project $$$i, j$$$ which is $$$L_i = 0$$$ and $$$R_j = N$$$. It's okay if $$$i = j$$$ if possible.

    Also, if all $$$N$$$ people finally recovered from coronavirus, there is a "border line" between infected area and non-infected area, if you plot in 2D when $$$x$$$-axis stands for "the number of days from start" and $$$y$$$-axis stands for "the ID of citizen". If no borderline exists, it means there is a hole that expands infection finally to all citizens.

    Combining this two facts, the borderline starts at $$$L_i = 0$$$ and ends at $$$R_j = N$$$. and it should be connected. So now, let's use Dijkstra's Algorithm by letting each treatment project to vertices!

    We can link from treatment project $$$i$$$ to treatment project $$$j$$$ (directed edge) if:

    • When $$$T_i \leq T_j$$$, the $$$L_j$$$ should be at most $$$R_i - (T_j - T_i)$$$
    • When $$$T_i \geq T_j$$$, the $$$R_i$$$ should be at least $$$L_j - (T_i - T_j)$$$
    And the cost of vertex $$$i$$$ is exactly $$$C_i$$$. The answer is the minimum sum of vertex cost from any vertex of $$$L_i = 0$$$ to any vertex of $$$R_j = 0$$$. Using Dijkstra's Algorithm, we can calculate in $$$O(M^2)$$$. That's worth 35 points so far.

    However, we can improve it finally to time complexity $$$O(M \log M)$$$.
    The way to get 100 points
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will editorial be published (even in Japanese)?

»
4 years ago, # |
  Vote: I like it +82 Vote: I do not like it

Hello Everyone!

I made a mirror contest on AtCoder. I got contact with the committee and was allowed to use real graders, which means that you can know real score of Stray Cat (Day3-3).

I hope many people use it!

https://atcoder.jp/contests/joisc2020?lang=en

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

When will be the test data of day 4 open?

»
4 years ago, # |
Rev. 3   Vote: I like it +50 Vote: I do not like it

Important Information

IOI 2020 Japan Team is now selected.

Rank Name Username
1st Place Masataka Yoneda E869120
2nd Place Hirotaka Yoneda square1001
3rd Place Rintaro Matsuo QCFium
4th Place Tomohito Hoshii TMJN (AtCoder)

Source: Link1, Link2
Hope IOI 2020 will not be cancelled.

(Note: All four participants shares his results on twitter.)

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi ojuz, I think your testcases arent strong enough for Capital City.

https://oj.uz/submission/943508 This passed despite giving the wrong output on this input:

input

The correct answer should be 2 but instead it outputs 1.