Fixed, thanks.

As the "MVP", I want to copy Error_Yuan's words: Nice problems, recommend to participate :)

Thankfully the div1 part was accidentally cancelled. I can't imagine how crazy I would be if this round is rated!!! It felt really annoying when finding that the first four problems are all mathy and problem D took me more than half an hour!!!

Fun fact:

PS: It's three minutes before the contest starts.

You can find three more red ones on the line "helping with preparation on Polygon (including testing)" :)

As the only "LGM" "writer" of this "specialist round" (though I proposed no problems actually), I wish you good luck, positive delta and a happy new year! (I believe an lgm may make the round look better :)

Here's an online method (mainly about the (2) part in your idea):

Let's consider $$$w(i,j)$$$: the number of not-covered edges on the path between node $$$i$$$ and the $$$2^j$$$-th ancestor of node $$$i$$$. $$$F(path)$$$ represents the number of not-covered edges on a path. It can be seen that $$$F(path)$$$ can be divided into sums of $$$O(\log n)$$$ different $$$w(i,j)$$$, and for each $$$j \gt 1$$$, $$$w(i,j)$$$ can be divided into sum of two $$$w(x,j-1)$$$. We want to know all the paths $$$x$$$ that $$$F(x)$$$ becomes $$$0$$$ after this update.

$$$F(x)$$$ becomes $$$0$$$ if and only if the $$$w(i,j)$$$ it is divided into are all $$$0$$$. After we cover an edge ($$$x,fa_x$$$), first $$$w(x,0)$$$ becomes $$$0$$$, then it will affect some $$$w(y,1)$$$, and then $$$w(y,2)\dots$$$. However, it is meaningful to update the upper $$$w(x,y)$$$ values if only $$$w(i,j)$$$ becomes $$$0$$$. Thus there're only $$$O(n\log n)$$$ updates(Let $$$S_{x,y}$$$ represent the set of pairs $$$(i,j)$$$ that $$$w(i,j)$$$ can be divided into $$$w(x,y)$$$ and something else. When $$$w(x,y)=0$$$, do update on all elements in $$$S_{x,y}$$$). Then we can know all the paths that its weight will become 0 after the update.

It seems a bit difficult to implement, so I didn't do that. I took the idea from NOI2024 D1T3, that is really similar and much more difficult, you can refer to this for further details.

Btw, this solution can solve the problem that the $$$n$$$ paths are not $$$(i,(i\bmod n)+1)$$$, but can be the $$$m$$$ given special paths, online.

There should be a definition for this at the beginning of the code.

#define cntbit(x)   __buitin_popcount(x)

It means the number of 1 bits in a number's binary form. For example, cntbit(10)=__builtin_popcount(10)=2, because $$$10_{10}=1010_2$$$

Really sorry for that, it should be a typo: should be $$$(|Q|-1)k\ge \max-\min$$$.

But I thought a while for the mistaken one: let $$$n=|Q|,d=\gcd$$$, then consider $$$nk \lt (n-1)d+1$$$, $$$n \gt \frac{d-1}{d-k}$$$. Let's take sth $$$B=\sqrt V$$$. Consider $$$\frac{d-1}{d-k}\le B$$$: the lower range for n is not high, so brute force it; otherwise, $$$d-k$$$ is not large, so brute force it. I can only solve it in $$$O(n\sqrt V\log)$$$ (or maybe $$$O(n\sqrt V\log^2)$$$ ?). There also seem to be something $$$O(V\log^{sth})$$$, but neither can fit the original constraints. Maybe it can be a not bad problem that $$$n,V\le10^5$$$. Anyway super sorry for the inconvenience ):

There're only $$$n\log V$$$ possible $$$\gcd$$$ over all $$$[l,r]$$$. Go over all the $$$\gcd$$$ from small to large, maintain the array $$$b_i=x$$$: the maximum $$$x$$$ that $$$\gcd_{i\dots x}\ge g$$$, where $$$g$$$ is the current gcd. There're only $$$n\log V$$$ updates. Use range sum queries to answer the queries.

In your previous submission, you forgot the following case: If there's only one question mark at the position of the root, you code processes the second step (made by Dora) even if it doesn't exist.

1
2 1
1 2
?1

correct: 1

The first one to color the root or the leaf has disadvantage, so everyone tries to color the unimportant nodes first. So the process is: Iris sets $$$s_3=0/1$$$, Dora sets $$$s_1=0/1$$$, Iris sets $$$s_4=1-s_1$$$, Dora sets $$$s_5=s_1$$$, Iris sets $$$s_6=1-s_1$$$.

We need to maintain all the $$$cnt(1,i)$$$ and $$$cnt(\frac{k}{i+1}+1,k)$$$ stuff, $$$2\sqrt k$$$ elements in total, for each query. Using Mo's algorithm, after moving one of the pointers, you can only maintain the number of $$$x$$$ that $$$x=i$$$ or $$$\frac{k}{i+1} \lt x\le \frac{k}{i}$$$ in the range. When you solve a query, use prefix sums to find the $$$2\sqrt k$$$ elements.

Refer to this. Actually I'm not good at explaining things clearly, sorry for that.

$$$d$$$ should be the tolerance.

About the gcd thing, you can consider merging two adjacent tolerances together: $$$a,b$$$ becomes $$$a,\frac{b-a}{2},\frac{a+b}{2}$$$. Ignore the $$$\frac 12$$$ stuff, and it's just the same reason as $$$\gcd(a,b)=\gcd(a,b-a)$$$. The whole process is similar to this.

Sorry, that's my fault. Updated.

About the second question, I forgot that you should checkmin the two cnt values with $$$\lfloor\frac n2\rfloor$$$. It only goes wrong when $$$n$$$ is odd, $$$cnt(1,i)=\frac{n-1}2$$$, $$$cnt(\frac{k}{i+1}+1,k)=\frac{n+1}2$$$.

Read Hint 1. As it is mentioned, if you add $$$a$$$ or $$$b$$$ to all the elements except $$$c_i$$$, it is the same as decreasing $$$a$$$ or $$$b$$$ from $$$c_i$$$. So it doesn't matter if $$$X,Y$$$ are negative.

Congratulations for tourist for reaching $$$4000$$$ rating, which is the highest rating on Codeforces ever! I'm proud to see that in my contest!

Now everybody knows you have a girlfriend/tuu

Shit problem G

Why is the title of problem C "Maximize the Last Element"? Shouldn't it be "Absolute Zero"?

UPD: Changed.

Few samples for harder problems!

Problem E has only two samples with $$$n=m$$$, so when I made a mistake in my code(it plays $$$m$$$ rounds instead of $$$n$$$), it passed the samples and got wrong answer on test $$$2$$$! Spent two minutes staring it out.

Problem F,G both have only one sample??

For problem F, here's one similar problem (similar trick) on luogu, and it's in one of the recent contests.

The first one to pass problem E~

Also my first time to be the first to pass a problem on Codeforces! Happy~

Why the sooooooo tight memory limit in problem G? I didn't see any reason to reject solutions on the memory constant factor!! Or do you really have a meaningful $$$O(n)$$$ memory solution? Anyway, if an acceptable solution uses $$$1\cdot n\log n$$$ memory, why to reject $$$2\cdot n\log n$$$?

Our div1 proposal(1635) was submitted in August 2023, but hasn’t got reviewed yet. I’m just wondering why. We’ve already waited for eight months!

Update in Jun2024: Finally a coordinator after over 10 months' waiting!!!

It seems that G is a little too easy for the position? I personally consider F more difficult than G.

I guess the authors like constructive problems veeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeery much!!!

Fast editorial, and...

using namespace atcoder; is found in problem 1E !

That's it! (I didn't realize we needn't do the 2nd operation twice in the contest QWQ)

When we perform the 2nd operation only once, we can consider on the reversed string. We can try all positions for the highest bit, and binary search on the final length of the string ignoring leading zeroes.

If the positions of the highest bit and the lowest bit are determined, the greedy solution is to put all 1 outside to the last few 0s in the interval, so the prefix of some length doesn't change. So we can use hash or suffix array to compare the prefixes, and then the best starting position can be determined.

Nice problem F! Thanks!

I'm just curious. To solve G, I have worked out the cases when n is even. But when n is odd, I have completely no idea.

I wonder if we randomly choose numbers from {-3,-2,-1,1,2,3}, is is possible to "random" out a possible permutation?

What the hell with E?? Seven very similar submissions, five of them TLE on test 7??? Moving the array from inside the function to the outside gets AC???

What's the intended solution by the way? Only have $$$O(\frac {\sum n}n\cdot n^4\log n)$$$ solution.

-update: I actually know the solution for $$$n \gt =20$$$, but am seeking for a quicker solution for $$$n \lt 20$$$.

Seems like the trick in F has appeared quite a lot times recently, e.g. abc308g and 1851F. So it may seem more solvable for me than E...

My binary search is similar. I do binary search on the answer (that is $$$l+1$$$, but call it $$$ans$$$), and check if it is deleted from $$$a_n$$$ to $$$a_1$$$.

Suppose the number deleted by $$$a_i$$$ in the $$$j$$$-th round is $$$x$$$. Since in this round i numbers $$$\le x$$$ are deleted, the number deleted by $$$a_i$$$ in the $$$(j+1)$$$-th round should be the $$$i$$$-th undeleted number after $$$x$$$. The numbers deleted this time which are greater than $$$x$$$ must be deleted by $$$a_{l \gt i}$$$, so do it from $$$a_n$$$ to $$$a_1$$$.

Suppose $$$y$$$ numbers smaller than $$$ans+1$$$ are deleted by $$$a_{n},a_{n-1},\dots,a_{i+1}$$$, there're now $$$ans-a_i+1-y$$$ numbers not deleted in $$$[a_i,x]$$$. Since it goes $$$i$$$ steps each time, the answer for $$$a_i$$$ is $$$\lceil\frac{ans-a_i+1-y}i\rceil$$$.

Just sum them up and check if the value is $$$\le ans-1$$$. If so, the real answer should be less or equal to the current. The time complexity is $$$O(n\log \text{ANS})$$$

Interesting Problems and quick editorials :3

I like problems 1A 1C very much, but have not enough time for 1D...

Also, isn't 1A too difficult for this place?

Saw expectation problem in the position of D and got afraid... Spent nearly one hour trying to understand how to implement expectation dp, finally understood, and got AC.

It's just like: you have n equations and n unknown values, and you have to solve the equations to get the answers.

Obviously you are able to solve all the equations because the number of equations is the same as the number of unknown values