Hey, Codeforces!
Pinely is here! Just like every year, we are sponsoring the PTZ competitive programming camp. As a part of this, we have prepared a contest for the participants and invite everyone to join it on Codeforces.
Pinely Round 2 (Div. 1 + Div. 2) is scheduled to start on Aug/30/2023 17:35 (Moscow time).
During this round, you will have the opportunity to solve 9 problems within a time frame of 3 hours. The round will be rated for everyone.
The problems have been authored and prepared by the Pinely team: AndreySergunin, ch_egor, Endagorion, amethyst0, zeliboba, zemen along with our special friend Golovanov399.
We would like to express our special thanks to:
adventofcode, mtw, PurpleCrayon, Silver_Fox, maomao90, qrewetka, Vladithur, nigus, jdurie, alwyn, dorijanlendvaj, OAleksa, ognjentesic, Kostroma, oursaco, tiger2005, SSerxhs, absi2011, EternalAlexander, Lavine, wh0816, Kieray, socpite for testing,
irkstepanov and KAN for coordination
MikeMirzayanov for the amazing Codeforces and Polygon platforms.
We sincerely hope that you enjoy our contest. Wishing you good luck and lots of fun!
P.S. If you are interested in working at Pinely, please visit our website: https://pinely.com/, send us an email at [email protected] or fill in the form here
Congratulations to the winners!
my favourite tester OAleksa
Is the cat in Golovanov399 profile coughing?? Or what else it is doing??
It's thinking.
it's licking it's paw’s
No
it symbolises oppression
As a tester I tested the round.
Smile :)
blushes
People are so cold hearted.
It's a toxic community
irkstepanov orz for coordinating two rounds in a row ...
I just hope it doesn't affect the quality
Some of the best problems I have ever seen :)
All the best to pinely for not getting down votes this time!
Why does the contest page shows that it's 2 hours length (?)
As a tester, I tested because it clashes with IOI :(.
Subtle flex xD
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!
It means you're not ready for CM yet and you will still drop eventually even if you reach it luckily. Try to improve so when you reach CM, it won't be by luck, and you will be able to maintain it.
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
Keep orange please :)
Please let me return to CM (for the fourth time...)
Yeah no not happening :(
Hope to become a master today. TwT
Me too!
good luck to you \o/
thx! Good luck to everybody!
It seems like we've all failed. T_T L_Wave HHY_zZhu
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
Agreed...
speedrunned speedrun
Nice contest. I hope pretests for D are good)
How to do E?
E>FG for sure...
How to do F? Is is again bitsets
use DP: [l,r] is possible iff [l,r'] is possible and XOR[l,r]>=XOR[r+1,r'].
The constraint equals to XOR[l,r]&Highbit(XOR[l,r'])>0, the following part is trivial.
Thanks but won't it take $$$O(n^{2})$$$ space.
We don't need to store all n^2 states.
Basically we just care about Highbit(XOR[l,r']) for all possible $$$r'$$$, so we just store the OR sum of them for each $$$l$$$.
So the memory complexity is $$$O(n)$$$.
Could H be solved with segment tree using lazy propagation?
another speedforces thank you
Was E a directed graph question???
yes you can do it with dfs
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
same bro C was much easier for me than B.
i could not get it even in two hours. B made my day BAD.
yeah bro. negative delta here we go :(
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.
I think you should only increase events that do not depend on any other events by k, one by one, in order of increasing h.
Of course, that's how I did it.
I did not solve it, but not I actually think that you should increase every connected component together, and not just components containing one event.
There is a case when increasing minimum event by k does not affect its maximum dp (so that final dp value doesn't depend on current minimum)
My solution even adds k to these values in advance and then does not process them further.
I did exactly the same thing LOL
The fact is , at a position where I should use 'x' , I used 'i'.
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?
For D, The dominoes must come in pairs.
Can a horizontal domino's coloring affect a row's parity? Can a vertical domino's coloring affect a column's parity?
Can you try minimizing the final task's completion time from moment zero first?
Now you need to minimize the difference between start time and end time. How to increase start time with minimal impact to end time?
Try pushing some tasks from day 0 to day 1. This can be done in O(N+M).
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.
congrats sir
Sketch of proof for G:
What's wrong with my e 221169557
You need to try all possible start quests instead of checking for only one start quest.
ohh ! What was am i thinking..
Ha, finally understood why my solution for E doesn't TLE. I wasn't able to prove the time limit cause I kept track of the hours taken instead of days. Makes total sense now.
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 did almost the same thing and didn't get AC either. I also looked at 2 corner cases — if endpoint for each connected component is maximum the next day (so all nodes without any edges might not be in this interval) and if endpoint is the same day as startpoint. I think that in general this aproach is corrent or maybe there are some other corner cases
Your solution will fail for this case.
4 2 24
23 23 2 6
2 4
3 4
The answer should be 7 I guess. Mine gives correct output
Not yours, newusercf solution will fail on this.
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.
dfs for it and keep track for every row and column number of black and white so that when you start a new dfs it would balance this column or row and just keep fliping the color as you dfs from each cell. a check must be made that all rows and columns contain even numbers of half dominos otherwise no solution exist.
Consider the following test for E:
(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?
$$$a_{i} < b_{i}$$$ most hold for your input
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.
practise more, do more virtual contests and have other hobby than cp along with it.
Third time in row solving c, d and stucking in b so sadd :(
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?
How do you debug for a large testcase, lets say 1000 size input array.
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!
Thanks for giving a good experience! The problems are interesting , but I haven't solve the B problem. Could someone give me the solution ? Thaks a lot.
Can someone explain the idea behind E without DP approach?
Is my dp cute?
Video tutorial for problems A&B&C in english: https://youtu.be/X08zbEDtaI8
Thought would be useful to the community
I hate freaking E problem
Was this contest unrated ??
Good problems
Hi all, it would help if you can post some insights/hints for the problems of this contest on https://starlightps.org. Here's a link to the problems: https://starlightps.org/problems/collection/cf-pinely-2/. This will help us get more data so users can have a platform to:
Check it out if you're interested. Thanks!
has anyone got a call back from pinely ??
Great Contest and Fast Editorial
Very good problem! Love from China.