my favourite tester OAleksa

Is the cat in Golovanov399 profile coughing?? Or what else it is doing??

As a tester I tested the round.

As a tester I tested the round.

irkstepanov orz for coordinating two rounds in a row ...

Some of the best problems I have ever seen :)

All the best to pinely for not getting down votes this time!

During this round, you will have the opportunity to solve 9 problems within a time frame of 3 hours

Why does the contest page shows that it's 2 hours length (?)

As a tester, I tested because it clashes with IOI :(.

pinely round 1

the duration in this blog is 3 hours and the duration in the contest section is 2 hours. MikeMirzayanov

So this is only Legendary GM and international GM round.

As a blue participant, I hope to stay blue after this round. GL & HF

Losing hopes of becoming CM. I wish I knew what I had to do different to achieve this silly milestone. Everyday waking up thinking this contest will make me CM is a curse in itself!

Recently the frequency of Codeforces contests is less.

As a Pinely Round 1 "competitor" (I say competitor in quotes because it would imply that self destructing and losing 140 points can be considered "competing"), I will be in this contest for redemption.

Where's the score distribution??

As a tester, hope you will enjoy the problems. It’s been 18 months since the most recent div1 + 2 on a Wednesday

As a tester, I hope all of you will enjoy this contest! Also, Pinely Treasure Hunt Contest, which is my first time cooperating with a team and earning knowledge from mind storm & attempts, is also a nice contest, and I recommend it to you all :D

3 hours OMG

I can't

omg Raksha Bandhan round

Hi Codeforces!

It would be very helpful if you can post insights/hints for the problems of this contest on https://starlightps.org. This (Starlight Problem Solving) is a website where people can share and discover key insights/hints for problems (with the help of AI) AND find similar problems (with the help of AI) based on insights they struggled with on one problem. We hope this will help many problem solvers and need data in order for that into happen. (Just keep in mind that you agree to publish the insights under CC by 4.0 license.)

By the way, we are also planning a gift card giveway to people posting insights to a certain number of problems, so stay tuned for that!

I want to participate but my sisters will beat me up.

Green me pleasēéêè

score distribution pleeease

I hope this one can reach 1200

Keep orange please :)

Please let me return to CM (for the fourth time...)

Hope to become a master today. TwT

As a tester, i hope everyone gets positive deltas

Hope to become Specialist today. Finger crossed.

As a tester, I'm not a tester.

Any bets on how much rating I'll lose?

nice 88005553535 reference

Good Contest ever.... Problemset was clear...

unbalancedForces

speedrunned speedrun

Nice contest. I hope pretests for D are good)

How to do E?

E>FG for sure...

Could H be solved with segment tree using lazy propagation?

another speedforces thank you

Was E a directed graph question???

Good round. Really liked problems B, C, F, and G.

I spent 2 hours trying to get the observation for B. I am so dumb

I think A to D is easier than before.

I completely don't understand why my solution for problem E is wrong. Simply put, I first do a dp calculate the time , then increase the minimum event by k, one by one. But this approach resulted in a WA,I find this outrageous.

Speedrun until "Speedrun"

Me in the contest:

First hour: finish A,B C and D

Second and third hour: Stare at E and see my ranks dropping.

The contest was really beautiful, and I liked the problems a lot. Definitely one of the best contests I've participated in in the past few months.

any hints for D and E?

First time solved G (by guessing) in div1+2 round, and first time got top50 in div1+2 round. I can't wait to see 100+ delta (no FST please).

A: We can record "there are how many online events in total" and "there are how many subcribers are online at most at the same time" during the process, and the first number is the maximum number of subscribers have seen the post, the second number is the minimum.

B: Let q be the inverse function of p, and count there are how many i such that q[i]>q[i+1], we can get the answer. In fact, when we choose x for operation, we let q[x-1]<q[x], and the relations of q[i-1] and q[i] for all i!=x are remained the same. So each operation will decrease #(i: q[i]>q[i+1]) by at most 1.

C: There are n distinct integers in [0, n] (n+1 integers), so there will be exactly one missing number in [0, n]. Let a[0] be this missing number, then each operation will swap a[0] and a[i] for 1<=i<=n, and this will make a[0, n] be cyclic right-shifted (a'[i]=a[i-1] for i>0, a'[0]=a[n]).

D: If there are any row or column with odd cells with domino, there's no solution. Otherwise, we can construct a solution like this: First consider vertical dominos. Because the 1st row contains even cells with domino, and each horizontal (LR) domino has 2 cells in one row, the first row must contain even U-cells (the 1st row can't contain D-cells), and we can color half of them black and half white. Then we colored the 1st row with equal black and white cells, and the D-cells in the 2nd row will also be colored equally (which means 2nd row contains even D-cells). Then because 2nd row must contain even L-cells and R-cells, the 2nd row must contain even U-cells, and we can color them equally again. By induction, we can color all vertical dominos and fill rows equally (Note that vertical dominos will always fill columns equally). Similarly, we can also color horizontal dominos equally.

E: We sort all "start quests" (quests without dependencies) by h[i] and assume we start game by the first start quest (with minimal h[i]). Let dp[i] = the earliest day we can complete quest i (the days are 0-indexed), then the time we complete i-th quest is k*dp[i]+h[i], and the dp formula is dp[j]=max(dp[j], dp[i]+(h[i]>h[j])) for dependency i-->j. Then we need to try to change the quest we start the game. For each start quest, we need to change start time to h[i+1] and change dp[i] from 0 to 1. Of course when we increase dp[i] we need to update dp[j] for all i-->j, but during the whole process, each dp[j] will be increased at most once. So we can update dp[j] by dfs.

F: We solve the problem by check every ranges [i, j] if [i, j] can be remained (we call such ranges valid). First [1, n] is valid. For range [i, j] to be valid, we need a valid range [i, k] where xor_sum[i, j]>=xor_sum[j+1, k], or valid range [k, j] where xor_sum[i, j]>=xor_sum[k, i-1]. If we let high_bit(n) be the highest significant bit of n (example: high_bit(21) = high_bit(0b10101)=0b10000=16), then a >= b is equivalent to (a^b)==0 or (a&high_bit(a^b))>0. The first condition means a==b, and the second means "on the highest bit where a and b differ, a is 1 and b is 0". So [i, j] can be obtained from [i, k] means: there's valid range [i, k] such that xor_sum[i, k]==0, or xor_sum[i, j]&high_bit(xor_sum[i, k])>0. So if we let R_flag[i] = (if there's any valid range [i, k] such that xor_sum[i, k]==0), R_mask[i]=(the bitwise or of highbit(xor_sum[i, k]) such that [i, k] is valid), we can check if [i, j] can be obtained from [i, k] in O(1), and we can check if [i, j] can be obtained from [k, j] by L_flag[j] and L_mask[j] similarly. Thus we can solve the problem in O(n^2).

G: I guessed the answer but don't know how to prove it: build a directed graph with edge i-->a[i], for each connected component, the answer is (prod(deg[u])-sum(deg[u]-1))(prod(deg[v])), where u are nodes on the cycle, v are other nodes.

How to solve F? Is it checking whether previous block's xor's MSB is set in current block's xor and doing it for n^2 subarrays with bitmasking?

There's an $$$O(n\log^2 v)$$$ solution (could be optimized further to $$$O(n\log v)$$$, but I didn't implement it during the contest) for problem F. Unfortunately, I didn't realize that $$$O(n^2)$$$ was enough to pass and wasted too much time on the Polylog solution, which needed much care when implementing :(

Is this approach incorrect for E? I do this, and in my brain it feels this should give the correct answer 100%. But I don't get AC.

First, I find the minimum completion day for each node, assuming the roots start at day 1.

Then, I traverse in reverse topological order and try to maximize the completion day of each node, while making sure it doesn't affect it's dependencies.

Now, for each connected component, we have some start point S and endpoint E. We can sort all these by increasing order of start hour, iterate over start hours, and find the answer if we choose to start at this hour on day 0. I print the minimum of these answers.

I hope one day I can solve E

I really liked F and G although/because I was terribly stuck on both of them! I still feel F is harder than G though. Thanks for the nice round!

Can someone explain graph based solution for problem D? Thank You.

Consider the following test for E:

1
3 2 12
7 8 0
2 1
1 3

(3 tasks to do at hours 7, 8 and 0; task 1 depends on 2, task 3 depends on 1)

My solution says the optimal order is to first do task 2 (since you literally can't do any other tasks at first) — that will happen at hour 8 of day 1 — then do task 1 (again, you can't do any other task) at hour 7 of day 2 — then finally do task 3 at hour 0 of day 3. Time between first two tasks is 11, and time between second two tasks is 5, for a total of 16.

However, tourist's solution gives the answer 11. What am I missing?

It's was my second time i participated,i tried to solve A for 3 hours but i couldn't same happened with me in the first contest ,and now i feel very demotivated , i feel myself very weak, what shall i do? Please help.

Third time in row solving c, d and stucking in b so sadd :(

Problem D's these days are just....

Upto what rank participants are considered for further rounds of pinely ??

IS there a way to see a test? For example can you send it to me if I ask nicely?

nice name for E. good mid contest motivation

Problem B,E,F are really good, especially problem B, which let me stuck for half an hour. Thanks for the nice problem!