return of chtholly (tree?)

as a tester

As a tester, thomasthomasthomas

willy108 on codeforces in the big 26?????

As a tester, this round is memorable. I encourage you to participate.

As a tester, I can confirm chromate00 authored between 0 and 9 problems.

Here is my solution to B for q = 0 (it can be easily extended to q = 1).

Say we are trying to solve the range $$$[l, r]$$$. While the highest bit of $$$l$$$ equals the highest bit of $$$r$$$, remove the highest bit from both. This does not change the answer.

Let $$$x$$$ be the greatest power of $$$2$$$ less than or equal to $$$r$$$. Then if $$$r - x \lt l$$$ we will recursively solve $$$[l, x)$$$ and $$$[x, r]$$$ and return the sum. Only the left interval can keep splitting so the number of intervals is bounded by $$$O( \log R )$$$

Otherwise, we can count the number of the numbers in $$$[l, r]$$$ with even popcount and odd popcount and return the max.

Finished implementing $$$q = 1$$$ right after the contest ended :(

dont know how I should feel about one of my problems being in your last 100 :O

passed D 1 minute after the contest ends :(

Nice problems tho

As a tester, the problems are nice and I encourage you to participate.

As a tester, wait where is the tester list.

Intel(legent) stonks

As a tester, I hope you enjoy the round as much as I did. :)

I ran my solution to 2E (which mle'd on system tests) in gym with higher limits and it takes 3.5/4s and 1400/1024 MB.

I'm not sure if its possible to optimize. :(

My solution idea was to use a bitset which denotes which elements of the frequency array are positive and use find first to find the best area.

Submission: 343415947

Update: I used short instead of int for areas that are small enough and my solution passed.

Submission: 343431788

I found B to be the most difficult problem in the first 5 :\

Hahaha

I was trying something with lazy segment + another segment tree + mergesort tree but ran out of time to debug my solution :(

As a tester of teamscode, I'm excited to see danx in the author list.

As a tester, you should participate in USACO ...

I was doing problem C2

Submit to C2, -> TLE

Someone evicts me from the room I am sitting because there is a university office hours session taking place there.

I walk outside and sit on the floor.

Fix my sol, finally AC!

Round is unrated ...

As a tester, here is a different solution to stones:

Note that we can always some operations to do the following $$$2$$$ moves.

1) add ($$$-1$$$, $$$-1$$$) to $$$i$$$ and ($$$+1$$$, $$$+1$$$) to $$$j$$$, $$$i \neq j$$$.

2) If you have $$$\ge n - 2$$$ white and $$$\ge n - 2$$$ black stones at at least one other stone of any color in a pile we can add $$$(-(n - 2), -(n - 2))$$$ to this pile.

It makes sense that we would want to stack as many pairs of opposite colored stones in one pile and then use the second move as much as we can.

Let $$$c$$$ be $$$\sum_{i=1}^n \text{min}(b[i], w[i])$$$. We can increase $$$c$$$ further by doing a move we subtract each pile of black or each pile of white by $$$1$$$ as long as they are all positive.

Note that at this point each pile has either a positive number of black or white stones and then we can pretend we set all the $$$c$$$ pairs on the side.

However, it may be optimal do more type $$$1$$$ or type $$$2$$$ operations to increase $$$c$$$ before we subtract $$$n - 2$$$ as many times as possible.

When we increase the entire array in a type $$$1$$$ operation, $$$c$$$ increases by the amount of piles with positive black stones minus $$$1$$$ and then each of these piles decrease in size by $$$1$$$ (and similar logic for type $$$2$$$ operation but with white stones).

Its never optimal to do both extra type $$$1$$$ and type $$$2$$$ operations because at most you can get $$$n - 2$$$ extra pairs and they "cancel" out.

We can simulate this in $$$O(n \cdot (w + b))$$$.

However, we can notice that we don't need to simulate it directly and it only depends on the number of positive elements in the side we are doing extra operations to subtract from and the total number of black and white stones.

We can sort the array to find out when the number of positive numbers changes and maintain the sums as we do more extra operations.

We can use this to speed up the simulation to $$$O(n \log n + w + b)$$$

To speed this up further we can consider every interval where the number of positive piles is the same. Call this $$$k$$$. At every step the sum of the array will change by $$$n - 2 \cdot k$$$ and the number of pairs increases by $$$k - 1$$$.

Because the pairs are taken mod $$$n - 2$$$ we can't just check the first and last values of the interval. However, it is enough to check the first and last $$$\frac{2n}{k}$$$ in order to find the global minimum (on this segment). This is fast enough because $$$\sum_{i=1}^n \frac{n}{i} \approx n \log n$$$

Since there are only $$$n$$$ different possible values of $$$k$$$ the total time complexity is $$$O(n \log n)$$$.

Code: https://pastebin.com/DYLEYN37

As a tester, this is the first time I'm hearing that I tested.

As a tester, there is at least one problem I like a lot.

As a participant, I was invited to test this round when it was a div2 but thankfully I was lazy so I can participate officially.

As a tester, I enjoyed the problems and encourage you to participate.

It seems like links to comments no longer work.

For example, https://codeforces.me/blog/entry/131610#comment-1172666 just takes me to the blog page without going down to the comment.

OMG same!

As a tester, 0 people solved H in testing ...

As a tester I enjoyed suffering (and the problems of course). I encourage everyone to participate.

+1 I was running a lot of inputs in custom invocation until I noticed the pattern and figured out the problem but it was quite slow.

As a tester, I'm so back.

The contest starts in 1 day!

Remember to join the discord server as we will be answering clarifications from there.

Will the blitz game be released publicly to codeforces users at any time?

As an author, I encourage you to participate.

As a tester, Intellegent forgot to mention me :sobb:

upd: he fixed it :)

There are already 7 scoring opportunities in Div2.

I'm guessing they didn't want to increase it even more to 8 so put the hard version only in Div2.

First time I tried competing in Rust. Hopefully next time will go better. Thanks for the round!

Context: I had 30 wrong submits to F before getting AC

Some of my favorites include

1935E - Distance Learning Courses in MAC

1965E - Connected Cubes

1977E - Tensor

1991G - Grid Reset

Of course, I'm a little biased but I also really like 2035D - Yet Another Real Number Problem, 2035F - Tree Operations, and especially 2035H - Peak Productivity Forces from global round 27. :)

As a tester, I enjoyed the problems a lot!

Thats not what you originally said. You said no one reaches CM from div3. This is not true.

Even from non new accounts, you can get quite close to CM from winning one div3.

i_hate_newbies reached CM from div4.

After downvoting a blog/comment, it shows a triangle icon which you can click to report.

no trusted participant rules

Maybe this is the issue that could be fixed ...

Hi, I'm the author of the problem. I was curious if you read the intended solution because from my limited understanding of your solution I think you did something different. I think the intended solution doesn't have any casework and the code was quite easy to write.

In addition, I was wondering if you liked solving it? :)

I guess that would have made sense. However, there were a lot of optimizations that where any of them could make it pass (although unoptimized passed comfortably for many people).

• Adjust the bounds of binary search to look for only a better answer
• Skip half of the binary searches by only checking the correct parity of the answer
• Unrolling the dfs order and iterating instead of doing recursion
• Optimizing to $$$\mathcal{O}(n^2 \log n + n \log a)$$$

We knew the TL was tight for some people but were also aware of a very fast N^3 solution and wanted to cut it.

Fixed, thanks for letting me know

Interestingly enough the answer for lower $$$n$$$ is just the identity permutation. I still decided to remove it so people didn't get confused by edge cases.

C can be solved for 3 rows too!

Code courtesy of liympanda https://pastebin.com/mjcPwbAa

If China hadn't gotten 1984'd at IOI, then Open AI would not get a gold medal. LOL

Actually the rank title is "tourist" (you can see this in the max rating section).

However Codeforces capitalizes the first letter in the official title. This is true for other ranks as well.

tourist solved F!!!

Hi, I don't know where to post this but I want to report Dazlin7 for suspicious submissions. MikeMirzayanov Vladosiya

because ill get fired for saying this

as a tester, im never testing teamscode again

I'm very curious about this infamous d1E problem but now it seems like we will never see it :(

It seems like 1 + 2 = 3.

As I tester, I enjoyed the problems and encourage you to participate!

(yes this comment is copied from my div2 tester comment and no i have not actually tested any problems)

As I tester, I enjoyed the problems and encourage you to participate!

As of writing this comment, congratulations on reaching top 1 contributor!

Just tested the method! Here are your alts: flammifer, tzhamoidin_twink, secretno_botaem

My view when coding

dark gathering

Watch Horimiya.

literally 1984

Thanks for contest! C and D were not that great but B was nice and E is amazing!

I think this misses his point that he seems to be pushing in his last few blog posts which is that at least while taking contests guessing is faster and more optimal than proving solutions.

I am not sure I completely agree with his philosophy as the quality of my guesses tends to be directly related to the quality of samples.

How come it is div1 + div2 when it seems like the sponsor (codeton) has backed out?

Reyna breaks this record and has 1313 days.

I guess another question is how to construct a testcase such that it takes about V^{1/k} turns to have no consecutive k monsters alive. I think(?) some of the FST on E2 came from people simulating not enough steps.

My solution to E today was casework.

I split into segments of consecutive characters. If even number of segments, we can just pair segment[i] to segment[i + 1] and we're done.

Odd number of segments: if there is a position where segment[i] != segment[i + 2], we can make a segment starting from i + 1 and extend it equally as much as possible to both left and right. After that, there might be an even number of segments left which we can pair off just like above.

Now we have alternating segments. We can look for a segment[i] where i is odd (0 indexed). If the length of segment[i] >= 2, we can break into two distinct segments, and then pair up like the even case.

If we still have not found anything, we can look for a segment[i] where i is even and i is not the first or last segment. If the length is >= 2, then we can s into two strings [0, x] and [x + 1, n — 1] where s is somewhere in segment[i] (basically split somwhere in segment[i]).

Now the only thing we should have left is an odd number of alternating segments of length 1. We can prove that this is impossible to split because after splitting, there is guaranteed to be at least one odd length segment but this will always be a palindrome.

Submission: https://codeforces.me/contest/1951/submission/255365657

Unfortunately, I did not finish this during the contest qwq.

I will quit cf, touch grass, and enjoy life until September. :)

2 people from the same school? Wow!

As an author, I contributed to the spreading of propoganda.