Codeforces Round #698 Div2 Summary - Construction Problems

All construction problems. The construction problems test the thinking ability and IQ the most. But the problem is that I'm not good at both of it. I'm 蒟蒻.

Ugh. Question D number theory can't do it. Question F can even be failed in a two-way linked list... I feel that my thinking ability is indeed not able to keep up.

A. Nezzar and Colorful Balls

Solution

Just count the number with the most occurrences.

Code

B. Nezzar and Lucky Number

Interesting construction problem. Get 1 TLE because of typo error.

Also checked official solution. But not very clear about it. Personally think my solution is more simple and clear. But anyway, it's problem B, there can be lots of different solutions. Nothing special.

Codeforces Round #698 Nezzar and Lucky Number - Search by brute force

Let current query is x, let remian=x mod d. If x>=10d}+remain. Then there must be a solution for x.

xloypaypa's Blogxloypaypa

C. Nezzar and Symmetric Array

Not note requires int64 for the input. Get one RE.

Also refer to the description of problem. $a$ should include distinct integers. I forgot this one once. Get WA7 for this.

Codeforces Round #698 Nezzar and Symmetric Array - Construction

First let’s choose any two numbers, $a_i$ and $a_j$. So There must be $-a_i$ and $-a_j$ in $a$. And so there is no need to consider the symbol. Let’s assume $a_i>0,\ a_j>0$.

xloypaypa's Blogxloypaypa

D. Nezzar and Board

Number theory. Bézout's lemma. Don't know this one.

E. Nezzar and Binary String

Still can handle segment tree very smoothly. Want start with $s$ first. But it's too complex to do. So turn to start from $f$. Then it much easier to solve.

Codeforces Round #698 Nezzar and Binary String - Segment tree

Of course a segment tree problem.Let’s start from $f$. Then actually, the state of last day is fixed. Also fixed for the day before last day. The only thing we need to know is how many zeros between $l$ to $r$. Then we can know what is changed.

xloypaypa's Blogxloypaypa

F. Nezzar and Nice Beatmap

I'm too stupid to implement two-way linked list correctly. T7 and WA7 because of it. I realize this until I add a exception below:

int ans = n;
Point now = last;
while (now != null) {
    now.ans = ans;
    ans--;
    now = now.pre;
}
//check if the two-way linked list is broken.
if (ans != 0) throw new RuntimeException();

Codeforces Round #698 Nezzar and Nice Beatmap - Computational geometry

SolutionLet’s consider three points first. three point can build a triangle. So at most 1 angle equal or more than $90^\circ$.

xloypaypa's Blogxloypaypa