Geothermal's blog

By Geothermal, history, 2 years ago, In English

A — Tenki

This is a fairly simple task--just iterate over all positions in the strings and count the ones where S[i] = T[i].

Runtime: $$$O(|S|)$$$. Click here for my submission.


B — Power Socket

Note that we already have one socket, so we need to fill $$$B-1$$$ more sockets. Additionally, each new outlet we add will take up one socket and add $$$A$$$ sockets, resulting in a net addition of $$$A-1$$$ sockets. We thus need to create at least $$$B-1$$$ sockets where each outlet gives us $$$A-1$$$ sockets, making our answer $$$\lceil \frac{B-1}{A-1} \rceil$$$. Since most programming languages use floor division, we can also express this as $$$\lfloor \frac{A+B-3}{A-1} \rfloor$$$.

Runtime: $$$O(1)$$$. Click here for my submission.


C — Lower

We essentially use two pointers. Maintain the starting position at zero. Then, while the next position isn't higher than the current one, we make that move. If the next position is higher than the current one, we need to reset the starting position to the current position. The answer is then the maximum number of consecutive moves we make without resetting the starting position.

You can also think of this as simulating the given process and picking the best answer, but only from starting positions that are higher than the previous position. The reason this gives us the best possible answer is that if we have a starting position lower than the position before it, we could get one extra move by starting from the previous position instead, so we should never start at a position that is not higher than its previous position.

Runtime: $$$O(N)$$$. Click here for my submission.


D — ModSum

Notice that the result when a number is taken mod $$$X$$$ can be at most $$$X-1$$$. Therefore, since we're summing results mod $$$1$$$, $$$2$$$, $$$3$$$, and so on, up to $$$N$$$, our answer can be at most $$$0 + 1 + 2 + \cdots + N-1 = \frac{N(N-1)}{2}$$$.

Now, let's prove that we can always achieve this answer. Take $$$1$$$ mod $$$2$$$, $$$2$$$ mod $$$3$$$, and so on, up to $$$N-1$$$ mod $$$N$$$. Then, take $$$N$$$ mod $$$1$$$, which adds zero to the sum. Therefore, this approach gives us an answer of $$$1 + 2 + 3 + \cdots + N-1 = \frac{N(N-1)}{2}$$$.

Runtime: $$$O(1)$$$. Click here for my submission.


E — League

Let's rephrase this as a graph problem. We essentially have $$$\dbinom{N}{2}$$$ matches we need to play, and we are given a set of criteria that each indicate that some match must be played before some other match. We can express the matches as vertices on a graph and the given requirements as directed edges. An edge from one match to another means that the first match must be played before the second.

Phrased like this, the problem seems very similar to topological sorting (given the set of requirements that one vertex must come before another). And indeed, this motivates a similar solution. Maintain the set of matches with no incoming edges. Then, while this set is non-empty, increase the day by one and delete these matches from the graph, removing their outgoing edges as well. Finally, replace the set of matches with no incoming edges by adding any matches whose last incoming edges were removed. (To avoid checking each individual match every time, we can maintain the indegrees of each match and then simply check whether a match now has indegree zero each time we remove one of its incoming edges.)

After the set is empty, we must have either processed every match or encountered a cycle. In the latter case, the answer is $$$-1$$$, as this indicates that there is no order in which to play the matches. In the former case, we can now output the number of days we computed.

Runtime: $$$O(N^2)$$$. Click here for my submission.


F — Engines

First, I'll present the (rather sketchy) solution I used in-contest. Then, I'll discuss the somewhat simpler approach that was most likely intended by the problemsetters.

My solution used a pruned complete search. The actual idea is fairly simple--the challenging part is showing that it will run in time.

First, let's split into four cases. In two of the cases, we'll be attempting to maximize the x-coordinate; in the other two we'll try to minimize it. Similarly, in two of the cases, we'll attempt to maximize the y-coordinate, and in the other two we'll try to minimize it. (The motivation for these cases is that we maximize our end result by either maximizing or minimizing the two coordinates.) The rest of the solution will be tailored to the case in which we attempt to maximize both coordinates--the other cases can be made identical by multiplying the appropriate values in the data by $$$-1$$$.

Now, let's make a key observation. If, after considering some number of the engines, we could reach two points $$$(a, b)$$$ and $$$(c, d)$$$, with $$$a <= c$$$ and $$$b <= d$$$, we shouldn't consider $$$(a, b)$$$ in the future, as no matter what moves we make later on, $$$(c, d)$$$ will always do a better job of maximizing $$$x$$$ and $$$y$$$.

Let's suppose we're adding the engines one by one. Given a set of candidate points we've reached so far, our new set of candidates is the original set plus the points in the original set when the current engine is added to them. Then, we can prune this data to delete any redundant nodes as outlined in our observation.

Finally, after we process every engine, we can iterate over all points in our candidate set and pick the one that gives us the best answer. We'll then print the best answer from all four of our cases.

We should be able to intuitively see that this is correct--each case is guaranteed to print the correct answer if that answer lies in its quadrant. However, the tricky part is bounding its time complexity. One fairly simple bound is $$$O(N^2 \, maxX)$$$, as we consider $$$N$$$ engines, and at any point our set may contain at most $$$O(N \, maxX)$$$ points because it will contain at most one point for each X-coordinate. However, in practice, we actually do much better than this, as it's rare that we'll actually have anywhere near $$$N \, maxX$$$ points. My solution had an unnecessary $$$\log N$$$ factor in the big-O expression (though this made it somewhat faster in practice--I sorted the candidate points rather than iterating over every possible position), but it passed in about 900 ms. It's possible that some particularly tough test case might cause this submission to TLE, but such a case would have to be very contrived.

Click here for my submission.


Now, let's discuss a simpler and more efficient solution. The key observation is that when we order the engines by the angles their vectors make with the x-axis, the answer will include vectors in some contiguous range. A proof of this fact is at this link. Then, the solution is fairly easy to implement--we can iterate over all possible ranges and compute the answers for each of them, taking the maximum as our result. When implemented appropriately, this is an $$$O(N^2)$$$ approach. Credit for this solution goes to silxi, as he was the one who showed it to me after we both finished the contest.


As always, feel free to post questions or comments below.

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

»
2 years ago, # |
  Vote: I like it -54 Vote: I do not like it

I am the first to comment for both announcement and tutorial.

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

how can u write editorial so fast?you were the participant of contest

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

    He usually finishes the contest before time is up, so he writes the editorial during that time period. Also he is a really fast typist. ;)

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

    He finished all the problems in 45 minutes.

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

After sorting by the angles, couldn't you get $$$O(N)$$$ with two pointers?

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

    You can, but there are some corner cases with the ends of the considered halfplane.

»
2 years ago, # |
  Vote: I like it +26 Vote: I do not like it

It seems that using ordinary greedy algorithm + randomize can pass the tests of problem $$$F$$$. Check this submission for detail.

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

For problem F, I first came up with the solution to keep $$$minY$$$ and $$$maxY$$$ for each $$$X$$$, but I thought it is too slow so I gave up it. After some thought I did it with sorting by angles then two pointers to achieve $$$O(NlogN)$$$ time complexity.

I think it is easy to construct such test cases to break the former solution: we can set the $$$x$$$s as $$$1, 2, 4, 8, \dots$$$ and $$$-1, -2, -4, -8, \dots$$$.

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

Please post link to silxi's submission also.

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

Any help why my solution on E gave wrong answer on some test cases. Thank you :)

I used queue in vector.

https://atcoder.jp/contests/abc139/submissions/7291162

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

F was well-known, but I didn't know it.

I hope there will be no well-known problems next round.

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

    What is the name of this problem?

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

      I don't know the exact name of this well-known problem.

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

Please elaborate the problem B, what exactly we need to do in this and how to do:)

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

    We need to convert 1(initally given) socket into 'b' empty sockets.To do that we can use a wire which has 'a' empty sockets. So now to add 'a' empty sockets you need to use 1 socket from empty sockets we have.

    So let empty sockets we currently have = t.

    Initially t=1, now loop till t!=b. In each loop by adding '+a' empty sockets in 't' and removing '1' empty socket from 't' as explained above.

    My code: https://atcoder.jp/contests/abc139/submissions/7276398

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

    Each time, you remove 1 empty socket and add A empty sockets to your empty sockets, so number of empty sockets increases by A — 1; and you want to increase it by B — 1 at the end, so the answer is ceil((B — 1) / (A — 1)).

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Another way to think about E: the answer is equal to the number of nodes in the longest path in the dependency graph.

You can compute the length of the longest path with a dp by processing the nodes in reverse topological order.

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

    Can you please explain the logic behind your approach, thank you in advance.

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

    But won't the no. of edges in the graph be O(N^3)?

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

      no. of edges is exactly N*(N-2) one for each A[i][j] — A[i][j + 1] pairs

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

Can E be solved with maximum matching? or its overhead?

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

so hectic that I implemented RMQ and binary search for C

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

E — O(n^3) passes with pragmas https://atcoder.jp/contests/abc139/submissions/7299157 ( I am not the author, I slightly changed one of the AC solution). Is it possible that for some case minimum number of days requried to play all matches is (n*(n-1))/2 ?

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

Here is my approach for F:

https://atcoder.jp/contests/abc139/submissions/7299412

I can't figure out why I'm failing some of the test cases. Can someone help me identify what I'm doing wrong? Thanks in advance

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

why does a solution of type O(n) pass on problem D

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

I tried implementing silxi's solution for problem F, but it is giving me WA for a few test cases.

To find whether two given vectors lie in the same halfplane or not I used the fact that that two points (x1,y1) and (x2,y2) lie on the same side of a line ax+by+c if ax1+by1+c and ax2+by2+c have same sign. The line (ax+by+c) can be taken as perpendicular to one vector and passing through origin.

Here's my solution. Any help would be appreciated. Thank You. :) https://atcoder.jp/contests/abc139/submissions/7315942

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

    Since there are only $$$O(n^2)$$$ contiguous ranges of points, we can simply try them all and take the maximum.

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

      Can you please explain what exactly do you mean by contiguous ranges of points?

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

Geothermal I think it'll be great if you also link the problem titles to the link of the problems in the contest like the codeforces editorials.