Pinely Round 1 (Div. 1 + Div. 2)
By pigstd, 2 years 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 [email protected] 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

Comments Comments (223)
| Write comment?
»
2 years 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).

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

    Where is fyy Memorial Valley School

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

    .
    → Reply
    • »
      »
      »
      2 years 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. :(

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

        i am agree with him

        → Reply
      • »
        »
        »
        »
        2 years 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. :(

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

All hail our emperor anton

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

orzdevinwang orz

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

As a tester, i'd say

guess
→ Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Anime round is coming :|

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

As a tester, I'm cute (｡･ω･｡)ﾉ♡

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

pigstd orz

→ Reply
»
2 years 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!

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

Who is she?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years 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 ?

→ Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years 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.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it hard?

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

    Maybe hard I think.

    → Reply
    • »
      »
      »
      2 years 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!

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

What a cute blog ._.

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

She is so cute!

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

Looks like a good contest, good luck everyone!

→ Reply
»
2 years 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

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

happy world cup day

→ Reply
»
2 years ago, # |
  Vote: I like it -40 Vote: I do not like it

Stop putting otaku images in codeforces!

→ Reply
  • »
    »
    2 years 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

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

is pigstd a girl? pigstd

→ Reply
  • »
    »
    2 years 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.

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

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

    → Reply
  • »
    »
    2 years 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.

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

    It depends on your imagination :).

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

Hopefully I can hit 500+ this round :)

→ Reply
»
2 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Rated?

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

The problems are very nice, recommend participating.

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

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

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

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

    Don't worry :)

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

dXqwq orz

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

orz

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

I hope I can be red this time!

→ Reply
»
2 years ago, # |
  Vote: I like it -16 Vote: I do not like it

is this rated?

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

Great progress on the announcement

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

CF plus World Cup night！

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

All hail our emperor Anton :)

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years 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 ^,^

→ Reply
»
2 years 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? :/

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

How young is orzdevinwang?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck everyone !

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

Weebs Get a life

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

EZEC-chan is so cute！

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

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

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

Is pigstd really a girl?

→ Reply
»
2 years 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

→ Reply
»
2 years 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

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

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

→ Reply
»
2 years 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.

→ Reply
»
2 years 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. :(

→ Reply
  • »
    »
    2 years 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.

    → Reply
    • »
      »
      »
      2 years 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).

      → Reply
      • »
        »
        »
        »
        2 years 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.

        → Reply
    • »
      »
      »
      2 years 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)

      → Reply
      • »
        »
        »
        »
        2 years 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.

        → Reply
        • »
          »
          »
          »
          »
          2 years 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.

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

How to solve D?

→ Reply
  • »
    »
    2 years 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)$$$.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years 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.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Root idea
    → Reply
    • »
      »
      »
      2 years 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

      → Reply
      • »
        »
        »
        »
        2 years 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
        → Reply
»
2 years 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?

→ Reply
  • »
    »
    2 years 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.

    → Reply
  • »
    »
    2 years 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

    → Reply
»
2 years 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
→ Reply
»
2 years ago, # |
  Vote: I like it -17 Vote: I do not like it

B and C were pretty "sucky sucky" problems.

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

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

→ Reply
»
2 years 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?

→ Reply
  • »
    »
    2 years 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.)

    → Reply
    • »
      »
      »
      2 years 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?

      → Reply
»
2 years 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?

→ Reply
  • »
    »
    2 years 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.

    → Reply
    • »
      »
      »
      2 years 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)?

      → Reply
      • »
        »
        »
        »
        2 years 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.

        → Reply
»
2 years 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.

→ Reply
»
2 years ago, # |
  Vote: I like it -6 Vote: I do not like it

dalbaiob

→ Reply
»
2 years 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?

→ Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years 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

→ Reply
  • »
    »
    2 years 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)

    → Reply
»
2 years 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?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D?

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

A really huge gap between C and D.

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

How to solve E ?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

FSTforces.

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

If anyone is curious, my take on

F1 and F2
→ Reply
  • »
    »
    2 years 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
    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it

.

→ Reply
»
2 years 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 ?

→ Reply
  • »
    »
    2 years 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

    → Reply
»
2 years 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

:(

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years 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

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

stupid e

→ Reply
»
2 years 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.

→ Reply
  • »
    »
    2 years 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.

    → Reply
  • »
    »
    2 years 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

    → Reply
    • »
      »
      »
      2 years 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?

      → Reply
      • »
        »
        »
        »
        2 years 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

        → Reply
        • »
          »
          »
          »
          »
          2 years 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 :)

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years 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)

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

→ Reply
»
2 years 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!

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

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

    → Reply
»
2 years 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

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

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

→ Reply
»
2 years 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;
}
→ Reply
  • »
    »
    2 years 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

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

      Submission

      → Reply
      • »
        »
        »
        »
        2 years 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

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

Really liked problem E. Thank for authors of contest!

→ Reply
»
2 years 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.net/contest/1761/submission/181809468

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

    Sir,please check MY CONTEST CODE OF C of PROBLEM C , i am applying the same APPROACH as you but got wrong on test 2 UNABLE TO FIND OUT WHAT IS WRONG IN MY CODE SINCE YESTERDAY

    → Reply
»
2 years 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.

→ Reply
  • »
    »
    2 years 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 :(

    → Reply
»
2 years 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

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

(

)
→ Reply
»
2 years 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?

→ Reply
»
2 years 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.

→ Reply
»
2 years 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...

→ Reply
»
2 years 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.

→ Reply
»
2 years 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.

→ Reply
»
2 years 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.net/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.net/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.

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

    Interesting how both your codes coincides with the same person (Nighthe).

    → Reply
»
23 months 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 Konijntje
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
→ Reply