Автор pigstd, 16 месяцев назад, По-английски

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:

  • Проголосовать: нравится
  • +590
  • Проголосовать: не нравится

»
16 месяцев назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Where is fyy Memorial Valley School

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +109 Проголосовать: не нравится

    .
    • »
      »
      »
      16 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится -89 Проголосовать: не нравится

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

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        i am agree with him

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +144 Проголосовать: не нравится

All hail our emperor anton

»
16 месяцев назад, # |
  Проголосовать: нравится +103 Проголосовать: не нравится
»
16 месяцев назад, # |
  Проголосовать: нравится +400 Проголосовать: не нравится

As a tester, i'd say

guess
»
16 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Anime round is coming :|

»
16 месяцев назад, # |
  Проголосовать: нравится +110 Проголосовать: не нравится

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

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

pigstd orz

»
16 месяцев назад, # |
  Проголосовать: нравится +62 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Who is she?

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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 ?

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    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.

»
16 месяцев назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it hard?

»
16 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What a cute blog ._.

»
16 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

She is so cute!

»
16 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Looks like a good contest, good luck everyone!

»
16 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

happy world cup day

»
16 месяцев назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится

Stop putting otaku images in codeforces!

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    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

»
16 месяцев назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

is pigstd a girl? pigstd

»
16 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Hopefully I can hit 500+ this round :)

»
16 месяцев назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Rated?

»
16 месяцев назад, # |
  Проголосовать: нравится +255 Проголосовать: не нравится

The problems are very nice, recommend participating.

»
16 месяцев назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

dXqwq orz

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

orz

»
16 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I hope I can be red this time!

»
16 месяцев назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

is this rated?

»
16 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Great progress on the announcement

»
16 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

CF plus World Cup night!

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

All hail our emperor Anton :)

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How young is orzdevinwang?

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

good luck everyone !

»
16 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Weebs Get a life

»
16 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

EZEC-chan is so cute!

»
16 месяцев назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Is pigstd really a girl?

»
16 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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.

»
16 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

        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.

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

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

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve D?

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    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.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Root idea
    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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
»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem C:

what should be the answer for this test case:

1
4
0001
0010
0001
0000
»
16 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

»
16 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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?

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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.

»
16 месяцев назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

dalbaiob

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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?

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится -34 Проголосовать: не нравится

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

    You will see it in the tutorial soon.

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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)

»
16 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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?

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve D?

»
16 месяцев назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

A really huge gap between C and D.

»
16 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve E ?

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

FSTforces.

»
16 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

If anyone is curious, my take on

F1 and F2
  • »
    »
    16 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

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

    this
»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится -43 Проголосовать: не нравится

.

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

»
16 месяцев назад, # |
  Проголосовать: нравится +136 Проголосовать: не нравится

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

:(

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

stupid e

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

    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.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            16 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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)

»
16 месяцев назад, # |
  Проголосовать: нравится +114 Проголосовать: не нравится

»
16 месяцев назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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!

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

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

»
16 месяцев назад, # |
Rev. 3   Проголосовать: нравится -41 Проголосовать: не нравится

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;
}
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Really liked problem E. Thank for authors of contest!

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

My solutions (video):

A. Two Permutations

Solution

B. Elimination of a Ring

Solution

C. Set Construction

Solution

D. Carry Bit

Solution
»
16 месяцев назад, # |
  Проголосовать: нравится -84 Проголосовать: не нравится

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

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

(

)
»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
16 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
16 месяцев назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

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.

»
16 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
16 месяцев назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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