By pigstd, 3 months ago, In English

text

Hello, Codeforces!

Members of team EZEC are glad to invite you to participate in Pinely Round 1 (Div. 1 + Div. 2), which will start on Nov/20/2022 17:35 (Moscow time). You will be given 7 problems, one of which has a subtask, and 2 hours and 30 minutes to solve them. The round will be rated for everyone. It is greatly recommended to read all the problems.

There is at least one interactive problem, so please see the guide of interactive problems if you are unfamiliar with it.

We would also like to thank:

Fun facts:

  • Anton reviewed 18 problems in total.
  • This is the 13th round of EZEC. Here are some previous rounds: Round 11 on Luogu, Round 12 on nowcoder.
  • The team has an anime character EZEC-chan (the girl in the image), hope you like it :3
  • orzdevinwang found a better solution of F the day before the contest.

This round is made possible with the support of Pinely!

Pinely is a privately owned & funded algorithmic trading firm, our main focus is set on high frequency and ultra low latency trading.

We are a team of mathematicians, programmers, engineers and computer scientists driven by the immense passion for knowledge. We constantly face various challenges such as developing strategies for trading, optimizing trading systems to achieve the lowest latency reactions to various market events, saving and processing large volumes of historical data. The work we do requires a high ability to create effective C++ code, algorithmic thinking and mathematical intuition, which attracts winners, awardees and medalists of various competitions in the respective fields such as ICPC, IMC, HITB PRO CTF and Google HashCode etc.

Find out more about us on our website pinely.com or from our employees registered here on CF.

If you want to join our team please send your CV to hr@pinely.com or fill in the form

Apply

Top 30 contestants and 10 random contestants placed 31-100 will receive a branded Pinely hoodie :)

The statements were made as briefly and clearly as we could. GLHF!

Scoring distribution: 500 — 1000 — 1250 — 1750 — 1750 — (2500+2000) — 3500

UPD1: Editorial is out. link.

UPD2: Congratulations to the winners:

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

»
3 months ago, # |
  Vote: I like it +46 Vote: I do not like it

Auto comment: topic has been updated by pigstd (previous revision, new revision, compare).

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

    Where is fyy Memorial Valley School

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

    .
    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it -89 Vote: I do not like it

      In fact there's something more about the problem D: As a tester, I give out a solution with BGF and ODE for it. So in fact, this problem still can be strengthened. :)

      But to make the gap less large, the problem provider didn't do that. :)

      However, the gap between D and E might be even larger than such between C and D. :(

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it -66 Vote: I do not like it

        oops

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

        i am agree with him

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        In fact there's something more about the problem D: As a tester, I give out a solution with BGF and ODE for it. So in fact, this problem still can be strengthened. :)

        But to make the gap less large, the problem provider didn't do that. :)

        However, the gap between D and E might be even larger than such between C and D. :(

»
3 months ago, # |
  Vote: I like it +144 Vote: I do not like it

All hail our emperor anton

»
3 months ago, # |
  Vote: I like it +103 Vote: I do not like it
»
3 months ago, # |
  Vote: I like it +400 Vote: I do not like it

As a tester, i'd say

guess
»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Anime round is coming :|

»
3 months ago, # |
  Vote: I like it +110 Vote: I do not like it

As a tester, I'm cute (。・ω・。)ノ♡

»
3 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

pigstd orz

»
3 months ago, # |
  Vote: I like it +62 Vote: I do not like it

As a tester, I strongly recommend this round for straightforward statements & high-quality and interesting problems. GLHF!

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

    I agree by being a contestant on luogu and their problems have high quality in just about every round. Hope to get higher ratings this round!

»
3 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Who is she?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WAIFU!!!! We really need an anime-mascot-cute-girl for codeforces <3

»
3 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Just noticed Technocup 2022 Elimination Round 1 is going to be held tomorrow as well (which in the past years has a live mirror on CF). Are we going to have 2 rated CF rounds in the same day ?

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

    This year Technocup will be held not on Codeforces, but on the Allcups platform made by VK so unfortunately it seems to me there will be no mirror.

»
3 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Wow, EZEC Round! EZEC is one of my favourite Chinese problemsetting groups. Looking forward to solving the problems with high quality.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it hard?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Maybe hard I think.

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

      In this round, we tried our best to avoid weird, difficult and confusing problems. Let's discuss them after the contest!

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

What a cute blog ._.

»
3 months ago, # |
  Vote: I like it +7 Vote: I do not like it

She is so cute!

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Looks like a good contest, good luck everyone!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

500 — 1000 — 1250 Fabulous!! ^_^

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow! 60 people are coordinating in this round.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

May the anime girl bring me a high +ve delta in this contest.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

After seeing the photo I really have a good feeling about this round

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Patalok!

»
3 months ago, # |
Rev. 3   Vote: I like it -11 Vote: I do not like it

This ROUND seems interesting one (^o^) ,eagerly waiting for this round ★^^★

»
3 months ago, # |
  Vote: I like it +22 Vote: I do not like it

happy world cup day

»
3 months ago, # |
  Vote: I like it -40 Vote: I do not like it

Stop putting otaku images in codeforces!

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

    I apologize if it bothers you. The picture is a representation of our team spirit. She is not from an anime. We designed the picture and spend a lot of time and money to make her alive. I appreciate your honesty and hope you like her

»
3 months ago, # |
  Vote: I like it +17 Vote: I do not like it

is pigstd a girl? pigstd

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

    If you take a look at her profile, you will know that she is Chisato Nishikigi, obviously a girl. She even has a picture of herself uploaded as proof.

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

    Yes!I'm her classmate,she is so cute! :d

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

    Dude, this is not important, the important thing is that pigstd is really cute.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    It depends on your imagination :).

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Hopefully I can hit 500+ this round :)

»
3 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Rated?

»
3 months ago, # |
  Vote: I like it +255 Vote: I do not like it

The problems are very nice, recommend participating.

»
3 months ago, # |
  Vote: I like it +20 Vote: I do not like it

I hope there will be no anime in the problem description.

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

dXqwq orz

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

orz

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I hope I can be red this time!

»
3 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Is this contest rated for everyone?

»
3 months ago, # |
  Vote: I like it -16 Vote: I do not like it

is this rated?

»
3 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Great progress on the announcement

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Expecting Interesting Problems

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

CF plus World Cup night!

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

    Is China in the world cup?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +32 Vote: I do not like it

      yes! in the same group with Italy (

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

        Centainly Not. Honestly, neither China nor Italy has made it into the World Cup this year.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it -21 Vote: I do not like it

          As Chinese all know,China football team will never get the oppotunity to join the world cup,unless they train hard enough.In China,this has become a joke.

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

    They can't because they are small.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

CF round + FIFA world cup day... OMG :)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

All hail our emperor Anton :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how did you draw the anime girl? did you get it commissioned?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Red Round and The World Cup.... just I need tourist beside me and a tub of popcorn... Rank 1 and amazing World Cup guaranteed ^,^

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ah, why it couldn't have been moved a bit earlier so it doesn't clash with WF opening? :/

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How young is orzdevinwang?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck everyone !

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Weebs Get a life

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

EZEC-chan is so cute!

»
2 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Off topic: where does EZEC-chan's tail come out from?

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Is pigstd really a girl?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

as a newbie downvote me

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

All hail our emperor anton.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

how is this div1+div 2? where is the div 2 in this lol

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

It is difficult for me,I wrote problem A and went to bed. After reading B and C, I have no idea. I want someone to teach me, after the game

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

wasted starting 10 minutes figuring out wtf is common prefix and sufifx

»
2 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Oh, the round seems to be more difficult than the writers expected, but as difficult as I expected, because I'm just a low-level taster.

btw, the writers are watching the World Cup.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just every single time I think that I can't get results worse than previous time, I somehow manage to do this anyway. At least the next competition is div 4 round...

»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Spend 1h on E because I forgot to check whether the vertex is a cut point and 1h on an incorrect solution of F. :(

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

    is there a nice way to cover this case? i ended up directly checking the validity of my candidate answers in $$$O(n^2)$$$ with bitset.

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

      what language are you guys talking in?

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

      I did the following:

      Find arbitrary spanning tree, choose any leaf in it. It is definitely not cutpoint. In case it has degree less than $$$s - 1$$$, (where $$$s$$$ is the size of current connectivity component), you can switch it and you're done. Otherwise, switch any other node, for example, adjacent of the leaf in the spanning tree (as I did it).

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +10 Vote: I do not like it

        hmm I'm not sure that any node works in that case, since there can be other nodes in the spanning tree that are also degree $$$s-1$$$. for example, the case

        1
        6
        011100
        100100
        100100
        111000
        000001
        000010
        

        which looks like


        1 / | \ 2 | 3 \ | / 4 5-6

        hacks your solution 181782667. If the spanning tree is a star graph about 1, then choosing node 4 as your leaf will cause you issues, as it and its parent are both connected to everything.

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

      Any smallest degree vertex in the component works (unless it's a clique which is a different case)

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Doesn't this break for this example:

        1-2, 1-3, 2-4, 2-5, 4-5, 3-6, 3-7, 6-7

        1 has the smallest degree of 2, but it is a cut point.

        Edit: Oh, I guess it works for the overall problem, though.

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

          Yes, doesn't matter if it's a cut point, it will always give an answer set of size 1.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lets hope I dont get TLE in C

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve D?

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

    put $$$a$$$ and $$$b$$$ on top of each other, and lets build a string $$$c$$$ of length $$$n$$$ on the alphabet $$$(0,0)$$$, $$$(0,1)$$$, $$$(1,0)$$$, and $$$(1,1)$$$ (i can't get the column vectors to play nice with the inline latex, but the first one goes to $$$a$$$ and the second goes to $$$b$$$). we will count by starting off with the empty string, and sequentially inserting characters into valid positions.

    carries are started by a $$$(1,1)$$$, are continued leftwards by either $$$(0,1)$$$ or $$$(1,0)$$$, and are terminated by $$$(0,0)$$$ or another $$$(1,1)$$$.

    suppose we will place $$$x$$$ chains of carries, where $$$1 \leq x \leq k$$$. we will place $$$x$$$ of $$$(1,1)$$$ and $$$k - x$$$ of $$$(0,1)$$$ or $$$(1,0)$$$ that will continue these chains. we have $$$2$$$ characters to choose for each of the continuations, and we must place these $$$k-x$$$ items into one of $$$x$$$ groups, so there are $$$2^{k-x}\binom{k - 1}{x - 1}$$$ to make this assignment.

    now, for each of these $$$x$$$ chains, either it will be terminated by a $$$(0,0)$$$ or by the $$$(1,1)$$$ that starts the next chain. let's manually terminate $$$y \leq \min(x, n-k)$$$ chains with $$$(0,0)$$$. there are $$$\binom{x}{y}$$$ ways to place these.

    we have $$$n-k-y$$$ non-carry positions left to place. each of them can go in one of $$$y+1$$$ groups: either to the left of one of the $$$(0,0)$$$'s, or on the very right before any of the chains have begun. there are $$$3$$$ legal characters for these: $$$(0,0)$$$, $$$(0,1)$$$, and $$$(1,0)$$$. thus, we have $$$3^{n-k-y} \binom{n-k}{y}$$$ to fill in these last positions.

    our answer comes out to

    $$$\displaystyle \sum_{x=1}^{k} 2^{k-x}\binom{k - 1}{x - 1} \sum_{y=0}^{\min(x,n-k)} \binom{x}{y} 3^{n-k-y} \binom{n-k}{y} $$$

    from here, i brute forced my way though to the end using a convolution, so there is likely a more clever solution. nevertheless, i manipulated the equation with

    $$$\displaystyle \begin{align} & \sum_{x=1}^{k} 2^{k-x}\binom{k - 1}{x - 1} \sum_{y=0}^{\min(x,n-k)} \binom{x}{y} 3^{n-k-y} \binom{n-k}{y} \\ =& \sum_{x=1}^{k} 2^{k-x} \frac{(k-1)!}{(x-1)!(k-x)!} \sum_{y=0}^{\min(x,n-k)} \frac{x!}{y!(x-y)!} 3^{n-k-y} \frac{(n-k)!}{y!(n-k-y)!} \\ =& 2^k 3^{n-k} (k-1)! (n-k)! \sum_{x=1}^{k} \frac{x}{2^x(k-x)!} \sum_{y=0}^{\min(x,n-k)} \frac{1}{3^y y!^2(n-k-y)!} \cdot \frac{1}{(x-y)!} \\ =& 2^k 3^{n-k} (k-1)! (n-k)! \sum_{x=1}^{k} \frac{x}{2^x(k-x)!} \sum_{i+j=x,i \leq n-k, j \leq k} \frac{1}{3^i i!^2 (n-k-i)!} \cdot \frac{1}{j!} \end{align} $$$

    note that the inner summation is a convolution of two sequences $$$p$$$ and $$$q$$$, where

    $$$\displaystyle \begin{align} p_i &= \frac{1}{3^i i!^2 (n-k-i)!}, i \leq n-k \\ q_i &= \frac{1}{i!}, i \leq k \end{align} $$$

    precompute the inner summation with your convolution tool of choice in $$$O(n \log n)$$$, which allows us to compute the outer summation in $$$O(k)$$$.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to do D without breaking out the arbitrary mod FFT/NTT?

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

    I got to the following formula:

    $$$\sum_{i=1}^{min(k,n/2)} \binom{n-k}{i} \binom{k-1}{k-i} 3^{n-(2 i)}+ \sum_{i=0}^{min(k-1,(n-1)/2)} \binom{n-k}{i} \binom{k-1}{k-1-i} 3^{n-1-(2 i)},$$$

    where $$$i$$$ is the number of blocks of consecutive carries (11 followed by 11,10 or 01 any number of times, ended by 00). The binomial coefficients count the placement of these blocks within the n bits. The second sum accounts for the case when the last block is not ended by 00.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Root idea
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I could think of this during the contest, than my idea came out to be that we want to divide a block of size n + 1 into f different blocks of size >= 1, f = n + 1 — k as the root idea is a block of size k + 1 dimineshes it into k, its true for all k >= 0, so we need size of k + 1 >= 0

      I think somewhere in the middle i started to think too much and it all became a mess but can you explain how to move ahead after this, or what is wrong in my approach

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

        Let's consider i blocks with sum lengths of all blocks being k, then there are two cases

        • Last block at the end.
        • The last block is not at the end
»
2 months ago, # |
  Vote: I like it -21 Vote: I do not like it

I demand the castration of the authors of this round!!!

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

GREAT ROUND, How to solve Problem C? and can anybody prove why answer always exists?

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

    It doesn’t. The checker guarantees that the answer exists for all testcases.

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    The answer does NOT always exist. The problem specifically implies this. However, the problem guarantees that an answer must exist for each test case, so you don't have to worry about these no-answer scenarios.

    A simple counterexample is when every row has at least one 1. Since there is no all-zero row, this means every set is a proper subset of another set, which must lead to a cycle of proper subset chains, so each set in this cycle is a proper subset of itself, which is impossible.

    Anyway, my answer was to enforce a rule that the number $$$i$$$ will only appear exactly in set $$$i$$$ and its proper subsets. I'll refer to $$$i$$$ as the ID of set $$$i$$$. This fulfills the three conditions:

    1. Sets are non-empty (must contain its ID) and values are from $$$1$$$ to $$$n$$$ (all IDs are from $$$1$$$ to $$$n$$$, and no other values are considered).

    2. All sets are distinct, because if we consider any pair of sets, they cannot both be proper subsets of each other (this leads to a contradiction as I mentioned above), so the one that isn't a proper subset will lack the ID of the other.

    3. Binary Matrix representing proper subsets is proven by how we construct the sets: for row $$$i$$$ of the matrix, we add the ID $$$i$$$ to each column $$$j$$$ for which $$$b_{i, j} = 1$$$. This fulfills the third condition, while also following the ID rule.

    My submission: 181766895

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C:

what should be the answer for this test case:

1
4
0001
0010
0001
0000
»
2 months ago, # |
  Vote: I like it -17 Vote: I do not like it

B and C were pretty "sucky sucky" problems.

»
2 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Hopefully I lose enough rating to do tomorrow's Div 4 contest

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem E, if there is a component which contains a cycle, how do we determine the minimum non-zero number of operations that can be performed on it such that the component remains connected?

I realized that the answer is $$$|C_u|$$$ if $$$C_u$$$ is complete, and 1 if $$$C_u$$$ is acyclic but not complete, but I couldn't figure out the solution for general graphs. Can anyone provide a hint on how to solve this general case, or at least let me know whether there is an easier alternative approach for solving E?

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I have thought of this solution:

    1. Let's think the graph is not connected.

    2. Let's think there is no single vertex, else we could invert its edges.

    3. If there is a connected component that is not complete, let's invert the edges of one its vertex that is not a joint and is not connected to all vertices of the component. Then it will be connected to at least one of the other vertices and the other vertices themselves will be connected together. Note that if there is a vertex of the component that is connected to every other vertex, the other vertices are all not joints, and if there is none, the leaves of the DFS tree still are all not joints.

    4. If all the components are complete, there are either two components or more.

    5. One possible answer is to invert all the vertices of any component.

    6. There is another way to do it if there are >= 3 components. We can see that if we invert a vertex in each of some two components, the graph will be connected. (Note that after we invert some vertices, the not inverted vertices of each component will be connected together and the inverted vertices of each component will also be connected together and also with the not inverted vertices of other components.)

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

      I understand that if there is a degree-1 vertex in a component with $$$\geq 3$$$ edges, then this vertex alone is enough. But there is a broad set of graphs for which no vertex has degree-1, but the graph is also not complete. Inverting all vertices in this component might not be optimal (which pretest 4 thankfully demonstrates), so how do we determine the optimal number? Is there some clever way of choosing which vertices to invert that leads to an optimal solution?

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Spent more than half of contest trying to figure out amount of ways to choose t blocks of k elements from n positions and didn't seem to succeed(problem D). How to solve it?

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

    First N choose t for the places, then for the sizes, we have t integers summing up to K, each must be greater than 1, it's a case of bars and stars.

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

      Thanks! But shouldn't we take care about cases where for example n=5 last block is at position 3 and it's size more than two(0-indexed)?

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

        The way I imagined the places, was rather than based on a fixed position, based on insertion between blocks of n-k integers. As in, if we have n-k integers and we need to place t blocks of a total of k between them, we have n-k+1 possible places a block.

»
2 months ago, # |
  Vote: I like it +30 Vote: I do not like it

In problem G, the time limit seems not to be enough to make the allowed number of queries interactively.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm wondering if there will be an editorial for this.

»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

dalbaiob

»
2 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Can problem $$$D$$$ be solved using $$$DP$$$ and matrix exponentiation trick to optimize the $$$DP$$$ to not end up in a complexity of $$$O(N\cdot K)$$$?

If so, how can we use matrix exponentiation in this case?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    In fact we can solve the bonus of D with DP, but need some hard knowledge. :(

    You will see it in the tutorial soon.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve E? because I don't get what's wrong with my code

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    I don't know your approach, but here is a counterexample: graph with two components A-B-C and D-E-F, both paths. The answer should be 1, because if you apply the operation on any vertex other than B or E, the graph becomes connected. The test-case format is:

    6
    010000
    101000
    010000
    000010
    000101
    000010
    

    More generally, if there is a connected component with at least 3 vertices and at least one vertex has degree-1 (which is always true for a tree btw), then choosing this vertex would always be sufficient. It will connect to all other components, and although it loses an edge with its neighbor, it will gain edges to the other neighbors of this neighbor, so connectivity within its own component is preserved.

    (I didn't solve E btw, but this particular subcase I was able to establish)

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Penalties for wrong submissions are killing me. And it's not just in this contest, but in almost every contest I participate in. Last 6 contests: 15 wrong submissions of which 9 are in last 2 contests...

Any advice on how to have mental energy to spend extra few minutes checking if the solution is actually correct?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D?

»
2 months ago, # |
  Vote: I like it +35 Vote: I do not like it

A really huge gap between C and D.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is C is to hard or I'm just a rookie ?

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

    if (User.rating <= 1300) { cout << "ROOKIE\n"; } else cout << "HARD\n";

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

FSTforces.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

If anyone is curious, my take on

F1 and F2
  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    But for those wondering, the next part of the solution is along the lines of:

    this
»
2 months ago, # |
  Vote: I like it -43 Vote: I do not like it

shitty fucking contest im crying so hard!!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone help me.....What is the output for this test case in problem B.

14 1 2 3 2 1 2 1 2 1 2 1 2 1 2

If it give answer n ? how it is work ?

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

    Answer will be n (Size of the vector) which is 15 here! For cases like a,b,a,b...the answer is (n/2)+1 and otherwise it'll be n because we can choose the number next to the different number and delete it without causing two equal numbers becoming adjacent to each other (Since initially no two equal numbers are adjacent)

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

      first one (14) is the number of element. But why?? maxxi can chose any element and delete it. if I delete first element 2(i=2) and 2(i=n) will be adjacent. again chose 3(i=3) again 2(i=2) and 2(i=4) will be adjacent. So, Why we get answer 14 for this test case??

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

    remove 14 then 2 next to 3 then 1 next to 3 and so on until everything is removed

»
2 months ago, # |
  Vote: I like it +136 Vote: I do not like it

ALL of the following simultaneously being true for problem D is pretty infuriating:

  • 1s time limit for no good reason
  • Test 30 not in pretests
  • The fact that n*log(n) on n=1e6 TLEs in Java
  • The fact that this TLE on system tests is not something anyone would ever think to hack

:(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A speed-round for contestants who didn't solve D

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D is a problem of distributing 1s into blocks, which is easy.

how do you do the case for distributing 0s? The first 0 of each block has to be both 0, and other 0s has 3 ways to get it

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

stupid e

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

Why is my solution getting WA for problem E?

My Logic:

  1. Find all connected components. If the number of connected components = 1 then return 0
  2. For each component, I will check if it is strongly connected. If it is not strongly connected then the answer is 1, because we can choose a node in this component then it will still remain connected after 1 operation and also it will get connected to all other components.
  3. Now we are left with all strongly connected components.
  4. If the number of strongly connected components is> 2 then the answer is 2 because after one operation we get to the same situation as the second point.
  5. Else (no. of comps ==2) then anser is minimum size of two components.

Please correct me if my approach is not correct.

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it +10 Vote: I do not like it

    First of all, the graphs are undirected, so every connected component is "strongly connected". I don't understand how you arrived at Steps 4 or 5, but neither are correct.

    Counterexample for Steps 4 and 5: consider two or more trees (a component with no cycles within it) of say, size 50 each. Then the optimal answer is 1. Just pick any leaf (degree-1 vertex); the operation will connect it to all other trees, and although it loses the edge to its parent, it gains an edge to its grandparent, so it is still connected to its parent and all other nodes in its tree.

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

      Sorry I meant "complete components" instead of Strongly connected.

      I just realized step 4 is wrong.

      But step 5 is still correct because in the counter-example you have given a tree that is not a complete component. So the answer is 1 from step 2.

      I still claim that my approach is correct ignoring step 4.

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    You missed a case in step 2. Consider the following example:

    1
    6
    011100
    100000
    100000
    100010
    000100
    000000
    

    Your solution will operate on node 1, but it will not make the graph connected.

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

    Your solution is (almost) correct, look at test 4 to find error in logic. I one-line-fixed your solution: 181807261

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

      From guitarhero_0221 's comment test case, I realized that we can't directly remove any node from the non-complete-component. We should first check if removing a node from this component still preserve the connections between other nodes in the same component.

      But, why does reversing the component fix the solution?

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

        Unlike first vertex, last vertex in dfs order will never break condition "check if removing a node from this component still preserve the connections between other nodes in the same component". This vertex will be one of the leaves or vertex on some cycle.
        I fell into this trap too. And could not understand this until I saw test above. Tourist solves this "issue" by taking last vertex of bfs order if all vertices are not connected to each other

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

          Wow, thanks a lot. I understood it. Also I was thinking instead of reversing( or getting the last vertex of bfs) we could sort the nodes in each component based on the degree of that node. Will this work?

          Upd : Yea Its working, Thank you Igorjan94 :)

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

            Yes. This way we will get leaves first (or if there is no leaves we don't care at all about order and can use any vertex)

»
2 months ago, # |
  Vote: I like it +114 Vote: I do not like it

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

Seems like this solution of mine for B is similar to editorial. May I know a testcase where it'd be WA?

submission

Thank you in advance!

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

    When n <= 3 you don't read the rest of the input

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

why this is wrong for the first test case ?! 3 1 2 3 1 1 2 1 2 4 1 2 3 4 1 1 2 1 2 3 1 2 3

»
2 months ago, # |
  Vote: I like it +67 Vote: I do not like it

Congratulations to dorijanlendvaj for reaching LGM with a 2nd place finish!

»
2 months ago, # |
Rev. 3   Vote: I like it -41 Vote: I do not like it

Can somebody please check where my toposort solution of C is wrong

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define f(i,k) for(int (i)=0;(i)<(k);i++)
void findTopoSort(int node, vector < int > & vis, stack < int > & st, vector < int > adj[]) {
    vis[node] = 1;
 
    for (auto it: adj[node]) {
      if (!vis[it]) {
        findTopoSort(it, vis, st, adj);
      }
    }
    st.push(node);
  }
 
 vector < int > topoSort(int N, vector < int > adj[]) {
      stack < int > st;
      vector < int > vis(N, 0);
      for (int i = 0; i < N; i++) {
        if (vis[i] == 0) {
          findTopoSort(i, vis, st, adj);
        }
      }
      vector < int > topo;
      while (!st.empty()) {
        topo.push_back(st.top());
        st.pop();
      }
      return topo;
 
    }


int main(){
    
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        vector<string>a(n);
        f(i,n)
        {
            cin>>a[i];
        }
        vector<int>adj[n+1];
        f(i,n)
        {
            f(j,n)
            {
                if(a[i][j]=='1')adj[i].push_back(j);
            }
        }
        vector<int>lvl = topoSort(n,adj);
        map<int,int>mp;
        f(i,lvl.size())
        {
            mp[lvl[i]+1]=i+1;
        }
 
        for(auto it:mp)
        {
            cout<<it.second<<' ';
            for(int j=1;j<=it.second;j++)
                cout<<j<<" ";
            cout<<endl;
        }
    }
    return 0;
}
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    put your full code in ideone , we don't know what the "topoSort" does

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

        The solution is wrong because of this part of the problem statement: "In other words, bi,j is 1 if Ai is a proper subset of Aj and 0 otherwise.".

        Also if you get WA on pretest 1 (the samples from the problem statement), then you can look at the failure details even during the contest and the checker says "wrong answer Not meet the requirements of b_{3,1} (test case 1)". I made exactly the same mistake in my initial submission: 181794076

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem B i'am not able to think of any approach due to circular array term getting confused each time a small hint to the problem will be a great help

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

as contester go on and do more rounds

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

Really liked problem E. Thank for authors of contest!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my solution getting WA for problem E? sorry for my bad english and thank you in advance https://codeforces.com/contest/1761/submission/181809468

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem B . my approach was i would check for every index if( index && index+2 are equal ) i'd increment a duplicate variable by 1 . for n-2, n-1 th index i'd check with 0 , 1 index. if duplicate == n . ans == n/2+1
else ans = n.

why wouldn't this work

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

500 delta and 250 comments! So, 500/250 = 2; we want 2nd round in near future!

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

My solutions (video):

A. Two Permutations

Solution

B. Elimination of a Ring

Solution

C. Set Construction

Solution

D. Carry Bit

Solution
»
2 months ago, # |
  Vote: I like it -84 Vote: I do not like it

Trash problem E, if use cin or scanf("%1d",&x) will get TLE.Meaningless.

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

    Try C++20. It's faster.

    btw after the contest, plenty of my classmates were complaining about this meaningless TLE in problem E.

    Extremely thankful for this. Skill issue? maybe :(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice round, i like b, d, e!

although im still annoyed at myself for accidentally printing n^3 on the k=0 case instead of 3^n LOL

its worse when the one sample with k=0 had n=3 XD

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally became pupil. Please suggest how can I be a specialist? What things should I learn. I am not doing well with DP.Can I become a specialist without using DP?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial link is made private. I can't open it.

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

(

)
»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hey Everyone , This is My Code for C ,but i got wrong on test 2 but don't know why?

my approach is :) - i am applying DFS in PROBLEM C assume like directed tree
- i is subset of j then we can say that j is ancestor of i - we got a adjacency list from given matrix

then we set of parent = set of parent + set of its all sons please go through my code ,

please give any counter cases where the code is falling , is there anything i missed?

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

I deeply love this contest. But the data in problem B is a little bit weak.

My program passed the final test but it uses the wrong initialization.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First comment as specialist ! :)

Round was really good for me than usual

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

TLE with std::cin for std::string in problem E is sad. :( I usually use scanf/printf for everything except strings, but here is an example where it may screw you, so you either should use char* with scanf or ios_base::sync_with_stdio(0) and your lovely cin/cout...

»
2 months ago, # |
  Vote: I like it -18 Vote: I do not like it

It would be nice to finally fix language selector issue and remove excessive use of flags.

Sources with supporting arguments:

Codeforces Language Picker -- chrome extension to see how fixed codeforces language picker would look like.

Please support the initiative and stop reinforcing poor UX practices.

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I really enjoyed this one, I'm a big fan of dX!! Although I didn't play this game, I like E and D very much. Personally, I think the difficulty of E is much less than that of D. It may also be my math problem.

»
2 months ago, # |
  Vote: I like it -9 Vote: I do not like it

I have been wrongly accused of copying the code. Both the codes are quite different and any similarity is just a coincidence. I use codechef ide for writing programs which is not public and hence the question of copying the codes cannot arise. I request you to not to mark my submissions for these two questions as invalid. I don't copy code and compete with full honesty.

This is regarding these two messages I received:

Attention!

Your solution 181793513 for the problem 1761C significantly coincides with solutions Nighthe/181764653, suryansh_2003/181793513. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

Attention!

Your solution 181762172 for the problem 1761B significantly coincides with solutions Nighthe/181756764, suryansh_2003/181762172. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

jayanth777/181777290 (mine)

KaranBardhan/181760840 was flagged for cheating .

i dont know the other guy. it was coincidence . how to prove this

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Congratulations to hoodie winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_tshirts.py
randgen.cpp
List place Contest Rank Name
1 1761 1 tourist
2 1761 2 dorijanlendvaj
3 1761 3 mnbvmar
4 1761 4 fivedemands
5 1761 5 Benq
6 1761 6 jiangly
7 1761 7 maroonrk
8 1761 8 inaFSTream
9 1761 9 hitonanode
10 1761 10 gisp_zjz
11 1761 11 ksun48
12 1761 12 BurnedChicken
13 1761 13 noimi
14 1761 14 TheQueenOfHatred
15 1761 15 ugly2333
16 1761 16 tranquility
17 1761 17 fallleaves07
18 1761 18 Maksim1744
19 1761 19 ecnerwala
20 1761 20 wangziji
21 1761 21 tabr
22 1761 22 WYZFL
23 1761 23 353cerega
24 1761 24 nantf
25 1761 25 Vercingetorix
26 1761 26 Egor
27 1761 26 Nyaan
28 1761 28 SSRS_
29 1761 29 Magpie_
30 1761 30 suyiheng
55 1761 55 Little99
57 1761 57 Tlatoani
63 1761 63 fengzhengwei
81 1761 80 kmjp
84 1761 84 oleh1421
85 1761 85 Jimanbanashi
88 1761 88 acceptedzhs
95 1761 95 TrivialMan
97 1761 97 Ayanami_desu
99 1761 99 Everule