Yes, I just give a rough idea. Those parts should be taken care when implementing.

It can be solved with sweep line algo and segment tree in $$$O(N \lg N)$$$.

1. For each rectangle $$$[x_1, x_2] \times [y_1, y_2]$$$, produce two events $$$(x_1, (y_1, y_2), +)$$$ and $$$(x_2, (y_1, y_2), -)$$$.
2. Sort all the events (there are $$$2N$$$ such many) by $$$x$$$.
3. From minimum $$$x$$$ to maximum $$$x$$$, if it's from left side of some rectangle ($$$(x_1, (y_1, y_2), +)$$$), add 1 to all the points in the closed interval $$$[y_1, y_2]$$$, otherwise, subtract 1 to those in the closed interval $$$[y_1, y_2]$$$.
4. After each addition or subtraction, find the maximum value among all possible $$$y$$$ which is a candidate to the answer(update the answer).
5. Addition/Subtraction on an interval and querying maximum value can be done with segment tree in $$$O(\lg C)$$$ per operation, where $$$C$$$ is the range of values. If we first normalize all the value $$$y$$$, it can be reduced to $$$O(\lg N)$$$.

After applying Gaussian elimination in O(N³), the determinant of the matrix is equal to the product of all the element on the main diagonal.

J:

1. Enumerate all the possible cycles
2. For a cycle, contract all the vertices into one vertex
3. then, we can calculate the number of spanning tree after contracting with Kirchhoff theorem

The first part can be computed by a O(2^VV²) TSP DP. The overall time complexity is O(2^VV³) since you need to compute at most 2^V times Gaussian elimination.

I didn't really code it. But, I think it works in this way.

For each (position, character) pair, create a n bits bitset and initially set all bit to 1. Let denote it as B(p, c). There are (5 × 75) such many bitsets.

For each string s_i, if p-th character of s_i is c, set i-th bit of B(p, c) as 0.

Then, for i-th string, the possible candidates to pair up is the 1 bits of . One can use _Find_next function to extract each candidate bit one by one.

B: For each added point, consider all the points within the square with length equals to the twice of current answer and centered at this point. Try all the possible triples. There won’t be too many points.

H: dp[i][j]=min length of s_i - 1 when s_i=p[0..j]

My solution seems to work in with arbitrarily number of server.

First binary search the farthest distance d. For a fixed d, I'm going to find the least possible number of servers to cover all vertices within d. Let dp[i] be the critical vertex in the subtree of vertex i, where critical vertex is the deepest one still uncovered, if all the vertice in the subtree of i are covered, the critical vertex is the highest one placed with server.

Then, for each vertex i, collect critical points from its direct children. If the critical point is placed with server but farther than d, skip it. For those uncovered critical points, keep the deepest one. For those with server, keep the highest one. Considering following cases:

• No critical points: If i is root, place a server. Anyway, dp[i] = i
• Exists a critical point with server and no critical points uncovered or all uncovered points can be covered by the highest critical point with server: dp[i] =  the critical point with server.
• Othewise: If i is root or distance between i and an uncovered critical point is exactly d, place a server at i and dp[i] = i. Otherwise, dp[i] =  the deepest uncovered critical point.

Then, I can find the least possible number of servers to cover all vertices within d.

It's somehow greddy and I didn't prove it.

So the intended solution also involves floating-point calculation?

I tried the same idea with rng_58. But, keep receiving WA on test 40. The precision issue when calculating the fractional part is very significant. Is there any good way to deal with it?

A: For each point, the possible center of the donut to contain that point is also a donut. After adding each score to the corresponding region, the answer is the one with maximum score. It's equivalent to add the score to a square with length r and subtract the score to a square with length l.

It can be done with sweep line and segment tree in .

Is there any better solution for F?

Our solution in O(3ⁿ × n²) got TL on the first try. And, finally got an OK with some constant optimization.

Considering a star graph, insert one vertex into each edge.

1 2
2 3
1 4
4 5
1 6
6 7
...

The sum of answer will be O(|V|²)

Is the checker of Limited Moves correct?

I keep receiving Wrong Answer on sample test 2(1024000) during the contest. Now, I test it in the archive and the log prints 499712, 1, 1, 1, ..., 1. Can't I win? or I misread something?

Edit: After removing one of the assert, it got Accepted now. But, I remember that I have tried the same code without assert during the contest.(Annoyed by lots of WA, I kept adding assert to find out the problem) Then, why the verdict is showing Wrong Answer when it went to an assertion failed?

J:

We solve it by Euler's criterion. Pick about K primes, module the given integer and test it with Euler's criterion. The probability of failure will be about 2^- K.

I'm also running topcoder-arena on Archlinux using icedtea-web and facing exactly the same issue today.

I solved it by changing default java environment into jre8. e.g. archlinux-java set java-8-openjdk/jre. Hope this help you.

To clarify, the problem described in the post is actually from a programming contest for high school student in Taipei city in Taiwan not from ACM-ICPC Taiwan regional.

Though some problems from Taiwan regional actually has weak test cases, I'm not sure whether that is a correct example. Some problems uploaded to ACM-ICPC Live Archive has only included sample tests(or some random permutation of it). But, those problems indeed have stronger tests during the official contest. For example, some problems from the daejeon regional in 2016 contains only sample tests.

C can be solved in a more (maybe) straightforward way.

Let dp[i][mask] be the number of way to choose some subset of first i elements and their product has j-th prime with odd degree(if j-th bit of mask is 1). Directly implementing this solution results in a O(N × 2¹⁹) solution which is too slow.

However, for each number x ≤ 70, only 2, 3, 5, 7 can have power more than 1. If we group up all the number whose prime divisor contains 11, we can have a smaller dp state as dp[mask][11?] denoting the parity of current product on 2, 3, 5, 7, 11. After going through all these numbers, we can get rid of everything about 11 and only store the information of dp[mask][0]. Then, considering all the number whose prime divisor contains 13, and so on.

The time complexity is O(N × 2⁵). In this way, we can even solve the problem with different weight on each element(i.e. sum of total weight of choosing a subset whose product is a square number).

How to solve I?

Yes, I did read the constraints til the 4th one(1 ≤ s_a ≤ N, 1 ≤ s_b ≤ N). And, I thought rest of the parts may be something like no self-loop, no multiple edges, etc. as usual graph-related problem.

It looks like a normal graph size(N, M ≤ 10⁵) and 10⁶ ≤ K seems to let the game go into some stable state. Thus, I thought I totally understood the problem and decided to skip it first.

If the graph is some special graph(tree, DAG, functional graph, etc), I thought it would be better to mention it in the description.

Anyway, the contest is still very nice!

For problem L, I only read the description part of the problem. And, I can't believe there are so many ACs on the scoreboard of the online mirror.

After contest, I finally found out the most important key points in the Constraints section...

• For all nodes which has property, .
• For every i from 1 to M, 1 ≤ u_i < v_i ≤ N.

My screencast

Hope you find it interesting!

There's a O(m^2) solution for J without binary search.

http://catalog.lib.kyushu-u.ac.jp/handle/2324/14869/IJFCS-revision.pdf

My screencast

Hope you find it interesting

Same here... But, sadly, I didn't pass D during contest even with FastIO and some optimizations.

Code that got TLE on RCC got AC easily on CF in about 400 ms. Most frustrating is wasting more than one hour trying to make it fit in time limit.

D can be solved in O(1) by case-studying.

During contest, I coded a brute-force method to check all the possible assignment of knights and knaves for k ≤ 10. And, find out the pattern for each pair of

In problem C,

The length of the text is positive and doesn't exceed 100 characters.

Instead of,

The length of the message is positive and doesn't exceed 100 characters.

Thus, the maximum length of message will be 10(username)+1(':')+100(text)=111. Unfortunately, I set the maximum length of char array as 111. Thus, null byte('\x00') will overflow to next row and makes me keep getting WA :(

Does someone face same situation as me?

It's me. :(

The RE is from that if I can't guess out the hidden string, it will trigger an assertion fail.

But, after changing random first guess to fixed first guess, it got AC now. However, I'm still not sure why random first guess will fail to guess the hidden string in 7 queries.

Try this: 4 7

The way you check whether k is a divisor of N! isn't correct.

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

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

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

There will be editorial in Chinese. But, it's not guaranteed to have English version or English version will be posted later.

You can still discuss the problems after contest here.

Same here ._./

But, whether "who is rank k" is solvable with same constraint?

The huge difference doesn't come from I/O.

Actually, time complexity of strlen() is O(n) while size() is O(1).

Thus, time complexity of first one is O(n²) which will definitely get TLE.

Yes, it does exist. A treap with duplication can actually be maintained, but, in a different way.

When merging two normal treap, one will decide which root of sub-treap will be root by their pre-given random value. However, when duplication, the pre-given random value won't be random anymore. Thus, instead of giving a random value at the very beginning, now, we decide which one will be root by their size in this way:

merge(treap a, treap b){
  # if a or b is null, do something first
  ret = random() mod (size(a) + size(b))
  if ret < size(a): # root of a is new root
    a.right_child = merge(a.right_child, b)
    return a
  else: # root of b is new root
    b.left_child = merge(a, b.left_child)
    return b
}

When merging, the probability of choosing the root of each treap is proportional to its whole size. It can be proved that time complexity will also be .

Also, as I mentioned above, LHiC got accepted with this solution at 19527903.(Although, it's just in time.)

I came up with following method during contest:

1. First, we can sort all t-shirts and get the order of them. Then, quality isn't important anymore.
2. Let dp[i][j] denote the number of t-shirt one will buy if he has j dollars and is going to consider i-th t-shirt(in the sorted order).
3. Then, dp[i][j] = dp[i + 1][j] if j < c_i and dp[i][j] = dp[i + 1][j - c_i] + 1 if j ≥ c_i. (Now, c_i is the cost of i-th t-shirt after sorting)

Then, we can maintain the dp value backward. But, maximum j can be 10⁹. Thus, we need some copy-on-write structure.

Considering the transition of dp, for i-th dp value. It's actually the concatenation of [0, c_i) and [0, 10⁹ - c_i] of i + 1-th dp value. Then, we need add more 1 in the range of [c_i, 10⁹](lazy-tag can work).

Thus, it requires a copy-on-write structure which can maintain duplication, move, and range addition. Finally, we can find the answer in dp[1][b_i] by querying the 1st dp value in that structure.

Treap seems to be that required structure. However, I never implemented a copy-on-write treap so far, not to mention a duplication.

Look forward to easier solution!

UPD: It seems that LHiC solved it with this method.

Fortunately, Nope. It got TLE with time complexity O(NM).

However, I still get AC with another O(NM) solution which has less constant.

Submitted at the last minute with this for div1 E...

  for( int i = 0 ; i < q ; i ++ )
    puts( ans[ i ] ? "YES" : "NO" );

It should be "Yes"/"No" instead of "YES"/"NO"....

My rating also got changed( increased about 24 ).

Seems that those getting rating increased in round 305 increased less now, while those getting decreased in round 305 decreased less.

Yes, I also did it. I use something like gradient descent and pass system test.

Repeat following procedure for about 10 times:

1. First, sort all elements by b_i/a_i

2. Repeatly about 10^5 times: randomly swap one from first half and one from second half. Then, sort first half and second half by b_i/a_i again. If the resulting list is better then take it to replace the original one.

I'm also solved nothing, hacked nothing, 2091 -> 2153....

There's even no any submission in my room(in parallel round).

Do someone know when will the online mirror be available? And, also is it actually on here. Thanks!

Yes, you are right.

Maybe there are different solutions to even and odd n.

Is it possible to solve div1A/div2C in this way: Binary search the answer, and check how many points need to be banned by the archer.

I submitted it in the contest but got a WA on pretest. However, it seems that this solution goes well for those countertest given so far.

Here is my code.