What I've learnt from Pinely Round 4

#	User	Rating
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

#	User	Contrib.
1	awoo	161
1	maomao90	161
3	adamant	156
4	maroonrk	153
5	atcoder_official	149
6	-is-this-fft-	148
6	SecondThread	148
8	Petr	147
9	nor	144
9	cry	144

Abstract

After I participated in Pinely Round 4 yesterday, my rating dropped down a lot.

BUT, I learnt something useful.

1. Check your initialization — AND Reconstruction

After I solved A in a minute and saw the statement of B, I quickly realized that there's an efficient construction which is simply set $$$a_i=b_i|b_{i-1}$$$. The code is below.

code

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], b[N];
void run()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        scanf("%d", b + i);
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] = (b[i] | b[i - 1]);
    }
    for (int i = 1; i < n; i++)
    {
        // printf("%d %d\n", (a[i] & a[i + 1]), b[i]);
        if ((a[i] & a[i + 1]) != b[i])
            return puts("-1"), void();
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d%c", a[i], " \n"[i == n]);
    }
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

Can you recognize what's wrong with the code?

answer

2. It's never guaranteed that former problems are easier than others — Absolute Zero

$$$40$$$ minutes after I submitted the second wrong submission of B, I gave up and came to check C.

And, literally the moment I understood the problem statement, I came up with an efficient solution.

In each of the $$$k$$$ operations, sort $$$a$$$, then set $$$x=\lceil a_1+a_n\rceil$$$. If the legal operation sequence exists, my method always reduce $$$\max(a)-\min(a)$$$ for a half.

So I quickly implemented my method successfully, and got accepted. However, it was already an hour from the beginning, so I lost a lot of points.

3. Think about the probability that you're rickrolled by the problem when you struggled solving it — Prime XOR Coloring

From I solved C to the end of the contest, I struggled solving D because I believed that it was easier to solve D than to solve B (because I didn't find that silly bug). I tried to find a pattern what a legal construction has, but I failed. Because I tried to make every color as small as possible.

However, I forgot that it's not necessary to make every color the smallest. Making the number of colors smallest is enough. And in the editorial, the proposer told us, "Why not try to make all $$$\operatorname{xor}$$$ values of the positions with same color an composite number?"

In fact, the sample given in the problem statements is already a hint. It hints us to think about $$$4$$$. As we know, $$$(4)_{10}=(100)_2$$$. There's only one $$$1$$$ in its binary expression. If we make sure that $$$2$$$ lowest bits of two different positions with a same color are always the same, then their $$$\operatorname{xor}$$$ value is always divisible by $$$4$$$, which is a composite number.

Then, for $$$n\ge 6$$$, we can simply set $$$c_i=i\bmod 4+1$$$.

What a rickrolling problem, but I like it!

4. Maybe the answer resides in the boundary condition — Coloring Game

Since I spent all the rest of the time solving D, I only took a look at E and had no idea.

The statement says Alice chooses two different colors each time. So, in order to decrease the probability of Bob winning, she can only choose two colors all the time.

And in this worst case, Bob is possible to win only when the graph is a bipartite graph, which is able to be colored by only two colors.

So the instruction to win is obvious. If the graph is a bipartite graph, choose Bob, since he can always win with at least $$$2$$$ colors. Otherwise, choose Alice, since only a bipartite graph can be colored by only two colors, and it's impossible for Bob to find a legal coloring.

5. Range queries may not lead to a range data structure such as Segment Tree — Triangle Formation

When I took my first look at this problem, I thought about segment tree. However, it's unnecessary in this problem because the densiest sequence ("densiest" means the smallest maximum value) with no non-degenerate triangle formable is the fibonacci sequence. If you do a simple implementation, you'll discover that the $$$45$$$-th term of that sequence already exceeds $$$10^9$$$. So, under the constraint, a subsequence of $$$a$$$ with a size not less than $$$45$$$ always generates a non-degenerate triangle.

But the problem asks us to make $$$2$$$ non-degenerate triangle. How can we do that? In fact, we can simply add $$$3$$$ more numbers into that sequence. because after we extract one of the non-degenerate triangles, there are still $$$45$$$ elements in it, we can still extract another one.

For those subsequences with less than $$$45$$$ elements? Well, since it's obviously easier to get a non-degenerate triangle with closer elements if we sort that sequence, we can forcefully search all the possible combinations in subintervals in the sorted subsequence with a size of $$$6$$$, or all the consecutive subintervals with no intersections and a size of $$$3$$$.

But, if you do that without optimizations, you will get a TLE.

So how to optimize?

Add break to your code, as many as you can.