Pinely Round 2
By pinely, 15 months ago, translation, In English

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:

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 hr@pinely.com or fill in the form here

Apply

Congratulations to the winners!

  1. tourist
  2. Radewoosh
  3. QAQAutoMaton
  4. jiangly
  5. Ormlis

Editorial.

  • Vote: I like it
  • +472
  • Vote: I do not like it

Comments Comments (121)
| Write comment?
»
15 months ago, # |
  Vote: I like it +2 Vote: I do not like it

my favourite tester OAleksa

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +14 Vote: I do not like it

As a tester I tested the round.

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it
Hey you !
→ Reply
»
15 months ago, # |
  Vote: I like it +36 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Some of the best problems I have ever seen :)

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +17 Vote: I do not like it

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 (?)

→ Reply
»
15 months ago, # |
  Vote: I like it +78 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +12 Vote: I do not like it

pinely round 1

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

So this is only Legendary GM and international GM round.

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    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.

    → Reply
»
15 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Recently the frequency of Codeforces contests is less.

→ Reply
»
15 months ago, # |
  Vote: I like it +42 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where's the score distribution??

→ Reply
»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +38 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +10 Vote: I do not like it

3 hours OMG

I can't

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

omg Raksha Bandhan round

→ Reply
»
15 months ago, # |
  Vote: I like it -26 Vote: I do not like it

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!

→ Reply
»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Green me pleasēéêè

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

score distribution pleeease

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Keep orange please :)

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become a master today. TwT

→ Reply
»
15 months ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester, i hope everyone gets positive deltas

→ Reply
»
15 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope to become Specialist today. Finger crossed.

→ Reply
»
15 months ago, # |
  Vote: I like it +33 Vote: I do not like it

As a tester, I'm not a tester.

Any bets on how much rating I'll lose?

→ Reply
»
15 months ago, # |
  Vote: I like it +23 Vote: I do not like it

nice 88005553535 reference

→ Reply
»
15 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it -10 Vote: I do not like it

unbalancedForces

→ Reply
»
15 months ago, # |
  Vote: I like it +30 Vote: I do not like it

speedrunned speedrun

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest. I hope pretests for D are good)

→ Reply
»
15 months ago, # |
  Vote: I like it -15 Vote: I do not like it

How to do E?

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E>FG for sure...

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to do F? Is is again bitsets

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks but won't it take $$$O(n^{2})$$$ space.

        → Reply
        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)$$$.

          My code
          → Reply
»
15 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Could H be solved with segment tree using lazy propagation?

→ Reply
»
15 months ago, # |
  Vote: I like it -9 Vote: I do not like it

another speedforces thank you

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was E a directed graph question???

→ Reply
»
15 months ago, # |
  Vote: I like it +43 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    same bro C was much easier for me than B.

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    i could not get it even in two hours. B made my day BAD.

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      yeah bro. negative delta here we go :(

      → Reply
»
15 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I think A to D is easier than before.

→ Reply
»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Of course, that's how I did it.

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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.

        → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My solution even adds k to these values in advance and then does not process them further.

      → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did exactly the same thing LOL

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The fact is , at a position where I should use 'x' , I used 'i'.

    → Reply
»
15 months ago, # |
  Vote: I like it +109 Vote: I do not like it

Speedrun until "Speedrun"

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +69 Vote: I do not like it

Me in the contest:

First hour: finish A,B C and D

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

→ Reply
»
15 months ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

any hints for D and E?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For D, The dominoes must come in pairs.

    → Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    D
    E
    → Reply
»
15 months ago, # |
← Rev. 3   Vote: I like it +91 Vote: I do not like it

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.

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    congrats sir

    → Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    Sketch of proof for G:

    • A move consists in replacing edges $$$a \rightarrow b$$$ and $$$b \rightarrow c$$$ with $$$a \rightarrow c$$$ and $$$b \rightarrow b$$$.
    • Any node with a self loop becomes inactive for the rest of the process.
    • If the cycle has length $$$1$$$, the formula is valid. For example, you can show that you can always reorder the operations "from the leaves to the root", then it's enough to choose for each node if it's a $$$b$$$ in some operation and with which $$$a$$$. Note that the number of candidate $$$a$$$ (i.e., the indegree) is constant.
    • If you choose $$$a$$$ outside the cycle and $$$b$$$ in the cycle, you get a new cycle of length $$$1$$$ and you can use the formula.
    • If you choose $$$a$$$, $$$b$$$ outside the cycle, you don't affect the cycle.
    • The formula is not valid as it is if you choose both $$$a$$$, $$$b$$$ in the cycle, because of an edge case: if in some moment the cycle has length $$$2$$$ and you choose its nodes as $$$a$$$, $$$b$$$, $$$c$$$, you automatically make $$$2$$$ self loops instead of $$$1$$$.
    • Therefore, you have to exclude all configurations where you make all the self loops in the cycle except one using an $$$a$$$ in the cycle.
    → Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    What's wrong with my e 221169557

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You need to try all possible start quests instead of checking for only one start quest.

      → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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 :(

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
15 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I hope one day I can solve E

→ Reply
»
15 months ago, # |
  Vote: I like it +96 Vote: I do not like it

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!

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    $$$a_{i} < b_{i}$$$ most hold for your input

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    practise more, do more virtual contests and have other hobby than cp along with it.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +63 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    How do you debug for a large testcase, lets say 1000 size input array.

    → Reply
»
15 months ago, # |
  Vote: I like it +10 Vote: I do not like it

nice name for E. good mid contest motivation

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the idea behind E without DP approach?

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is my dp cute?

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Video tutorial for problems A&B&C in english: https://youtu.be/X08zbEDtaI8

Thought would be useful to the community

→ Reply
»
15 months ago, # |
  Vote: I like it -31 Vote: I do not like it

I hate freaking E problem

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was this contest unrated ??

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Good problems

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

  • share/discover hints/insights on various problems
  • find similar problems given insights they struggled with.

Check it out if you're interested. Thanks!

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

has anyone got a call back from pinely ??

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Contest and Fast Editorial

→ Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Very good problem! Love from China.

→ Reply