By MikeMirzayanov, 5 years ago, translation, In English

This weekend, on Dec/14/2019 14:05 (Moscow time) we will hold Codeforces Round 606. It is based on problems of Technocup 2020 Elimination Round 4 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fit into this category, please register at Technocup 2020 website and take part in Technocup 2020 - Elimination Round 4.

Problem authors are me, Endagorion and voidmax. Many thanks to the testers: Kostroma, never_giveup, Supermagzzz, AdvancerMan, Stepavly, unreal.eugene, cannor147 and geranazavr555!

Div. 1 and Div.2 editions are open and rated for everyone. As usual, the statements will be provided in English and in Russian. Register and enjoy the contests!

Good luck on the round
MikeMirzayanov

UPD 1: The scoring:

  • D1: 500-1000-1250-2000-2250-3000
  • D2: 500-1000-1500-1500-2000-2500
  • Vote: I like it
  • +169
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +131 Vote: I do not like it

Looking forward to A1, A2, B1, B2, C1, C2, C3

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

What is happeninggggggg!!!!!
3 rated contests in 24 hours :3 :3

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

    Maybe that means some official div1 participants in div2 contest?

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

      I don't think that would happen. They must have left 2 hours gap between tomorrow's 2 contests, so that they can update ratings.

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

    Will the ratings be updated after finish of both of them or individually?

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

      Individually I guess. Otherwise, some div1 participants will end up participating in div2 contest

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

There will be 3 Rated contests in 24 hours, it will be a happy weekend !!!!! Thanks to the writers of these contests. :)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -41 Vote: I do not like it

    Unfortunately one of them clashes with my class time.

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

      All three having unusual starting time.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -14 Vote: I do not like it

        Thanks for reminding me so that i don't make a mistake like last div3 where i started 30 minutes late.

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

      There are three (3) contests in 24 hours and you're unhappy that one of them clashes with something else. People are really hard to please!

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Short notice for so many contests.

»
5 years ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

Tomorrow is a great day.. Make a contest..take 2 hours rest..Then again...Boom.. Feeling very much excited...

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

so many contest!!! I've been waiting a long time!!!

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

Flood of contests!

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

For those who may want to take part in both rounds.

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Two div1 contests in the weekend! Great!

»
5 years ago, # |
  Vote: I like it -30 Vote: I do not like it

Will jqdai0815 able to reach at the top position today?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -47 Vote: I do not like it

    Even if jqdai0815 overtakes Tourist today, tourist will be able to overtake him later. Also, a lot of Legendary Grand Masters like Radewoosh will compete. It is not as easy as you think!

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -42 Vote: I do not like it

      I know tourist will beat him in next contest. But today he hasn't registered till now. So I was curious about it :)

»
5 years ago, # |
Rev. 3   Vote: I like it +48 Vote: I do not like it

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

    Seems like your prediction was wrong. You got minus for only 606. Other two gave you positive rating.

»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

WTF there're so many contests in a row (in a column?)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the problem statements are short and clear.

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it -12 Vote: I do not like it

    I think problem with short statement are hard to solve compare to problem with long statement.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Scoring distribution?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Score distribution for the contest?

»
5 years ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

When Three contest starts at different time

There is still this issue.

»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

:D

»
5 years ago, # |
  Vote: I like it +39 Vote: I do not like it

There is a very long queue :(

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I can't submit, though I have registered? It says you have submitted exactly same code before, when I submit any code, though there is no submission in my submissions or standing. Why? I tried to submit by editing my code. It is same.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

RIP queue

»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

queueforces right now

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Such a long queue. This round should be unrated.

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

    Queue finished. And there was many queue in some of the previous rounds but that rounds doesn't become unrated so this round should be rated because the only worst thing is queue.(There isn't any problem...)

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

      I submitted solution for problem A, then about 9 minutes later it gives WA. Then I submitted problem B solution, it took 11 minutes to show verdict AC. People who submitted earlier didn't face that problem I guess. So, how is that fair?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -19 Vote: I do not like it

        I know but in previous rounds it doesn't be unrated for long queue. So i think this contest should be unrated too.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        Even if it's annoying, it's "fair" in a sense that the guy who submitted earlier was rewarded for his speed.

»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Probably it should be good to close gym during online rounds.

»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve B without building tree of biconnected components?

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +85 Vote: I do not like it

    DFS from $$$a$$$ without going past $$$b$$$, call the set of reached vertices $$$r_a$$$, and DFS from $$$b$$$ without going past $$$a$$$, call this set of reached vertices $$$r_b$$$. The answer should be $$$|r_a \setminus r_b|*|r_b \setminus r_a|$$$.

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

      I did the same. Can you please tell how can we solve it by building tree of biconnected components?

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

      I did the same, got TLEd

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +16 Vote: I do not like it

        Did you use memset?

        If you use a memset on an array like vis[200005] on each testcase... Then as the constraints says, there can be a testcase with 40000 sub-tests.

        2e5*4e4=8e9... Then you will surely get a TLE.

        generator:

        #include<cstdio>
        int main()
        {
        	freopen("1.in","w",stdout);
        	register int i;
        	puts("40000");
        	for(i=1;i<=40000;i++)
        	{
        		puts("5 5 1 4\n1 2\n1 3\n1 4\n4 5\n2 3\n");
        	}
        }
        

        UPD: There is a mistake in my generator. Fixed.

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

          Oh man, you're right. I'm creating a vector array of size 2e5 for every test. resubmitted and got AC. Daaang this could've been my first time solving an E in a contest.

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

      Is it true that the common of ra and rb are the vertices that lie one at least one path between a and b? So we can use this to find all vertices that lie to at least one path between vertexes a and b in a graph?

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

        We can't (if you mean simple path). a = 1, b = 3, but 4 doesn't lie on the path from 1 to 3.

        1--2--3
           |
           4
        
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Right so is there a solution to this?

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

            If you're asking about how to solve the problem "given an undirected graph $$$G$$$ and two vertices $$$a$$$ and $$$b$$$, find all $$$v$$$ such that there exists a simple path from $$$a$$$ to $$$b$$$ containing $$$v$$$", I thought about it for a bit and here's what I came up with:

            Note that for a tree the answer is trivial; there is only one path from $$$a$$$ to $$$b$$$, so all the vertices from that path must be the answer. Now, for a general undirected graph, we decompose it into the biconnected components tree, and now there exists a path of blocks and cut vertices from $$$a$$$ to $$$b$$$ in our BCC tree, and we take all of the vertices in those blocks and the cut vertices on the path and that should be our answer. I don't know if there's a solution with a simpler algorithm, but I couldn't think of one.

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

    It seems that the answer is $$$(\text{No. of vertex not reachable by 'a' without going through 'b'}) \cdot (\text{No. of vertex not reachable by 'b' without going through 'a'})$$$

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

      I'm so stupid. :(

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

      Yeah... After the contest I realized that it is correct:

      Define three subsets of the n-2 vertices except a and b:

      A={Ai} be the subset of the vertices which can only reach a without passing through a and b;

      B={Bi} be the subset of the vertices which can only reach b without passing through a and b;

      C={Ci} be the subset of the vertices which can reach both a and b without passing through a and b.

      It's obvious that these sets contains all the n-2 vertices and the three sets have none in common. (Since the graph is connected there shouldn't be a point that can't go to both a and b.)

      For each unordered pair (x,y) (x!=y):

      1)x and y both belong to A. Then there is a path x-...-y don't contain b.

      (Both x and y can reach a without passing through b)

      2)x and y both belong to B. Then there is a path x-...-y don't contain a.

      (Both x and y can reach b without passing through a)

      3)x belongs to C. Like 1) and 2), the path needn't contain both a and b.

      If y belongs to A or C the situation is similar to 1).

      If y belongs to B the situation is similar to 2).

      4)x belong to A and y belong to B. then x can't reach y without passing through a or b.

      Otherwise:

      If a is not on a valid path x to y, then x-...-y-...-b should not contain a (Since y belongs to B). Then according to the definition of B, x belongs to B.

      If b is not on a valid path x to y, then y-...-x-...-a should not contain b (Since x belongs to A). Then according to the definition of A, y belongs to A.

      Both two suppositions lead to conflictions.

      so the answer is |A|*|B|.

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

        Can you please explain it more.

        Explain with this example.

        I have graph with 11 nodes. Consider 10th node as a and 11th node as b.

        Now edges are:


        1-a 2-a 3-a a-4 a-5 a-6 4-b 5-b 6-b b-7 b-8 b-9

        According to your explanation:

        A = [1,2,3]

        B = [7,8,9]

        C = [4,5,6]

        So the answer must be |A|*|B| = 3*3 = 9.

        But my question is why we aren't considering the path 1-a-4-b-5 as valid?

        I know you have written last two lines regarding this but still I am not getting.

        Please help me out.

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

          For the solution 1-a-4-b-5...

          It doesn't prove that all the paths from 1 to 5 pass through a and b.

          Simply we can find another path 1-a-5 proving that the pair (1,5) is invalid.

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

            Ok so we need to find pairs x,y such that all paths from x to y must contain a and b. But in question it was written that find pairs x,y such that any path from x to y must contain a and b.

            Please clarify this.

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

              I wonder what is different between those two statements. :(

              Logically, "all the things are" equals to "any of the things is", I think.

              P.S. Maybe you understood the problem as "Find pairs x,y such that there exists a simple path from x to y that contains a and b"?

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    Run two DFS from a and b individually ignoring b and a respectfully and save the visited nodes in two sets. Now, we have to delete the commonly visited nodes from the two sets. Then, the answer will be the multiplication of the size of these two sets.

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

    Find connected components of the graph without $$$a$$$ and $$$b$$$. Then for each component, determine whether it is adjacent to $$$a$$$, $$$b$$$, or both. The answer is the product of (sums of sizes of components adjacent to $$$a$$$ only) and (sums of sizes of components adjacent to $$$b$$$ only).

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

    My approach was bit different. I did it by doing dfs from a. Find the sum of size of subtree of b's children in dfs tree from which there is no back edge above b. Now, multiply it by (n — (Size of subtree of a's child which contains b) — 1).

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

    I made two dominator trees, using a and b as roots. The answer is: ((size of subtree b on first tree) -1) * ((size of subtree a on second tree) -1)

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    Another way to find it:

    Run a dfs from A and as soon as you reach a vertex (and it's not visited), add it to cnt. If you reach B, add it to cnt but do not move forward. It's obvious that n — cnt is equal to the nodes that are not reachable by A if we disconnect B.

    Do the same from B and you'll find the nodes that are not reachable from B if we disconnect A. Now, if we get 1 node from cntA and 1 from cntB, we can see that the only way to connect them would be to pass through both A and B. Hence, it's a valid answer!

    So, if we multiply cntA and cntB, we get the answer! :)

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

    Can anyone tell me why my solution is wrong? 66888589

    My approach was as follows :-

    Remove all the edges from and to b, then count the number of nodes which can't be visited through dfs from a, since these nodes could be visited by adding the edges of b, this simply means that any path from a to these nodes passes through b. Count this number and let it be A.

    Do the same after swapping a and b. Let the new number be B.

    Then the answer should be A*B, this fails testcase 18 :(

    UPD :- Nevermind, I messed up ll and int, fuck my life

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Too many query problem resulted in too long queue. :(

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any particular edge cases on Div1 C? Failed on pretest 48 :/

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    Check when shortest side is greater than the biggest number of duplicates.

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

One of my best contests ever. Thank you Endagorion.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    CF-Predictor is predicting you're going green :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is testcase 3 in Div2C

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

    Try "ttwoonee" For me this was the case.

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

      is answer 2 3 6 acceptable?

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

        Yes

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

          Thanks BTW for your time.

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

            Does your solution pass this case?

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

              The answer is

              2
              3 6
              

              in my machine Does it matches with your answer

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

                I see your code in comment below. I think "twone" is making both f2 and f3 true in your code which makes an issue here. As it match both with "two" and "twone" starting from t. I hope using else will solve your problem.

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

                And why are you trying to match "twon"?

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

        t##oo#ee Your answer should be correct

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

          Not t##oo#ee it's tt#oo#ee. Here 2 is no of index and 3 and 6 are index.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain Div2 D?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div1C did the authors want an O(n sqrt(n)) solution to pass, or not?

If "yes", then why set TL to 1 second, isn't it right on the edge? Would the problem be spoiled by 2 or 3 second TL?

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

    it can be solved in O(nlog(n)) but still 800 ms for me ...

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

    It's easy to improve $$$O(n \sqrt{n})$$$ solution to $$$O(n\log(n))$$$ with 2 pointers.

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

      Yep, I did it as well, took like 4 lines of code. Thanks :)

      My question is not how to do it, but whether authors thought about it, or just decided on a 1 second TL by default.

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

        Actually, my question to the public is: Did your fast and furious C++ O(n sqrt(n)) solution pass successfully?

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

          Yes — 66860664

          Let's say the size of the compressed input array is m. Then the submission with O(n log(n)) (sort the original array) + O(m log(m)) (sort the compressed array) + O(m sqrt(n)) ≈ O(n sqrt(n)) passes in 0.5s.

          Sometimes you may spend a lot of time making a very efficient code just to be bypassed by someone with a bruteforce approach.

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

        I think author set 1 second, cause it can be done in O(n). my solution pass pretest about 200ms.

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

      what is the O(nsqrt(n)) solution ?

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

        Compress the array, and then for i = 1..sqrt(n) find the amount of numbers such that for each a count(a) in input is no greater than i, thus for the current i you may have a rectangle with sides i, count(...) / i;

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    My solution has O(n) complexity :O Capped by the input tho. only took sqrt(n)*log^2(n) to binary search the grid. Upd : nvm. i got sort.

»
5 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Is it just me or was this round overkilled? I tried hard stuff but in the end, if I had a screencast, it would look like this.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Tell me, no one (especially me) is gonna fail in system test.

»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

THIS IS THE POWER OF CODEFORCES TO HOST MANY CONTESTS IN A ROW SALUTE CODEFORCES

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The true way to solve Technocup Elimination A,B,C(sometimes D) problems:

int main()
{
	int t;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		Evolution();
	}
	return 0;
}

Maybe it will help someone next year...

»
5 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Looks like the key to doing well in contests nowadays is having code snippets for everything.

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

    Can you elaborate? I did A,B,C without needing anything specific (unless my solutions fail).

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -58 Vote: I do not like it

      Did you not use biconnected components for B?

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

        i found B very easy .. just 2 dfs to check the component of each vertex in G-a and G-b ..

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

        Oh, I see. I just did a dfs on a and b, and broke the set of vertices reachable from each into different parts, and then multiplied those reachable by a but not b, and those reachable by b but not a. It probably is the same solution, but the code seemed short (I wrote it myself, didn't use some library code).

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain how to solve Div.2 D, please?

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

    Check the first and the last digit of each string. And you'll be able to classify them as [0~0], [0~1], [1~0], [1~1]. If the second and the third group are all empty, handle that case separately, otherwise regulate the size of the second and the third group properly.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Everyone is posting screenshot of list of contest to get UPVOTES .

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what are the edge cases in Div 2C

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

    Maybe this "twoooneeee"

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

      is the answer

      2
      2 6
      

      acceptable?

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

        ok. now try "ooonee"

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

          my answer is

          1
          4
          
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            What about "oonnee"?

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

              answer 0

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

                Can you show me your code.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it -31 Vote: I do not like it
                  #include<bits/stdc++.h>
                  #define lli long long int
                  using namespace std;
                  lli mod= 1e9+7;
                  void solve()
                  {
                     string s;
                     cin>>s;
                     s+=".......";
                     lli ans=0;
                     vector<lli>pos;
                     lli n=s.size();
                     for(lli i=0;i<n;i++)
                     {
                     // cout<<i<<endl;
                        char x= s[i];
                        bool f1= false;
                        bool f2=false;
                        bool f3= false;
                        if(x=='o')
                       {
                         if(s[i+1]=='n' && s[i+2]=='e')
                          f1= true;
                       }
                        if(x=='t')
                       {
                         if(s[i+1]=='w' && s[i+2]=='o' && s[i+3]=='n' && s[i+4]=='e')
                          f3= true;
                       }
                         if(x=='t')
                       {
                         if(s[i+1]=='w' && s[i+2]=='o' && s[i+3]!='n')
                          f2= true;
                       }
                       if(f1==true)
                       {
                         ans++;
                         pos.push_back(i+2);
                         i+=2;
                       }
                        if(f2==true)
                       {
                         ans++;
                         pos.push_back(i+2);
                         i+=2;
                       }
                        if(f3==true)
                       {
                         ans++;
                         pos.push_back(i+2+1);
                         i+=4;
                       }
                     }
                     cout<<ans<<endl;
                     for(lli i=0;i<pos.size();i++)
                      cout<<pos[i]<<" ";
                  }
                  int main()
                  {
                      int t;
                      cin>>t;
                      while(t--)
                      {
                        solve();
                        cout<<endl;
                      }
                      return 0;
                  }
                  
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  Are you sure about s[n + 3]? Also, this scheme:

                  one->f1; twone->f2; twon->f3

                  is very strange.What to do with "twontwontwo"? You doesn't even look at "two" itself.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    1) two -> t#o 2) one -> o#e 3) twone -> tw#ne

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

      I tried the same but failed in TC 3

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

        Do you need my code? I was doing like this and it worked.

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

        the case you're looking for is probably twoone

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

          Thank you man, but none are correct. I think there is some kind of overflow of large value

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

            after you handle the case of twone, make sure you're advancing iterator by 3, otherwise it'll check the case of one after handling two. This was the case with me.

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

              I did the same and my solution passed two test case,

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

        I think "twone" is making both f2 and f3 true in your code which makes an issue here. As it match both with "two" and "twone" starting from t. I hope using else will solve your problem.

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

    There are none. No of indices are twone + (twone-one) + (twone-two).

    Remove allways the middle character of the match.

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

    if the string is "ooneee" , you should only delete 'n' not('o' or 'e') coz if you did you will get oneee or oonee (Invalid output)

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

      I did the same, unfortunately it's not working Thank BTW

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

        svkrdj I have the same problem with it. Could you find out the issue behind it? Please help me with it.

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

          try twontwontwo

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it
            3
            10 2 6
            

            This is the output given by my machine. What is the answer?

            PS: Can you please tell me what is in pretest 3, if possible?

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

              As there are multiple test case so there can be many things. For me it was "ttwoonee". Can you show your code?

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

                My code

                I've basically stored the starting indices of the substrings where, "one", "two", "twone" occur. And stored them in 3 vectors. And then removed characters accordingly.

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

                  Please add '\0' at the end off character array when you are using it as string.

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

                  But I guess it's not helping. What should I do? Where's the problem?

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

                  I added '\0' at the end of array as 'one\0', 'two\0', 'twone\0' and s[input.size()]='\0'

                  Don't forget to increase legnth of s by 1.

                  It got accepted for me then why not for you?

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

                  Thanks brother. AC now! Such small mistakes can do big blunders. Lost a lot of time due to it.

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

                  So many data structure in your solution. String,character array, integer array, vector, map. I have rarely seen such many data structure at a place. :p

»
5 years ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

.

»
5 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

I solved the idea for E quickly and was happy about it, but I kept getting wrong answer on test 3 :(

Isn't the solution: We check if both a and b are articulation points and then multiply the number of nodes on a's side(nodes that can be reached by a but not b) by the number of nodes on b's side?

UPD: Can anyone check what is the bug in my code? 66862954

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

    The idea is kinda seems correct, but it can be simplified by thinking it like:
    Answer = (n -Size of the component where 'a' is present after removing 'b' and its incident edges) * (n -Size of the component where 'b' is present after removing 'a' and its incident edges).
    This requires just 2 dfs's.
    You can find my submission here.

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

    Your idea is correct, but probably you have a bug in your implementation. Anyway, you can solve it much more easily, see here: https://mirror.codeforces.com/blog/entry/72120?#comment-564067 (I used a similar approach)

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

    I also get the idea for E quickly but i have no time to code.

»
5 years ago, # |
  Vote: I like it -25 Vote: I do not like it

when I saw A,B,C then --------->

But When I saw D&E,------------->

»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

How to solve Div1D?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +44 Vote: I do not like it

    We do subtree dp. For each vertex $$$v$$$ we calculate 3 dp values: when parent $$$p$$$ of $$$v$$$ is taken before we go through edge $$$(v, p)$$$, when $$$p$$$ is taken by edge $$$(v, p)$$$ and when $$$p$$$ is either taken after edge $$$(v, p)$$$ or never taken at all. To calculate it we go through edges incident to $$$v$$$ in sorted order and store intermediate dp for wether we have taken $$$v$$$ and $$$p$$$.

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

      Aren't the first two states the same, because they do not affect the token on v and the tokens in the subtrees? (Of course, the distinction is needed when descending to subtrees)

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

        In the first case when we pass through edge $$$(v, p)$$$ we do nothing and in the second case we have to take $$$p$$$(and in order to do that we must ensure that $$$v$$$ is not taken yet).

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

          Oh right. I was trying to do something similar with just 2 states, I guess that's why I couldn't solve the problem.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

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

    Run two DFS from a and b individually ignoring b and a respectfully and save the visited nodes in two sets. Now, we have to delete the commonly visited nodes from the two sets. Then, the answer will be the multiplication of the size of these two sets.

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

      Actually, we don't even need the sets. I did it in this way: my used[] has an integer type, and I exited DFS when I see a or b. Counted, how many vertices visited twice. Obviously, if used[V] == 2, then it has been visited by both APs. Then just subtracted this value from vA and vB, where vA — number of vertices, accessable from a, and vB — ... from b. The answer, as yours, multiplication of vA and vB.

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

Pretest 2 of Div2D ???

UPD : I think I found the case when both [0-0] and [1-1] type are present and I was handling this case seperately when abs( number of [0-1] — number of [1-0] ) will be even which was not required at all. After removing this part from the code, it passed perfectly.

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve Div1C? I figured that we can simulate the process for each rectangle height (at most sqrt(n)), but I couldn't do that in O(n).

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

    I also do the same, but consider only rectangles where height is smaller than or equal to width. Now consider that you don't need to simulate the process (except at the end). If you have a fixed height H, you know you can't take more than H samples from each number. So, with Fenwick tree, count the sum S of all numbers from which there are at most H samples. Then, count the number N of numbers which occur more than H times in the array. In the end, calculate S + H * N — this is the maximal amount of numbers you can get. You can then find the max. width you can have for height H.

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

      All my countercases to similar approach failed only when W < H, this is so simple, yet so effective! Thanks :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the announcement for problem D in the contest was titled "Problem E" ??

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

Can someone show me pretest 3 for DIV2 C please?

I can't figure out why it failed for me.

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

    Struggling for the same

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

      mine was wrong bcz I didn't consider string of single character(of length 1.) and I got runtime error...after taking this in care it passed. so u can check this.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any successful hacks in this contest? Strong pretests!!

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

In problem D there is a problem in the constraints!

It's written "The sum of word lengths doesn't exceed $$$4*10^6$$$" but the length of a single word isn't mentioned, so we should consider that the maximum length could be $$$4*10^6$$$. I submitted D at minute 46 (with setting $$$2*10^5$$$ the size of the char array) but before the end of the contest I noticed this problem and I changed the size of the array to $$$4*10^6$$$ and resubmitted.

Now after the contest I resubmitted the code that has only $$$2*10^5$$$ array size and it passed! This is totally unfair. You either should consider my first submission or modify the tests for all of the contestants.

UPD: Please look in it, it would give me 150 ranks up! Endagorion voidmax

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I almost missed it...Although I didn't get good results in it...

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Two rated contest within 4 hours of difference

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Not satisfied with the delay of submission verdict. Did a silly mistake and got WA on test 1 after 10 minutes.

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

For Div2 Problem C- "As simple as One and Two", an important test case is missing.

The test is repeated 'twone' and it will lead to TLE in some solutions.

Test generation in Python

print(10)
for _ in range(10): print('twone'*(3*(10**4)))

In my opinion, it should atleast be added to the testcases for those who try it in practice later so as to fully test correctness.

»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I BECAME THE PURPLE!!!!

»
5 years ago, # |
Rev. 3   Vote: I like it +26 Vote: I do not like it

For div1 E:

solution
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    Damn, not again... I'm not doing great at making testcases for this kind of problems, do I.

    Your solution seems to timeout on a case

    -1000000000 -499999999 0 500000001
    -750000000 -249999999 250000000 750000001
    
    • »
      »
      »
      5 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      What if I do 20 random moves in the beginning?

      UPD: Does not work.

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

        I'd expect a sufficient amount of fiddling should be enough to pass any given test.

        I really should have made this a multitest, seems so obvious in hindsight.

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

My Div1C code passed pretests (50+ tests). It failed the main tests (runtime error on test 33). I submitted same code again twice after contest. It passed both times! Why?! How?

Two consecutive ACs submitting same code after contest https://mirror.codeforces.com/contest/1276/submission/66875312 https://mirror.codeforces.com/contest/1276/submission/66875827

RE on main tests of in contest submission https://mirror.codeforces.com/contest/1276/submission/66867062

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

    Never mind, now that I had a look at pretests, it was a dumb out of bounds access.

»
5 years ago, # |
  Vote: I like it +65 Vote: I do not like it

Why can't we see others submissions and tests past samples?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anybody know why this code for Div 2 E failed?

Spoiler
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Answer can be > INT_MAX Use long long for final multiplication

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

    Is it wrong answer on pretest 18?

    There're at most 2*1e5 points, xx * yy may become 1e10 as a result, you may use long long to store it.

»
5 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Can you, please, open test's verdicts

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What was the idea for Div2 D?

»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Why submissions aren't visible?

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

Can someone explain why this solution is failing? 66858891

Edit: It fails in the case

1 t

But I still can't figure out why?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Please post the editorials

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain or provide a small case why this IEP based solution for E is wrong — 1. Add total pairs

  1. We subtract those pairs which are in same component after removing a — because they can be reached without a.

  2. Same as 2 but after removing b.

  3. We add those pairs which are in same component after removing both a and b because they are subtracted twice.

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

Why are the solutions not visible?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody see why does this code(div2 E) failed?

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

Can someone please explain the approach for DIV2 D and also the corner cases?

Thanks.

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

ConstructiveAlgorithmsForces

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

    Welcome to the russian contests

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why cant we see testcases?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2D and div2E?

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    Div2 D

    Notice that the only important thing is the first and last character of the string so the possible values are (0,0), (0,1), (1,0) and (1,1)

    Notice that you can continue alternating the (0,1) and (1,0) they will continue forming a good sequence and you can add all the (0,0)'s in between any (0,0) and (0,1) and all the (1,1)'s in between any (0,1) and (1,0)

    With that said you just have to check if it's possible to alternate the (0,1)'s and (1,0)'s also reverse a few of them as possible and check that the reversed value is unique.

    My solution: Link

    This is the best I can explain my solution it's really difficult to explain it and I hope the code helps.

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

    2E: Delete every nodes that can reach both A and B without going through the other. Now the answer is (how many nodes that can reach A)*(how many nodes that can reach B).

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

      And pay attention that the answer may over INT_MAX. I got WA on test18 because I didn't notice this before :( .

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

When we can see the results of Technocup? How many people will be invited to the final?

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

Well...When will the solution be given?

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

still could not see others solutions?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div 2 F I'm getting WA on TC 37 and I'm not able to figure out why. Anyone else got WA on fixed it? It would be great anyone is able to give some corner test case.

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

editorial?

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Please provide editorials

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

    I was really busy these days hosting 3 rounds. Unfortunately, for my problems (D2A-D2F) I can write solutions only tomorrow. I hope you liked them :) It seems most ideas are written in the comments.

»
5 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Nice contests for newbies.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In D2-E, why the answer of testcase 2 is 0, we can go from node 1 -> 2(a) -> 3(b) -> 4. So we have a pair and the answer should be 1?

Testcase
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Excuse me, when will the totorial be published :D

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it