By awoo, 5 years ago, translation, In English

Hello Codeforces!

On May/15/2019 17:35 (Moscow time) Educational Codeforces Round 65 (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 Neon 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:

Hello Codeforces!

We are collaborating with an external sponsor who is offering a unique scholarship opportunity for women who want to study Cybersecurity or Fintech, both for Bachelors and Masters level.

The scholarship includes:

  • An up to $10,000, one-time financial award, paid to the University
  • An all-expenses-paid trip to the EMEA Summit 28-30 October, 2019 in Berlin
  • A Cybersecurity professional to serve as an industry mentor

Apply before May 30th and Harbour.Space will also consider you for a scholarship from our own funds.

Don't miss this chance to study with us in Barcelona!

If you have questions about the scholarship, please contact us at [email protected]!

APPLY HERE→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Radewoosh 7 174
2 mnbvmar 7 183
3 I_love_Tanya_Romanova 6 119
4 Farhod 6 124
5 xiaowuc1 6 142

Congratulations to the best hackers:

Rank Competitor Hack Count
1 algmyr 57:-1
2 mnbvmar 16:-2
3 xavier_cai 11:-1
4 halyavin 10:-3
5 avm 7
291 successful hacks and 306 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Dalgerok 0:01
B Farhod 0:05
C sillysilly 0:04
D nuip 0:10
E Farhod 0:23
F ugly2333 0:13
G Dukkha 0:57

UPD: Editorial is out

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

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

Will there be a scholarship for men also?

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

    No, but if you tell them you identify as a female, you'll get in.

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

    Hey SoulAdor ! We have scholarships for both men and women and we post about them regularly on Codeforces! If you are interested in one, you can apply on our website! Everyone applying to the university is taken into consideration for a scholarship and no separate application is required.

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

Is he considered as a woman ?

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

Educational round logic :D

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

Seems this round will be started before publishing division 3 rating change xD

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

Rmind:Educational round correspond the third category in System problem something and i hope Reconciliation to All Participants

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

wait this round is dedicated to women? Then I guess its a div 4 guys shit.

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

I have no experience of rating adding in edu round :(

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

hope to become an expert = =

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

What's the difference between Div 3 Rounds and Educational Rounds besides the rating limit?

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

    Problem difficulty. Div. 3 problems are generally easier than Educational rounds.

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

      I do not agree with you my friend.

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

        I do not agree with you my friend.

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

        Div 3 are full of greedys!

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

          That's accurate, no doubt about it, but it doesn't mean dificulty in Div 3 problems is lower, at least the way I perceive it.

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

Typo perhaps? Paid by the University not to the.

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

I have submitted for B around 10 times it says idleness limit exceeded please help

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

    flush the print. You can read the linked page, given in problem.

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

Any hint for E and F? I think F can be solved by divide and conquer, but I don't know if my idea is correct..

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

    I think E is related to finding the inversions in the array but couldn't improve the time complexity from O(n^2)

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

      You can use 2 pointers because it is monotonous. I used binary search and got WA on test 57 but not sure if the method is wrong or i have a bug.

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

    For E: Fix l, starting from 1 to x. The idea is similar to 2 pointers and you will need some precomputated arrays.

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

    Precalculate p[x] = are numbers <= x sorted, s[x] = are numbers >= x sorted, l[x] = max number <= x, f[x] = min number >= x, you can check if (l, r) is good in O(1), just do binary search.

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

    F is just counting the coefficient of each $$$b_i$$$. You can process the $$$b_i$$$'s in sorted order and use a BIT to efficiently count how many terms smaller than your current $$$b_i$$$ are in a range, and their contribution to the coefficient.

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

      Actually there are $$$O(n^2)$$$ range pairs, and I got stuck on this ranges. I try to consider left range and right range separately, but I cannot figure out how to count that for each i efficiently.

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

        Say you're processing the ranges containing $$$a_i$$$. These are $$$[l, r]$$$ with $$$l \le i \le r$$$. If $$$a_j < a_i$$$ and $$$j < i$$$ then you add $$$1$$$ to the coefficient for each of the ranges that contain $$$a_j$$$. The right endpoint doesn't matter, so for each right endpoint $$$a_j$$$ is contained in $$$j$$$ ranges, and the total contribution to the coefficient is $$$j \cdot (n - r + 1)$$$, the latter being the number of right endpoints. You can get a similar expression for $$$a_j < a_i$$$ and $$$j > i$$$. To query efficiently you can build a BIT that allows you to get the sum of $$$j$$$ for $$$a_j < a_i$$$ and $$$j < i$$$, and another one for the right side. Then when you finish processing an element, you add it to the BIT.

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

please anyone show his code for problem B in c++14 PLEASE...

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

    Here you are: 54185189

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

    code for B

    The queries are a1*a2 a3*a4 a1*a3 a5*a5,It is possible to deduce a1 a2 a3 a4 from the first three queries and we got a5 by asking a5*a5, Then the array can be determined uniquely.

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

Has someone's nlog^2n in E passed? I kept getting TLE on test 6. I binary searched the r for each l. Edit: Passed after I dropped a logn.

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

    I was thinking on similar lines but wasn't that n^2 logn? How fast do you test if a particular l,r is valid?

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

      No that is not n^2logn. What you are thinking is to check all possible (l,r) pairs whether it gives non-ascending array or not. Correct idea would be to get minimum r (using bs and some preprocessing) for each possible l (1..n) and adding n-r to the ans.

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

      No, what I did was to fix a particular l. Then calculate the first 'r' such that [l, r] is valid. Then added n — r + 1 to the answer. Check my code here. I maintained the max prefix and suffix till the array is sorted for calculation.

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

How to solve B?

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

What is test 57 on problem E?

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

What's with the super tight bounds in F? My O(n log n) solution takes 1996/2000ms. 54195181

Happy hacking :P

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

My code WA test 1???? 54208002

check the answer on CodeBlacks why this code Run on Codeforces get "WA" and this test example is test one !!!

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

The problem D inputs by "cin" will get "WA" ,replace "scanf" get "AC" ,why??

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

among 8 div2 participants eho is better than me 7 of them are fake accounts. it is unfair lol i should be the 2nd, not 9th

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

[submission:54208002]This code "WA" test 1???

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

Is in problem E wrong to do binary search? Isn't it the same as 2 pointers?

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

What a pity! For E, cin/cout got a TLE while scanf/printf passed.

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

    Input/Output speed is not a problem because I also used cin/cout in E and pased. You just need to add ios_base::sync_with_stdio(0) to make cin/cout as fast as scanf/printf.

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

      Thanks very much. Indeed, with sync_with_stdio(0) my solution passed. But it still has a gap with scanf/printf.

      For cin/cout with sync_with_stdio, it takes 1606 ms. While for scanf/printf, it takes 1278 ms.

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

        Try using cin.tie(0); cout.tie(0) It is usually faster than scanf/printf

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

          Thanks!

          But for this problem, it still takes 1578 ms, not as fast as scanf/printf.

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

            You can use "\n" instead endl

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

C and D were easier than B.

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

Why did my solution to problem D gave TLE: code

Removing stack and converting string to character array passed the pretest. Don't know why..

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

    Because adding two strings is linear to their length. If you just push the char in the end is O(1). Changing it with += that equals to push_back it gives acc 54211273 (your sub with this change)

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

Authors should have announced that there will be interactive problems in the contest beforehand.

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

    Why?

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

      Many of Division2 participants didn't have any idea about interactive problems (I am also one of them). Because usually div2 contests doesn't contain this type of problems. To know and learn about them all on a sudden in a running contest is taught and time consuming.

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

        There is nothing to learn, interactive problems don't differ much from usual problems. My first interactive problem was on NEERC 2010, I had green level then but I solved it without any difficulties. I don't understand why so many people are afraid of interactive problems.

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

Thank you creators for such cool problems. I really enjoyed it.

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

why this solution(54181282) is getting wrong answer on testcase 2?

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

    Wrong output

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

    The line producing the error is probably this:

    for(i=s.size()-11;i>=0;i--)

    s.size() returns an unsigned int and if s.size()<11, s.size()-11 will underflow and take a value of the order 2^32.

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

    For s with length less than 11

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

Is it possible to solve C with a method other than Union Find?

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

Why was problem b hacked?

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

    Because according to your method, the fourth and fifth Numbers can switch places

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

    因为你第四个数和第五个数可以换位置拉。

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

why this https://codeforces.net/contest/1167/submission/54206553 is getting runtime error ?

I did it like the blog example :(

using same code but with cout<<flush is accepted

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

is D the simple stack implementation ?

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

    You can also solve it recursively, by using the fact, that all valid sequences S = (A)B, or empty.

    54212912

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

    Yes. Actually, you just have to invert the color before processing a '(' and after processing a ')'.

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

      @MMXIX can you explain your approach in detail,and how does reverting colors gives us required answer

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

        You have to minimize depth, so as you encounter two same brackets in sequence invert your color . This will minimize the depth.Simple greedy approach.

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

      Thanks for your comment. I did this in the same way and got accepted but I was in doubt as it 'D' problem.

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

Was O(N logN) supposed to pass on E? I got TLE on test 50 with such an approach. If it was intended to pass, why set the bound as high as 1e6?

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

    There are O(N) solutions using 2 pointers. However, I think only simple O(NlogN) solutions passed (binary search).

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

      I used bs and got WA on test 57. Still can't understand what's wrong.

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

        Finally found the bug. It is not related to binary search.

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

The problem B could be more interesting if the number of elements would be greater.

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

xx

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

    sizeof(vs) is a constant value, you have to multiply it by the size of the array.

    Correct command would be memset(vs, false, sizeof(bool) * (n+1)) because type of elements in the array is bool. sizeof (vs) will typically be larger (8 bytes) than sizeof(bool).

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

    vs is a pointer, sizeof a pointer is generally 4 bytes (8 bytes for x64 compilation).

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

Can anyone explain their approach of solving problem D?? I am not able to make up any thoughts about it

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

    let r0 be the nesting of string with color 0, similarly define r1.

    Initially, r0 = 0 and r1 = 0.

    now ,each time you encounter an opening bracket, if r0<r1, color this bracket 0 (also increment r0)else color this bracket 1 (also increment r1).

    Similarly, each time you encounter a closing bracket, if r0>r1, color this bracket 0 (also decrement r0)else color this bracket 1 (also decrement r1).

    This guarantees that both strings will be balanced bracket sequences because r0+r1=nesting of original string =0 and r0 or r1 can't be negative (because we ensured it in the loop above) so r0=0,r1=0.

    This also guarantees that max nesting is minimised because only the min is incremented when encountering an opening bracket (always better than incrementing max) and the max is decremented when encountering a closing bracket (always better than decrementing min).

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

      Can you explain the proof a little briefly? , it is a nice approach.

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

The judge doesn't judge.

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

Why is Codeforces so slow after every contest? My past 3 submissions in the virtual contest have not been judged.

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

What is the approach for F?

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

    For fixed i, find all j's with (a_i >= a_j), then answer will be the sum of min(i + 1, j + 1) * max(n — i, n — j). Go through i's in increasing order and maintain several fenwick trees.

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

I'm very confused. Can someone please explain how to solve E? I have been reading multiple AC solutions but still can't understand the idea behind that!!

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

    Save the maximum index and the minimum index of each different elements in a. Then think of how to judge a f(l,r) is valid or not in O(1)

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

In problem C, I'm using DFS and getting a TLE in 7th test case. Can anyone help?

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

    Maybe you are not building the graph in an efficient way. Suppose you have 2 5 7 9 Then you don't have to do

    2->5->7->9
    5->2->7->9
    7->9->5->2
    9->2->5->7

    Instead do something like
    2->5
    5->7->2
    7->9->5

    You don't need to make exact graph as you only have to count connected components.

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

    you can skip visited groups

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

It would be nice, if someone please explain me the problem C using sample Case. I didnt figure out it yet for a while xD. Thanks in advance <3

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

    Lets take first case there are 5 groups and 7 people. Each of 5 rows starts with some number that means how many people in Ith group. For example in first group 3 people with number 2, 5, 4 and so on. And problem says if person sends news, their friend can also send info to their friends. After this if person in this group he can share news to this friends and if this friends in other groupes they can share news to other friends in that groupes. At the end we can say that we need to find every component and people in this component can share info with this size of component(including himself). First case if we take person with number 1 he is in two groupes {1, 2} and his friend 2 is in group {2, 5, 4} and if we add this two groups its {1, 2, 5, 4} everyone can share new with themselves that means 4 is the component size. You can solve this problem with dfs or dsu)

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

      You said: "First case if we take person with number 1 he is in two groupes {1, 2} and his friend 2 is in group {2, 5, 4} and if we add this two groups its {1, 2, 5, 4} everyone can share new with themselves that means 4 is the component size."

      But My point is it should be.. if we take person with number 1 he is in two groupes {1, 2} and his friend 2 is in group {2, 5, 4} and{2, 6, 7} and if we add this three groups its {1, 2, 5, 4, 6, 7} everyone can share new with themselves that means 6 is the component size." Can you please clear my confusion. Thanks xD <3.

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

        2 6 7 doesnt mean fifth group contains {2, 6, 7} first number means how many people in this group, in this example 2 people in fifth group with numbers {6,7}

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

In E, is it okay to find the max l value and min r value such that l<=r , and f(l,r) is valid. Then we know that f(l-k1,r+k2) is also valid for all possible values of k1 and k2.

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

    That is true but not enough. For example, leaving one element only inside leaves array sorted, if l != r, then we can leave l + 1

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

      couldnt understand

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

        I mean, what if l = n and r = 1. Which max l value and min r value do you choose? If you iterate all, then you count some segments several times.

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

          but l<=r

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

            What about this case. 1 4 2 5. f(4, 4) = 1 2 5. it is valid and we cannot make l bigger or r smaller, because then l > r. So you are saying that all f (4 — k1, 4 + k2) are true for positive k1 and k2, as I can tell. Well that is right. But we also have f(1,2), for example -> 4 5. And it is not of this form, 4 + k2 = 2 so k2 is negative.

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

              Oh, I understood. So you mean that 4-k1 and 4+k2 is correct but it leaves out other cases... because l is unable to become greater than 4 and r unable to become smaller than 4.... Is this what you meant?

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

Why using Dfs to get number of nodes in each connected components gives wrong https://codeforces.net/contest/1167/submission/54223559

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

    You are assigning the value of c to val[i] while running dfs, c being the number of connected components, this doesnot ensure that the parent of all these components is 'i' and therefore the answer is coming out to be less than than the actual number of components. Just a little bit of change and there you go..!!! 54225792

    PS-- This might give you TLE in system tests as you have not used weighted dsu.

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

Hope that I can reach 1600, it is only 12 ratings away but it seems that I am not performing well this time... Btw I really appreciate problem B as an interactive task, as we don't get to meet them often and this is a great opportunity to train up skills related to interactive tasks.

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

I wonder when I can see the ratings changing...

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

Easy busy contest

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

Why Radewoosh's submit 54183325 didnt get TLE? In his solution (sorry for my poor English) he didnt use rank's heuristic and got AC. I tried to submit solution without rank's heuristic and got TLE 54233682 . Could someone help handle it, please?

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

    Because he used a technique called 'Path Compression'.

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

    In his code

    int fin(int v)
    {
      if (v!=oj[v])
        oj[v]=fin(oj[v]);
      return oj[v];
    }
    

    not

    int fin(int v)
    {
      if (v!=oj[v])
        return fin(oj[v]);
      return oj[v];
    }
    

    So after a fin(v) operation, the nodes on the path from v to the root will all directly connect to the root.Therefore, when you perform fin(i) (i is a node on the path from v to root) will just return oj[i]

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

Wait for tutorial

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

I have passed problem G, but I have no idea whether my solution has a right complexity.

My solution is 54235792. It uses a method similar to two-pointer to find the nearest pair that is the same far from point x.

Could someone please tell why it's correct or construct a data that will lead to a TLE?

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

I got compilation error on problem D during system test after it passed during the contest? How is that? :D

54189857

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

Here is my $$$O(N)$$$ solution for problem E: 54241182

The general idea is to maintain, first of all, a global rightmost $$$L$$$ and a global leftmost $$$R$$$ such that ranges $$$[1,L]$$$ and $$$[R,X]$$$ are valid, then for each $$$r$$$ the rightmost $$$l$$$ such that the union $$$[1,l] \cup [r,X]$$$ is valid too.

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

Used DSU for problem C, got WA test 3 and I cant find the mistake, can anyone help? 54184178 Edit: Found the error, I was not checking if nodes are already connected before connecting them.

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

    same for me.
    then I used dfs and it got ac.
    I don't know what is the mistake.

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

    I also got WA test 3. You should check in your connect function that you don't connect the same element.

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

Hello, I tried solving problem C and I was getting TLE error on test 3. Somebody please help in optimizing my code. I didn't get the editorial properly. Here is my code: https://codeforces.net/contest/1167/submission/54269390

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

    The answer is the same for vertices in same connectivity component. You dont need to clean the array.

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

How to solve problem G?

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

problem D, solution1 got accepted whereas solution2 gave TLE. The only difference between the two is in line number 21. In solution1 we append 0 in string by res+='0'. In solution2 we append by res=res+'0'. I thought these two operated the same way. Can someone give insight to the reason?

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

Someone please help me with problem C. I am getting MLE. Any help would be appreciated. https://codeforces.net/contest/1167/submission/54526141

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

78428168 78426655 Why did this same code got accepted with C++17 while it got TLE on C++17(64)? All i did was change the array size.. That should've given a RE instead of TLE

Can anybody explain?