Hello,

The problem set in Yokohama regional 2023 is now available in Gym. Please enjoy. https://mirror.codeforces.com/gym/104832

The ICPC 2023 Yokohama regional contest is scheduled to take place on November 26 from 09:30 to 14:30 (JST, UTC+9).

An online open contest is also planned on Aizu Online Judge, with delay of 30 minutes. I will update this post with the exact timing once it is confirmed, but for reliable information, please refer to the official site.

• Official site of Yokohama regional contest
• Aizu Online Judge Open Contest Page

I hope you thoroughly enjoy the contest!

(Disclaimer: I am not responsible for organizing the open contest. In the event of any issues, there may be a postponement of the contest.)

Update: Open contest page is now available. It will start with 30 minutes delay.

Update2: The problem set is available in Codeforces Gym.

General

It was normal codeforces contest except the IO: input.txt/output.txt. I didn't know the IO change before contest began and I got upset. I used an unaccustomed fstream library in the contest, but I should use freopen as below code. (if C++)

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

A Extra-terrestrial Intelligence

Simple problem, calculate the interval length between first two '1's, then check if all interval lenghs are equal.
I failed to read the statement "It’s guaranteed that the given record sequence contains at least three 1s" at the beginning, then I stopped for a little.

B Fractal

This is also a simple problem, simple iteration is good because the input size is very small.
But I stuck at compilation error of vector<string> substitution, then I lost about 10 mins. This upset me. My C++ compiler MinGW outputs compilation error at below code. I don't know what is wrong yet..

        vector<string> vs1(N,string(N,'^'));
        vector<string> vs2(2*N,string(2*N,'^'));
        vs1=vs2;

C Bowls

Difficult geometry. Many branching are required and my submission failed in the contest.
When a bowl A is put on a bowl B, the contact point with A,B will be one of below situations.

So when we simulate putting a bowl A, calculate the height of putting on bowl B foreach 0<=B<=A-1, then take maximum height as a bowl A position.
To find the contact point, I first wrote binary search method instead because branching was laborious. But it was hacked quickly. (perhaps TLE or WA.)

Be aware that input size N is a bit large to run O(N^2) in 2000 msec limit, heavy calculation must be reduced.
Line struct class as below was bad thing because method push_back will consume much time.

    struct Line : public vector<P> {
        Line(const P &a, const P &b) { push_back(a); push_back(b); }
    };

(I think the input size 3000 was a bad thing because the code which is only a little heavy may got TLE.
In Codeforces, TLE may not detect at pretest that contains only easy tests, and we cannot test the worst case in judge server environment, so we can't check if the code will get TLE or not.
If O(N^2) algorithm is simply required, N<=1000 would be good.. wouldn't it?)

D New Game with a Chess Piece

I didn't read in the contest.
This problem looks like Nim, though the rule removing stones is different from Nim. Actually, this problem is not so hard if we experiment with small input size like 1<=N,M<=50.
The answer has a relatively comprehensible rule with N,M,K, so we can construct O(1) algorithm. The solution will be simply an enumeration of mathematical expression.
I thought D is easier than C, though two problems are in different category.

E Two paths

I don't read yet.

Result

ooxxx 1332pts 97th
1885->1814

Bad result. I'm shocked at C because I solved many geometry problems before and had a little self-confidence with geometry.
If a geometry problem is given next time again, I need to solve it.

I would like to write participation commentaries of Beta Round #33. I'm sorry my English may be poor.

A What is for dinner?

The problem is quite easy, but the problem statement is a little hard so I got as many as 2WAs. This made me upset a little.

B String Problem

This problem is also easy if we know warshll-floyd algorithm. But I confused the specification. I translated the statement "According to the game rules, with each move Valera can change one arbitrary character A_i in one of the strings into arbitrary character B_i..." as "each string can be moved at most one time" by mistake, and I spend much time in wrong and heavy coding, then I got 1WA.

C Wonderful Randomized Sum

Simple DP Problem. Let dp[n]:=(maximum sum using only "prefix multiplication" operation if an input sequence is a[1],a[2],...,a[n]). Each dp[n] can be calculated by as follow.

    dp[0]=0;
    ll mm=-1LL<<50;
    FOREQ(j,1,N) {
        mm=max(mm,-2*sum[j]);  //sum[j] is a sum of a[1],...,a[j]
        dp[j]=sum[j]+mm;
    }

And let dp2[n]:=(maximum sum using only "suffix multiplication" operation if an input is a[n],a[n+1],...,a[N]). This is also calculated as same as dp[n].
Then the final answer is max_{n} (dp[n]+dp2[n]).

D Knights

Interesting problem about geometry and graph. Query number k is large, so a program must calculate each query as fast as possible. Or, it is also good to calculate all possible M^2 queries in advance.
A way I tried was the latter tactics. First of all, I constructed a graph with M vertices. In the graph, there would exist an edge between node i and node j, if a fence i contains a fence j strictly. "a fence i contains a fence j strictly" means that there is no fence between the fence i and the fence j.
Construcing such a graph in O(M^2) is not so plain, but it can be done as follow: 1. sort all fences by their radius 2. see each fence from smaller one, then check if the fence contains the other fence strictly. Because it can be said that every fence will be contained by at most one the other fence, we need to check only fences that is not contained by any fence.
It would help implementation to add an "outer envelope" fence as a sentinel value like R=1e14, P=(0,0) , because: 1. adding it will not change any result 2. by adding it any control point will be contained in exactly one fence strictly.


After constructing the graph, we will calculate distance[i][j] for each pair (i,j). This can be done by some depth-first-search approach, starting from top node(outer envelope).


Implementation of above algorithm was laboring and I took much time. I finally got AC with 1 resubmission.


After contest I read some solution of other people, and following method looked quite good.
For each query, we can also calculate the answer by counting the number of fences that enclose only i or j. (i,j is an index of a control point)
If we use this method, the time complexity will be O(10^5*10^3)=O(10^9) and we would got TLE.
But if we calculate this not by bool[] one by one, but each bit of unsigned long long, it will be O(10^9/64) ~ O(1,562,500), then the method will be good for the time limit. I think this method is comprehensible and clever.

E Helper

I didn't read the statement yet.

Result

oooox +3442pts 62nd place