Yes, my team, JAW, with wangyenjen, nonamefour0210 and me, will go to World Finals.

I have heard of three cases of wrong test data:

1. Clerical errors (e.g. test data is empty or of wrong problem)
2. Wrong intended solutions

3. Wrong checkers accepting everything

   In the specific cases I know, (a) we didn't submit in time and no other teams even attempted it, or (b) everyone should get WA but got AC instead and the winner is unaffected (in this contest only winner matters)

   This should not appear in a perfect contest. Fortunately, it did not caused controversies.

I have heard of two cases of wrong intended solutions, too:

1. Ones that produce wrong test data

2. Ones that produce correct test data, but fails on some untested cases

   In the specific case I know, in-contest my teammate asked me if a solution make sense and I told them no. Later I told my teammates to try it anyway because so many teams solved it that it must be the intended one. Turns out problem setter generated the test data with a memory-heavy but correct algorithm, testing a lighter algorithm against the data, and thought the lighter one is correct.

   BTW some teams did solve it with truly correct algorithm that fit in memory limit.

   This should not appear in a perfect contest either. But hey! It's definitely a less severe issue. If we don't know the intended solution, we probably just thought the tests are weak.

Our team loses (to other NTU-tw teams) on penalty with easier problem set but wins on solves with harder problem set.

World Finals, Yokohama (Japan) site and NTU-tw internal contests are considered hard. Taipei (Taiwan) site and most other sites is considered easy. Therefore,

• We won the contest deciding foreign site for each NTU-tw team. Winner choose first and we chose Yokohama.
• We lost an easy local contest. We had a last-minute submission on L. Post-contest analysis of the source code shown that we just had one bug that I've already spotted but my teammate assured me it's correct. I didn't put on much thought as we were under severe time pressure.
• We lost the Taipei regional with 620 minutes more penalty. Our opponent's last solve is at 163 minutes.
• We did not win the Yokohama regional but we had a ticket. One can still consider it a win if you remove Chinese teams and medal schools, which have no effects on tickets.
• We won the contest supposedly deciding which NTU-tw team go to World Finals. We had a ticket last year and won the 2017 one too, but coach sent another team instead. Therefore we were somewhat confident we'll be sent regardless of the outcome of this contest.

Yangon 2018: the intended solution of F is wrong. Mid-contest, the problem is changed to match the intended solution. Moreover, problem H ask you to compute MD5. Beat that.

• The "unknown X and Y" problems were real in PSP, but no longer applies as the rule has changed (to what I mentioned).
• I didn't see the "implicit votes" in the blog. Has it been edited? The vote result is the same anyway.
• I do agree some regionals are awful. Here is a ridiculous problem from Yangon 2018 which asks you to compute MD5. It did not even tell you how MD5 is computed.
• What a wonderful world we have if corruption/incompetence can be cured with rules.

In which sense Asia (especially the PSP subregion) rules are shit?

PSP Rule (since 2016-2017 season)

For those who don't know: Each site has a site score (according to the number of schools/teams attending the site; formula is published beforehand) and each team can attend at most 2 sites.

For each site, remove medal schools, remove Chinese teams and keep only top team for each school. Each remaining team got a priority: (rank - 1) / (site score).

The teams with lowest priorities (over all sites) are qualified. (Keep adding teams until there are enough schools.) This is the published list in C. J. Hwang's blog. If multiple teams from one school qualify, coach decide (as only one team from each school can attend World Finals).

Factors on Choosing Site

• The problem style and contest quality of each site differs vastly.
• You can afford second (and maybe third) place in sites with higher scores, but you must get the first in sites with lower scores. However, as sites with lower scores are less appealing, it may be easier to get first (such as Manila 2016).
• Most teams compete in their local site. Therefore you may want to avoid sites with strong local schools (such as KAIST, National Taiwan University and National University of Singapore). You don't need to avoid if they had a medal, though (such as University of Tokyo and Seoul National University in 2018-2019).

Upcoming Changes

PSP Finals is proposed for 2019: regionals qualifies for this semifinal, and this semifinal qualifies for World Finals.

It's in the first link of this article.

My Solution to Problem A:

Let f_t(l, y) be the position of nearest store of type t to location l in year y. The problem is equivalent to computing:

Let n_t be the number of stores of type t. Clearly, [1, 10⁸] × [1, 10⁸] can be partitioned to ( ≤ 5n_t) f_t-monochromatic rectangles. Therefore, our problem can be reduce to "given  ≤ 5n labeled rectangles; for query (l, y), find the maximum (and minimum) label among all rectangles containing point (l, y)."

Obviously there is a two-dimensional data structure to do that. With fractional cascading, it can be reduced to . (Previous revisions were wrong.)

Edit: Now I realize that for every rectangle [l₁, l₂) × [y₁, y₂) labeled x, we have the property . Therefore, we can partition each rectangle to two, with the property . Now the data structure can be implemented in or with fractional cascading.

It took me more than a hundred lines:

https://gist.github.com/johnchen902/44d9c5be53154aec4acf685c41c88a81

Better ask tourist directly for the reason.

Anyway, I'd still post the comment as long as most of the world didn't know about this solution.

I have an easy solution to E in O(n²) with a sufficiently small constant, without using NTT, unlike 998244353 suggested. (p.s. I didn't bothered to check other solutions. It appears that first solvers have the same solution.)

int solve(int x, int y) {
    dp[0] = 1;
    for (int i = 1; i <= x; i++)
        for (int j = 1; j <= y; j++)
            dp[j] = (dp[j] + (long) i * dp[j - 1]) % mod;
    int ans = 0;
    for (int i = 0; i <= y; i++)
        ans = (ans + (long) dp[i] * inv[x + i]) % mod;
    return (long) ans * fac[x] % mod * fac[x] % mod * fac[y] % mod * fac[x + y] % mod;
}

We first observe that any valid swap is either:

1. Swapping a (0, 1) with a (1, 0) (swapping a_i, a_j s.t. (a_i, b_i) = (0, 1), (a_j, b_j) = (1, 0))
2. Swapping a (0, 1) with a (1, 1)
3. Swapping a (1, 1) with a (1, 1)

Let x be the number of (0, 1) and y be the number of (1, 1). Clearly the number of type 1 swaps is x, and the number of type 2 or 3 swaps is y. As type 3 swaps do not interfere with other types, we assume there are y - i of them, multiply the answer by , and forget their existence.

Now we're left with x of (0, 1), i of (1, 1), and only type 1 or 2 swaps. Let g(x, i) be the number of possible swap sequences. Clearly,

Let g(x, i) = (x!)²(i!)f(x, i). Then clearly,

And for the final answer, we must sum over 0 ≤ i ≤ y, i.e.

Of course.

something / (costH2O + costO2 * 2.0)

Judge's solution is incorrect.

I challenged someone computing costH2O + costO2 * 2 in int with 300000000, 0, 1000000000, 1000000000, and the result is

Your challenge of awata was unsuccessful. The method returned -0.231666082168 as expected.

I happened to have discussed with darry140 about problem F beforehand, and he came up with an O(NlogNlogC + QlogN) solution, though I never implemented it.

http://tioj.infor.org/problems/1905 (Chinese)

Unfortunately coding complexity exceeded for me.

Same here. !@@#$%^&*()*&^%#@!#%^&

That page mentioned an O(n) space and method.

Theorem 1 Let A, B be any multiset. .

Proof Trivial

Now assume we have an array A of size n. Split it into blocks, each of which sized . Precompute the mode and frequency of each consecutive blocks. It took O(n) space and time.

For each query, we have a prefix, a span and a suffix. By Theorem 1, the mode must be the mode of the span, an element of the prefix, or an element of the suffix. For each element in the prefix or the suffix, check if it is more frequent than the current mode. With additional preprocessing and analysis, per query can be achieved.

You can refer to the original page for more detail if you can't figure out yourself.

There is an entry on Wikipedia: Range Mode Query.

It's for others to compete for the second place of course.

And 245205 too.

But you cannot vote for your comments.

Got "unexpected verdict" in hack 245453, 245473 and 245477.

I'd like to explain my solution of F.

1. Sort all t-shirts by decreasing quality then increasing price.
2. Sort all customers by their budgets.
3. For each t-shirts T, find the next t-shirt one may afford if they cannot afford T, call it fail[T].
4. Call go(all customers, all t-shirts, 0, 0).
5. Print answer.

And go(customers, tShirts, ans, spent) does the following things:

1. If customers is empty, return now.
2. If tShirts is empty, set the answer of all customers to ans and return.
3. Let C1 be the customers that can afford spent + cost of tShirts[0] and C2 be the remainding ones.
4. Call go(C1, tShirts[1]..., ans + 1, spent + cost of tShirts[0]).
5. Call go(C2, fail[tShirts[0]]..., ans, spent).

EDIT: It's hacked.

Note that if there are r rows without rook and c columns without rook, there would be exactly r × c cells not under attack.

You have to remember the largest S_i in each block.

For a partial block update, you can just spent .

For a full block update, you have to answer y = max_i(S_i + ix) over i for some x. See http://wcipeg.com/wiki/Convex_hull_trick#The_technique if you don't know how to do that.

It is not true that . Counter example: n = 3.

Compiling with g++ -g -fsanitize=address -fsanitize=undefined and executing with n = 3 input gives this message:

==23853==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000f000 at pc 0x000000401cf2 bp 0x7ffc7c7f9e70 sp 0x7ffc7c7f9e60
READ of size 8 at 0x60200000f000 thread T0
    #0 0x401cf1 in initialise() /tmp/A.cpp:99
    #1 0x401ea7 in main /tmp/A.cpp:113
    #2 0x7f4a48751740 in __libc_start_main (/usr/lib/libc.so.6+0x20740)
    #3 0x4011f8 in _start (/tmp/A+0x4011f8)
... (truncated)

Line 99 is bsum[(int)i/rootn]+=arr[j];. As n = 3, rootn = 1 and sz = bsum.size() = 2, when i reach n - 1, bsum[(int)i/rootn] will be out of bounds, causing undefined behavior.

Unfortunately even if you fix this bug you will still get TLE.

Didn't actually check your code, but I guess you wrote A?B:(C&&D) instead of (A&&B)||(C&&D) while B, C, D is compute only when needed.

Upvoted for yutaka1999!

It was not about floating point issues but unnecessary eps. In your case, your solution failed because of the minus 1e-9, which is too large. It should be smaller than 1.25e-11 to get pass test 37. In fact, you didn't need to minus anything, just like:

printf("%d\n", (int) ceil(hypot(x1 - x2, y1 - y2) / (2 * r)));

By the way, the toughest case I've found requires your eps to be smaller than 6.28009e-012:

141081 99263 99774 -100000 -100000

I guess dist-=1e-12; of problem B.

I've hacked two people whose eps is larger than 1.25e-11 with this test case:

100000 100000 1 -100000 0

which became the case 37 in system test.

My virtual participation has ended but I still want to make more submissions. What can I do?

Thank you for pointing it out!

In this particular problem sqrt-decomposition means splitting all queries into blocks of sqrt(n), and shrinking the tree to only contain interesting vertices for each block of queries.

I finally understand why sqrt-decomposition works in this problem.

I hope these mess won't happen in the Warm up round (the one hosted on Codeforces). I don't like unrated rounds.

A friend of mine (qazwsxedcrfvtg14) only use a file named lkk.cpp. Whenever he is solving a new problem, he clear the content of that file and reuse it!

I prefer using only one loop. I think its more beautiful.

for(int i = 0, j = m - 1; i < n && j >= 0;) {
    if(a[i] + b[j] > x) {
        j--;
    } else if(a[i] + b[j] < x) {
        i++;
    } else {
        printf("%d + %d = %d\n", a[i], b[j], x);
        i++; j--;
    }
}

The idea is as same as the other people's.

I fell in that trick, too. I've thought of the answer==2 case but forgot to put it in my code until it was too late.

Oops. My comment did not match my intent. I would write auto instead of ???, too. I meant you need not to write

auto mapa = map<that_is<really, long, type>, std::vector<pair<tuple<int, int, int>, string>>>();

as what OP did.

Your post is good, but I would like to give some suggestions.

First, why you ever need an auto in the declaration of a variable? I meant, sometimes it would be shorter without auto.

map<string, pair<int, int>> itCanBeEvenShorter; /* pure C++98 way on this line */
array<int, 10> arr {5, 8, 1, 9, 0, 3, 4, 2, 7, 6};

Second, your iterator is not quite standard conforming. Read §24.2 [iterator.requirements] of the C++11 specification or this for detail, and Boost's Counting Iterator for a standard-conforming implementation. To make my third point compile on my machine, you need to make your iterator default-constructable.

	number_iterator(T _v = 0) : v(_v) {}

Third, lower_bound should not be used like this, when there is a good partition_point:

int findSqrt(int n) {
	int lb = partition_point(number_iterator<int>(0), number_iterator<int>(n),
		[&] (int value) { return value * value <= n; });
	return lb - 1;
}

May fast AC be with you.

I am motivated. I was in a neutral emotion when writing the comment. I just didn't notice my comment looks sad.

Anyway, see you next year!

This is my rough idea:

1. Cat three strings together (e.g. abc$bc%cbc) and compute its SA and LCP:
2. Traverse through the SA. Assume the current string is C. For each of the three strings S and each (necessary) length L, maintain the number of suffix T of S that is already seen such that C[1...L]==T[1...L].

This is my actual code: 7273217. The numbers I maintained is put in stack<T> st;. I (unnecessarily) used binary index tree for range-modification.

As someone who only got silver in this IOI, I agree with you. Though silver may be good enough for some contestants, it is not satisfying for me. I've blamed myself for not practicing enough, and I'll definitely solve more problems to prepare for the next IOI.

Also the task Friends, I'd gotten most of the clue needed to solve the problem, but when the time was getting less, I became panic and started writing random codes -- of course that failed and I lost the chance.

I thought in 374C - Inna and Dima recursion will cause stack overflow and I used my own stack. However, after the contest I found solutions on the top of standings simply use recursion. I copied those code and tested. Those code did RE on my windows 7, but they didn't in the "Custom test" in Codeforces. Why? This is my input generator:

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int size = 499; // or 999
char str[size][size+1];
const char *dima = "DIMA";
int main(){
    freopen("cout.txt", "w", stdout);
    cout << size << " " << size << endl;
    for(int i = 0; i < size; i++){
        fill(str[i], str[i] + size, '?');
        str[i][size] = '\0';
    }
    int k = 0;
    for(int i = 0; i < size / 2; i += 2){
        for(int j = max(i - 1, 0); j < size - i; j++)
            str[i][j] = str[i+1][j] = dima[k++ % 4];
        for(int j = i + 1; j < size - i; j++)
            str[j][size - i - 1] = str[j][size - i - 2] = dima[k++ % 4];
        for(int j = size - i - 2; j >= i; j--)
            str[size - i - 1][j] = str[size - i - 2][j] = dima[k++ % 4];
        for(int j = size - i - 2; j >= i + 2; j--)
            str[j][i] = str[j][i+1] = dima[k++ % 4];
    }
    for(int i = 0; i < size; i++)
        cout << str[i] << endl;
}

Yeah, A is easy, but I didn't think carefully. After I saw "pretest past" I moved to the next problem. When the test was about to end, I was hacked and I instantly found the bug, but that was too late...

It's just a test~~~~

Codeforces is a test for me, too~~~~