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 30.08.2023 17:35 (Московское время).
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!
UPD. Score distribution: $$$500$$$ — $$$750$$$ — $$$1000$$$ — $$$1250$$$ — $$$1750$$$ — $$$2500$$$ — $$$2750$$$ — $$$3500$$$ — $$$4000$$$.
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.
As a tester I tested the round.
Pls stop mafia activity in Subotica
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
Excited for this round. Best of luck to all contestants! :)
Some of the best problems I have ever seen :)
Aj kisu Pari na Bole :) {hehe}
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
As a contestant, I hope all of you will enjoy this contest!
As a contestant, I hope all of you will enjoy this contest!
I hope this one can reach 1200
Good luck to everyone ;)
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
Rounds like Pinely and others, are they ranked "its final rank effects on codeforces rate"?
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...
B was lit
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
B made my day BAD.
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.
Just needed 10 more seconds :")
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!
today's lesson : Don't ever participate in any div1+div2 rounds
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.
Yeah same here... my third contest. Found A very tricky as well. Seeing people's reaction though it seems like it was easier than the standard A level. Hopefully it'll get easier with practice.
this may sound very cliche, but the truth is... we've all been there before, and without struggling we'll never grow
considering this was only your second contest ever, i suggest waiting for div3 or div4 rounds. ABC will be much easier!!!
the struggle is real but it means that you're improving yourself and pushing beyond your limits so never back down never give up :) !!!
Thanks man! I will keep learning!
Third time in row solving c, d and stucking in b so sadd :(
Problem D's these days are just....
Thank you for the contest, I really like the problems!
Problem A: Had wrong solution and it took lots of time for fixing.
Problem B: My observation skill got boosted thanks to this.
Problem C: Recognized the pattern but not enough time for the implementation, solved after the contest just now.
I am happy because I can still manage to solve till the end even after getting lots of Wrong Answer verdict for problem A. Looking forward to enjoying more problems from you guys! Cheers!
Upto what rank participants are considered for further rounds of pinely ??
what's the approach for D? Is it observation/maths or is it a bit of backtracking+dp? A hint would be very helpful?
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.
Amazing contest! Problems were nice and statements were well-written and easy to understand. Thanks to the authors of Pinely and all the testers.
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.
see my submission and compare the code with the last test case in example you'll find that it's simple
Can someone explain the idea behind E without dp approach?
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
hello
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!
Good Contest. Really like the problems but had hard time to solve task A.
Felt bad for div 3 lovers who missed yesterday's contest
Why the problems' rating takes much time to appear?
has anyone got a call back from pinely ??
Great Contest and Fast Editorial
Yes it was really nice
Very good problem! Love from China.
bruh.. again pinely