By PikMike, 7 months ago, translation, In English,

Hello Codeforces!

On May/01/2019 17:35 (Moscow time) Educational Codeforces Round 64 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Hi Codeforces!

Harbour.Space University, the International Tournament of Young Mathematicians (ITYM) and St. Paul International School Barcelona have designed a special online test for high school students, to take place on May 5th at 15.00 CET Time.

You can take part in the online test if all the following conditions are met:

  1. Between the ages of 12 to 18,
  2. Have not graduated from high school
  3. Eligible to take part in IOI/IMO 2020.
Register (before May 3) →

After the test, all participants will get a 20% discount link to attend Tech Scouts, the two-week summer camp we run from the 8th-19th of July in one of Barcelona's leading international schools, St.Paul’s, and the most successful performers will be interviewed and awarded a full tuition waiver to attend the advanced level of the Advanced Technical Track of Tech Scouts.

In order to register for the contest, please fill out this form before May 3rd, 2019.

We would love to see you guys at our camp this year — if you’re interested in joining, or if you just want to know more, just head over to the Tech Scouts website.

UPD: There are some minor issues with one of the problems, we'll use one of lesser-known problems by Maxim Babenko.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 step_by_step 7 491
2 RimuruTempest 6 270
3 receed 6 280
4 I_love_Tanya_Romanova 6 286
5 dreamoon_love_AA 6 299

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 64:-3
2 WileE.Coyote 39:-23
3 wzw19991105 18:-1
4 FST-OIer 14:-1
5 omaewamoushindeiruuuuuuu 2
153 successful hacks and 180 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A halyavin 0:06
B nuip 0:07
C quailty 0:04
D waynetuinfor 0:11
E step_by_step 0:05
F step_by_step 0:15
G step_by_step 1:22

UPD2: The editorial is out.

 
 
 
 
  • Vote: I like it
  • -164
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +74 Vote: I do not like it
Every educational round ever
»
7 months ago, # |
Rev. 5   Vote: I like it -15 Vote: I do not like it

PikMike says, NEVER GIVE UP

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

Hope the problem set is going to be an interesting one like the last one :)

Happy Coding

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

Round Professional 64 activated successfully !

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

wtf?

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

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

the round should be unrated

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

what is going on?

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

    Problem A was not well described. The side note under the test case was explaining an unwritten test case which means it was misleading. The solution had been rejudged. I see something strange that most of the solutions get WA answer on test 3. check the announcement of the round. Whatever, it is unrated now

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

To be honest, for long enough hasn't a problem A been so... chaotic.

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

Is it rated? Rejudging affects >3000 people.

UPD: Unrated.

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

read first problem 10 times before seeing announcement. Feeling Irritated

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

I'm very upset today :(

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

The round should be unrated, it's not ok that after 30 mins I see my AC code on A get WA

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

    Literally everybody did though, I feel like it could still be rated, I don't know

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

oh no.

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

Eventually, the round became unrated. :(

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

Solve problems just for fun. ;)

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

Authors, dont worry. Shit happens. Good luck to you

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

So what's going on in Problem A? My code got WA after rejudge. But I don't know what's wrong in it. http://codeforces.com/contest/1156/submission/53616304

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

Got really happy after getting notification of round being unrated. Already many WA.

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

should have been rated but oh well

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

This round the highest Accepted on the entrance div2-A problem was 8. Out of 100! XD

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

to be honest, this compitition has got a really chaotic problem set.

(who had seen problem A give so many leaks? And problem B also got an error in the standard output.)

yet this round is unrated.

Irritating. Very irritating.

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

without paying attention to solved problems, It won't change our rating , yeah?

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

"_Unfortunately_, the round will be unrated."

More like, Fortunately am i rite?

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

happy coding

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

    this but with GCD, divisor and Number theory

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

    Why not try to learn those stuff and be able to solve problems way over your rating range?

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

Japanese people welcomed the new era, not error.

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

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

Literally half participants on problem A. ( including me )

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

    This photo really swapped out my bad mood today. www

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

    TFW codeforces comment section is funnier than all of reddit.

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

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

Something went wrong...

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

    Unfortunately, the contest is unrated(((

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

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

This year the highest grade on the entrance math test was 8. Out of 100!

I guess now everyone knows why xD

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

What a mess.

»
7 months ago, # |
Rev. 6   Vote: I like it +10 Vote: I do not like it

2 1 2

is this valid for Problem A?

UPD: Finally this is surely invalid because an anoucement.

The triangle is oriented in such a way that the vertex opposite to its base is at the top.

UPD2: really sorry, maybe I should change new glasses, the problem statement says, the triangle is oriented in such a way that the vertex opposite to its base is at the top

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

    No. The direction of the red triangle should be like the black one.

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

      isosceles triangle with the length of height equal to the length of base.

      each triangle base is parallel to OX

      for each i from 2 to n figure i has the maximum possible length of side for triangle and square and maximum radius for circle

      The red triangle fit these condition well.

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

        OK. But there is another announcement now.

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

        Yes, but you have drawn a equilateral triangle for which the height is not equal to the sides, so this configuration is impossible.

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

          this is my fault because of drawn misleading.

          even thought if drawn correctly, the answer may be 5 not 6. :D

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

    No. Notice that "each triangle base is parallel to OX".

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

      Anyway, the base is still parallel :)

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

        Yea, I think you are right. In this case, I considered the vertex as the "base" actually, so I thought it's not parallel to axis.

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

          How can a vertex be parallel or not to a line?

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

            If it does not intersect the line then it's parallel to the line :)

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

      But just now there was an annoucement

      The triangle is oriented in such a way that the vertex opposite to its base is at the top.

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

        It's also in the statement of the problem:

        the vertex opposite to the base of the triangle is poiting up;

        And I think it was there before the announcement because I had the tab open and didn't refresh.

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

          yeah, you are right.

          maybe I should change my glasses

          UPD: there are only four condition in very first,

          the vertex opposite to the base of the triangle is poiting up;

          this was just added later.

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

            No, you don't have to do that; that state is revised, and before revising that, there was some vague state.

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

    Hehe, didn't even think of this one!

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

Since the contest is unrated and everyone is discussing the problems anyway... how to solve C? It feels like there should be some sort of greedy way of matching up points but I can't figure it out.

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

    I did binary search for the number of matches k. Check by trying to pair the k smallest points with the k largest points.

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

    just sort the array, and use two variables i and j. initialize i=0,j=n/2 and then just start pairing them.

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

I want to experience how it feels like asking a solns of ongoing contest in comments.

Here it goes -
"How to Solve D??"

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

    You can solve it with a little bit of DSU.

    First of all, use all edges marked as $$$1$$$ to merge nodes into disjoint sets.

    Then, the remaining edges — those marked as $$$0$$$ — are considered as the actual edge of the graph (in other words, after using all $$$1$$$ edges to create disjoint sets, we remove them).

    From here, we'll perform DFS for the entire graph to find the components of nodes connected solely by $$$0$$$ edges.

    For each component, let's denote $$$m$$$ as the component's size. Also, let's denote $$$k$$$ as the number of nodes not within the component, but can be reached from some nodes of the component due to being in the same disjoint set (mentioned at the first step). We'll add $$$m(m-1) + mk$$$ to the final answer.

    The calculation of $$$k$$$ is simple — before the DFS traverse initiate $$$k = 0$$$. For each node $$$z$$$ visited, increase $$$k$$$ by $$$sizeof(dsc(z)) - 1$$$, with $$$dsc(z)$$$ is the disjoint set containing node $$$z$$$.

    Total complexity: $$$\mathcal{O}(n \cdot \log(n))$$$ or $$$\mathcal{O}(n \cdot \alpha(n))$$$, based on how you construct the disjoint set union.

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

      Why not to use DFS to find the components connected by 1 edges?

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

        Well, we still need $$$sizeof(dsc(z))$$$ after joining nodes by $$$1$$$ edges, and (not sure if there was any neat implementation), if I performed DFS on that step, I'd either do it twice to assign $$$sizeof(dsc(z))$$$ to all $$$z$$$ in that component, or use a vector/stack to maintain the newly visited nodes, which could actually makes the implementation be a bit unnatural.

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

      The answer is S(m*(m-1)) + S(dsc(z)*(dsc(z)-1)) + S(m*k) right? S() denotes sum over all components, disjoint sets and components respectively.

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

        $$$S(m(m-1)) + S(mk)$$$ actually. Forgot to include it into the main comment, will edit in a few seconds ;)

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

    I used Tree DP, with:

    dp[0][i]: number of 0-1 path whose lca is child of i

    dp[1][i]: number of 1-path which ends at i

    dp[2][i]: number of 0-path which ends at i

    dp[3][i]: number of 0-1 path which ends at i and the edge connecting i is 1-edge

    dp[4][i]: number of 0-1 path which ends at i and the edge connecting i is 0-edge

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

    It's also possible to do it in O(n) using dp on trees. Let dp[x][0] be equal to number of vertices to which we can access from vertice x using paths which have only zeroes as their weights and dp[x][1] same thing but which have only ones as their weights.

    We can note, that each path we are looking for has a point where ones change to zeroes. Let's assume that our vertice is the vertice of change for some paths. We can easily observe that we need to add to an aswer dp[v][0]*dp[v][1]+dp[v][0]+dp[v][1].

    So now the only problem is to find a way to calculate dp array. Firstly let's calculate number of paths which i mention before but only for vertices in the subtree of vertice x. That can be done as follows: if we have dp calculated for our son, and we use a path of weight y to go to him, then dp[x][y]+=dp[son][y]+1.

    Now we have the answer but only for a vertice from which we started our DFS (because his subtree is full tree). Now let's start second DFS. An observation is: if we go from vertice x to its son using a path with weight y then dp[son][y]=dp[x][y]. Why? Having in memory that dp[x][y] is number of vertices we can access from vertice x using paths which have only weights y, then we see that this number can't change if we are using a path of weight y.

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

    Lots of tree-DP problems based on paths have a standard procedure consisting of two steps:

    • Solve the DP, but the DP of a vertex will only be restricted to the subtree of the vertex.
    • Start changing the DP values from top to bottom, so that now, the DP of a vertex describes all paths originating at the vertex. There are only two cases — one, we have already included in our DP state, that the second vertex is a child of $$$v$$$, and the other is when the second vertex of the path is the parent of a vertex $$$p[v]$$$.

    Initially, if I define $$$dp[v]$$$ to be the number of vertices in the subtree of $$$v$$$ to which I have a valid path, and $$$dp1[v]$$$ to be the number of vertices in the subtree of $$$v$$$ to which I have a path by navigating only 1-edges, then in one dfs we can compute these values. Then, in the next dfs, we include in both $$$dp[v]$$$ and $$$dp1[v]$$$ the case where the second vertex of the path is the parent, which gives us the final answer for vertex $$$v$$$. So after this dfs, $$$dp[v]$$$ will be the number of valid paths originating at vertex $$$v$$$ and $$$dp1[v]$$$ will be the number of valid paths originating at $$$v$$$ by navigating only 1-edges. Note that we must change the value of the parent before that of a vertex, because we want to use the second definition of $$$v$$$ for the parent in the second DFS.

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

problem A (and other problems also) proved that every contestant is also a Labour. Happy Labour Day.

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

Is it possible that a cycle inscribed into the non-equilateral triangle (isosceles with the length of height equal to the length of base) with three distinct points touched?

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

    Think that there is "An inner circle of a triangle". It is always possible.

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

fortunately, the round be unrated :) problems are interesting,but I have bad performance.

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

I know author is going to be blamed for this round. But honestly, I found the problems really beautiful and engaging. Kudos to author.

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

Good decision to announce the contest as unrated .

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

Thanks for very interesting problems! Can anyone tell me how to solve B?

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

    Lets represent a, b, c...z as 1, 2, 3, ... 26. Now the best strategy is to club all a's together, all b's together etc. If you keep first all evens and then all odd terms, then we'll just have to worry about junction. For this you can find a pair of (even, odd) which differ by atleast 1.

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

    Let's switch to numbers instead of characters, so the alphabet will be $$$0,1,2,\ldots 25$$$. Notice that a pair can only be ugly if one of them is odd and the other is even. First we have two cases if there're only odd or only even numbers, in that case we're done. Else we have at least one odd and one even number, intuitively we may want to minimize the touching of odds with evens so we may think about an order where first the even numbers then the odds come. This will only be possible if there's at least a pair of odd and even numbers that have a difference larger $$$1$$$ (since then we can put them in the middle and the rest can be placed arbitrarily) and obviously in the case when we have $$$0$$$ such pairs it would be impossible to order them (since in every ordering there is at least one odd-even pair), so we can see that the above statement is equivalent to that there's a valid reordering.

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

For everyone who got WA on test 7 (problem C), try this case:

10 2 1 2 3 4 5 6 7 8 9 10

Correct output: 5

I made a greedy solution (sort all the numbers using multiset, then for every number find the smallest number it can be connected to and erase both numbers from the multiset) and this case showed me that my approach was wrong. I hope it'll be helpful to someone.

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

(Direct quote from Problem A) So can you pass the math test and enroll into Berland State University?

Um..... (sigh...)

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

after rejudged A

It was at this moment theroot knew, he fucked up xDD

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

Why RE on test 16? Code

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

    I guess it is due to size of the array. As segment trees have around 4*N nodes.

    Btw if possible then please explain your approach here!

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

So.. Any hint for C?

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

    If you order the array and one of the best possible solution has some pairs with both indexes in the first half of the array, you can change one index of each this pairs be indexes of the second half of the array. And this new set of pairs still is one of the best solutions.

    Same way if you have some pairs with both indexes in the second half.

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

Last contest I wrote a toxic comment and I'm really sorry for that because mistakes happens and we should understand that

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

Any hints for E ?

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

    You can doing it using a Mergesort tree.

    For each element Ai calculate the range in which it will be maximum. That is Li and Ri where Li is the highest index j < i such that Aj > Ai and similary Ri is lowest j > i such that Aj > Ai.

    For each Ai, check each j in Li...i-1 to see if Ai — Aj exists between i+1...Ri using the mergesort tree. (You just have to maintain a set on each node in the Mergesort tree and check for each node in the range if the required value exists in its set).

    Since for any j between Ai and Ri Lj >= i (as all elements from i...Ri <= Ai) so you'll be querying mergesort tree for each element only once. Each query takes logN*logN time.

    Thus the complexity is N*logN*logN.

    Not sure if easier approach exists.

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

      "For each Ai, check each j in Li...i-1 " Can you please help me understand why this will not lead to O($$$n^2$$$)?

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

      "Since for any j between Ai and Ri Lj >= i (as all elements from i...Ri <= Ai) so you'll be querying mergesort tree for each element only once."

      Could you explain this part a little bit more? What if we have a situation like:

      [ ( y ) x ]

      Here x and y are two elements, [] indicate Lx and Rx and () indicate Ly and Ry. Obviously, y < x. Evidently, we can construct such a case (for example, 10 5 6 7 1 3 2 8 9 4 11).

      In such a case, every element between Ly and y is queried twice (once because of y and once because of x). I thought of the same approach during the contest, but I didn't think it would work because of such cases.

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

      I had a similar approach, but i think it is easier. For each element you calculate l[i] and r[i]. These numbers represent the range in which a[i] is the maximum element. To find this easily we can use a stack.

      Then, for every i from 2 to N-1, we will do the following: Choose the smallest side in our range [l[i],r[i]]. ( Smaller between i — l[i] and r[i] — i ). Then we can try every number in this range with a "bruteforce" approach. To know if that number will make a valid solution, we need to check if its complement ( a[i] — a[j] ) its in the opposite side and inside the range in which a[i] is maximum.

      This approach seems like bruteforce, but with a little bit of math you can confirm it is actually linear.

      Code to understand the idea better : 53634108

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

        "This approach seems like bruteforce, but with a little bit of math you can confirm it is actually linear. " can you please give a rough sketch of proof?

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

      I think Li and Ri can be found using range maximum query inside a binary search..

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

    divide and conquer

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

    I think that 53648275 is pretty short, easy to understood and O(n log n)

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

      can you please explain your solution a little bit?

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

        I used divide and conquer... $$$f[l, r)$$$ counts how many pairs $$$(i, j)$$$ exists such that $$$p_i+p_j=max(p_i...p_j)$$$ and $$$i < m <= j$$$ for $$$m = (l+r) / 2$$$, and again solve the problem for $$$f[l, m)$$$ and $$$f[m, r)$$$ recursively (cases when the condition $$$i < m <= j$$$ not is true).

        So for a fixed $$$f[l, r)$$$ and $$$m = (l+r) / 2$$$ for every $$$l <= pl < m$$$ and $$$m <= pr < r$$$ the maximum of the interval $$$[pl, pr]$$$ is $$$max(max(pl...m-1), max(m...pr))$$$, i assume that the maximum is equal to $$$max(pl...m-1)$$$ this determine $$$pr$$$ of a unique way $$$(pr=max(pl...m-1)-pl)$$$ so you only need check if $$$[pl, pr]$$$ is a valid pair

        But what about if $$$max(max(pl...m-1), max(m...pr)) == max(m...pr)$$$ not $$$max(pl...m-1)$$$ ?, then solve the same problem again but with the reverse of the array, because if the maximum is in the right part in the reverse will be in the left part :)

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

          is selecting all possible $$$(pl, pr)$$$ doesn't lead to $$$O(n^2)$$$?

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

            For a fixed $$$pl$$$ you can determine of a unique way the maximum (assuming that is in the left part) and then $$$pr=max(pl...m-1)-pl$$$. So you only need iterate all $$$l <= pl < m$$$

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

Can someone tell me why this submission got WA https://codeforces.com/contest/1156/submission/53640819

got it fails for this input 10 2 1 2 3 4 5 6 7 8 9 10

»
7 months ago, # |
  Vote: I like it -11 Vote: I do not like it

is this unrated? as declared in announcement

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

If anyone wants to solve problem D using dfs 53633184.

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

    would you please explain your approach

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

      Divide the tree into connected components of edges of 0s and 1s.

      Now, there will be three cases to sum:

      case #1: the path contains edges of all 1s.

      case #2: the path contains edges of all 0s.

      case #3: the path contains some edges of 0s in starting then all 1s at end.

      For case #1 and case #2 answer will be simply cnt1 * (cnt1 - 1) and cnt0 * (cnt0 - 1) respectively.

      For case #3: select a center vertex containing both edges of 0s and 1s. Now, to form a valid path, you have to select first vertex from connected component of 0s and second vertex from connected component of 1s. Answer in this case will be (cnt0 - 1) * (cnt1 - 1). [ how ? center vertex will be counted in both components.]

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

        Thanks for explaining case by case.

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

How to solve B? What is the case when we don't get an answer??Please help guys

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

    You need to take unique elements in string sort it and keep even indexes in first and odd indexes in second array. For example if string is "dcbab" then it would be like "ac" and "bd" and check if we can return it as "acbd" or "bdac" if two if this replacements are not possible then we return wrong answer, else we would return possible answer.

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

      But how is this true ??

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

        Because there if we take even and odd indexes of the unique string then there would be minimum 2 letters between them and if there is the size of the string is odd number it means last element of two arrays differ by 1. It means you check if which replacement is right array two-> array one or array one -> array two. And don't forget to print out the number of elements in the string

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

    Cases when we don't get answer..
    2
    ab
    abc

    Critaical Test Cases you can check...
    2
    abd
    acd
    Output:
    adb
    cad
    How to solve:
    You can count the frequency of every letter from 'a' to 'z' in the input string... Then iterate through 'a' to 'z' and if count of it is not zero then insert it in a vector or string as you want... then take the even positions characters in vector1 and odd positions characters in vector2... then check if vector1+vector2 give you a valid solution or vector2+vector1 give you a valid solution if no one give a valid solution then, there exist no solution.. Hope you understand..

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

I'm a little bit confused. Isn't solution for problem F is to calculate number of winning and all combinations and just divide them?

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

What's halyavin doing?

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

in fact, Problem A is nice and trick. if you got WA... did you thought about this foken test case :D ?

6 intersection Points, NOT 7

also, the Infinite Cases :

But during the Contest: Set_IQ(0);

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

halyavin back in business.

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

Can anyone help me debug my solution for problem C

https://codeforces.com/contest/1156/submission/53644079

I get WA on test 7, is my idea completly incorrect ?

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

Lmao waited for this contest ever since they messed the last one a couple of days ago just to mess this one again.

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

Maybe this might interest someone...

I solved problem B using random_shuffle

https://codeforces.com/contest/1156/submission/53634293

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

    I thought of this solution but didn't have the balls to write it :D.

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

In tags of problem C I've seen ternary search.Can anybody explain how to use ternary search in this problem?

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

    https://codeforces.com/contest/1156/submission/53646659 here is a solution using ternary search. it's very similar to the binary search one so i think it isn't necessary to do it using ternary search. i think the easiest solution is using two pointers technique, it's clear that it isn't optimal if we matched any number with another one has index below than n/2 because it may decrease our answer and we could match the two numbers with another two have indices above n/2, so we only have to start the first pointer from 0 and the other from n/2 and increase our answer whenever the condition happen and increase the two pointers too if the first pointer is below n/2, else we increase the second pointer until the condition happen or the second pointer reach n and here is a solution using two pointers https://codeforces.com/contest/1156/submission/53615906

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

    if the solution has one peak or low on the middle of searching range, we can find that by ternary serach . when doing two pointer greedy rolling match p1 = 0 is optimal obviously, and choice of p2 have the property to do ternary search if choose 1 it is not good since best can only be 1 it will be optimal at some middle point and then be bad again at last part since some possible match will be in front of p2

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

can anybody help me on test 6, problem B plz :( thanks

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

    You can Check the following testcase
    2
    abd
    acd
    Output:
    adb
    cad

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

Don't worry PikMike, we still love you!

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

D, E, and F were really intersting. I guess without problem A we could've had a great contest.

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

Editorial?

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

Can someone tell we why I get a WA on test1 problemB My submission, it says that "wrong answer Resulting string should be a rearrangement of the given string" but I think my answer is correct!

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

Prob.B
BOGO SORT Σ(っ °Д °;)っ
53651542

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

The problems are really good, by the way, how to solve problem E?

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

My second unrated contest...

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

Can someone explain problem C using binary search?

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

    After sorting the set of point x, you only need to look at begin and last N points while checking whether N can be an answer.

    My submission

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

You have no right to recognize a non-existent state Its name is Palestine, not Israel -_-

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

PikMike There is a bug in the checker of problem G!
It says "each character is a lowercase or an uppercase Latin letter, or a digit" in the statement, but if you use uppercase, you get WA!

Accepted 53671039 and Wrong answer on test 1 53671084 only differ by 1 byte.

I think you have no choice but to rejudge G and make this round unrated :(

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

    I fixed the checker and rejudged your submission, it's ok now.

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

The problem G is 20 years old! It was offered by Maxim Babenko for Saratov internal contest. Now he heads development of the YT platform for distributed computing at Yandex. We studied in the same school, in parallel classes. I am very grateful to Maxim that he inspired me to learn programming in those years.

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

Loved the problems... keep taking such contests more... it was nice contest if we ignore issue on first problem