arsijo's blog

Codeforces Round #495 (Div. 2)
By arsijo, 6 years ago, translation, In English

Hi everybody!

Summer... It is a wonderful time for traveling, walking with friends, new discoveries and, of course, writing new exciting contests at Codeforces. Thus, I bring to your attention my new Codeforces Round #495 (Div. 2) with interesting tasks that will take place on Jul/05/2018 19:35 (Moscow time). If your rating is less than 2100, this round will be rated for you; otherwise, you can participate out of competition.

I would like to thank Mike MikeMirzayanov Mirzayanov for his help with problems preparing and for Codeforces and Polygon platforms. Also, Ildar 300iq Gainullin, Dmitry cdkrot Sayutin, Daniil danya.smelskiy Smelskiy, Chin-Chia eddy1021 Hsu, and Kevin ksun48 Sun for the problems testing.

You will be given 6 problems and 2 hours to solve them. Scoring distribution will be announced later.

In this round, you will have to help Sonya with her daily problems. Good luck!

UPD. Scoring 500-1000-1500-2000-2500-3000.

UPD. Congratulations to winners!!!!

Rank Nickname Score
1 EZ_fwtt08 7892
2 milisav 5550
3 VisJiao 5294
4 Jatana 4832
5 wasyl 4762
  • Vote: I like it
  • +379
  • Vote: I do not like it

Comments Comments (199)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

June 5?? Please correct the date, it's JULY 5.

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

I think this is the shortest, precise and most exciting round announcement I have ever read.I hope the problem statements are along the same lines.

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

Hope that we wouldn't see number 502 with label "Bad gateway" again)

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

Is it rated??????

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

Rating is like life . Full of up and down down down down down down down .

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

    are you saying this !!! hardly your rating had a downfall man ....but still i agree with you

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

    I think what I have said may come true. :(

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

Thank you for this announcement on the glorious Fourth of July. I hope my rating goes to 1776 after contest. For America, her allies, and my constitutional right to shitpost. #AMERICANUMBERONE

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

Unimaginably, they've mentioned Mike.

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

One more task and this would have been a beautiful regular round with two divisions.

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

+1 if you want problems to be short and concise instead of long confusing stories...

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it -41 Vote: I do not like it

    How about +2 ?

    UPD: By the way, what is so wrong with wanting the problems to be short and precise?

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

      unfortunately it canot stop...

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

      The same thing that's wrong with "is it rated"

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -38 Vote: I do not like it
  1. Seeing so many grey comments under the announcement...
  2. Summing the number of downvotes and upvotes of the comments.
  3. Getting -10 per comment in average.
  4. Trying to find out what's wrong with comments.
  5. Understanding that killer_god said the genius thing: http://codeforces.me/blog/entry/59942?#comment-436969.
→ Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

kun? Another Mathforces round?

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

    How are testers related to the inner contents of the round?

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

I hope codeforces work properly today.

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

Where is KAN for help to prepare the round.

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

I smell math for this round either

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

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

    Be careful — you've got 3 of 5 the most popular jokes in one picture. It will be very difficult not to be hidden.

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

What to do if you don't meet Wael.Al.Jamal in comments and can't downvote all his comments for reaching the new record (-200 contribution)? EXACTLY! You must help Codeforces community to reach another record — the greatest total number of downvotes under the announcement in the history.

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

arsijo, Is she the same Sonya from Codeforces Round #371 ..??

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

Again my rating will decrease.........Why there is no rank name under newbie....?

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

    you have chosen wrong handle maybe :)

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

I've noticed in the previous two Div 3 only rounds the registrations exceeded 8000 at both times and Div 2 contests don't often get that many participants. I wonder why

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

Rating is like life . Full of up and down down down down down down down .

see my graph

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

Problems are loading very slow. Is it just me?

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +23 Vote: I do not like it

#define int long long

Are you serious?

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

Congratulations to Codeforces with 40,000,000 sent solutions!

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

Am I the only one who is not able to submit the solution for problem C

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

A very uneven contest. Problem C has 2k+ solutions, and problem D has less than 100. Codeforces needs to work on the aspect of balancing the problems evenly.

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

A easy B easy C easy then suddenly D hard? Nice diff spread

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

very confusing statement

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

    Strongly agree. I had hard time understanding pA statement. Also forgot to set array value 0 in pC, cost me around half hour and 2 WA :(

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

Attempting Problem D after successfully submitting Problem C:

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

Was it just a bad day for me or there was seriously something weird with problem A? -_-

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

    No, you are not alone

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

    The way problem was framed: For the given test case 2:

    5 2
4 8 11 18 19

    The answer should have been: 7 i.e. 2, 6, 13, 14, 15, 16 and 21

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

      If you're gonna count 14 and 15 why not count 22,23,24... as well?

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

      "She wants to make the minimum distance from this hotel to all others to be equal to d".

      14 and 15 are not valid cities, because the minimum distance to an hotel is 3 for both of them, and in that test d = 2.

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

        When a hotel is located at 13, how is the distance equal to d for all the other hotels apart from hotel at 11

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

          "The minimum distance from this hotel to all the others" = "The minimum of all the distances to the others hotels" = "The distance between this hotel and the nearest".

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

            Actually, if you want to "make the minimum distance from this hotel to all others to be equal to d", then you are saying that for each hotel different from the yet-to-add hotel, you want the distance to be equal to d.

            It's obvious in this problem that this wasn't the intended meaning (actually, it wasn't obvious to me, I had to look at the sample tests), but if the problem involved a graph, for example, then I would never have thought that:

            "The minimum distance from this hotel to all the others" = "The minimum of all the distances to the others hotels"

            is true.

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

          "the minimum distance from this hotel to all others".

          The minimum distance to an hotel if you are in city 13 is 2 (hotel 11). Please notice that the problem ask for the minimum distance to any other hotel, not all the distances.

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

Wow, D was pretty tough for me...Can anyone provide a solution? My only thought was to simulate different possibilities with BFS and use heuristics to lower the search space, but I still timed out.

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

How to solve B? I didn't get any idea

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

    Just print an alternating 01 array. (Convince yourself why this is true)

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

      Kill me :')

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

        We all have felt the same in some contest or the other.

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

      I had thought of this solution but instead of proving it correct I thought it is too stupid solution which will not pass even the pretest.

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

        I also thought it can't be right, but since I didn't have any other ideas, I figured the risk of WA will be worth it on the off chance that it's correct.

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

          Why not? Let x be no. of roses then we have to maximize x(n-x) = nx — x^2. Differentiate and get x = n/2. For segment of even length if we place alternating 01 we will get equal no. Of both the flowers. For odd length segment we will get (n+1)/2 and (n-1)/2 which will maximize the product.

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

            i thought the same way

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

            I thought it can't be right because that solution is too easy for Div2B.

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

    I just printed a n length alternate string and it passed the pretest (01010101010...till n). I hope it passes the system tests.

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

    You need print "01" alternativey. Now why this is the right way. Supposefor some person has start l and end at r. Now what's the max possible answer. suppose you have R roses and L lily. Now R+L=(r-l+1) And we wish to maximise R*L. Standard. Very Standard. It will be maximum when R is as closed to L as possible. Which will be always satisfied by our answer of printing "01". As in every segment abs(R-L)<=1. So this answer is correct.

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

What was Pretest 4 in D?

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

    I think it will be either for n=1 or m=1 type of test case. Or where no of occurrence of each digit always produce -1.

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

How could so many people solve B? Is there anything I didn't keep in mind?

Also, F seems to based on sqrt-decomposition approach, doesn't it?

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

    answer B:"01010101010101..."

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

      Nooooo

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

      But what if

      Input

      2 1

      1 2

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

        The maximum beauty will be 1 with 01 or 10. If two flowers are of the same type, you'll get the beauty of 0 (since one type got no flowers).

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

          I want to die :(

          I thought in "010101..." but did not notice what you said so I discarded that solution >_< .

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

            Chill bro I couldn't even think of it for entire two hours :D

            Goodbye ratings anyway :D

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

        01 is still optimal as it gives 1 as ans. others give 0.

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

        Approach and Proof For B a/c to me. You need print "01" alternativey. Now why this is the right way. Supposefor some person has start l and end at r. Now what's the max possible answer. suppose you have R roses and L lily. Now R+L=(r-l+1) And we wish to maximise R*L. Standard. Very Standard. It will be maximum when R is as closed to L as possible. Which will be always satisfied by our answer of printing "01". As in every segment abs(R-L)<=1. So this answer is correct.

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

    B=1010101

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

    F: Nope segtree on bits I think

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

      Can you express your ideas?

      I tried with sqrt but got completely stuck in the 1st query.

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

    for B, you just have to print alternative 0 and 1.

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

    In B it is always optimal to print alternating ones and zeroes

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

    Its solution is constructive. You just need to output alternate 1s and 0s as they will maximize the product for all segments given a fixed sum.

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

    What????????

    Why didn't I even think of that in B? :<

    Thanks anyway guys ;) kukyo BeardAspirant noobied samyakjain Renaats JustInCase adityakumar3811

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

    I spend all my life to implement a f**king super algorithm ...

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

      Lol. I actually got no idea and decided to try F instead. Worst decision I've ever made :D

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

how to solve C

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

    For every unique element from left to right, add the number of unique elements to the right of it to the ans.

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

    I believe you can keep two vectors, one for the positions of the leftmost occurence of a number, and one for the right. You can iterate over the first vector and sum up all the ones in the second vector that are bigger than it (meaning no intersection) using binary search or c++ upper bound.

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

    for each position find the number of distinct numbers in the range [position+1, end of arr]

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

      3

      1 1 2

      According to you answer would be 3 but it will be 2, right?

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

    It is quite easy with sets in c++.

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

For this contest will have to say don't think too much.

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

What could be testcase 4 of D ?

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

Does the solution to E involve finding the Centroid of the tree? (Centroid in terms of the distance, not in terms of the number of nodes)

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

    You mean center of the tree? Yes.

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

      Take a diameter. And check each k consecutive on it?

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

        I placed the center on the path, then binary searched on the answer. For each such value I accounted for the nodes which needed to be in the path, and tested whether the path was valid (one segment of length at most k). I'm pretty sure that binary search was unnecessary, however.

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

        could you please tell me proof or how you came up with your idea of E .. that is sliding a window of size k on the longest path of tree..thanks

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

          For me,it seemed we can always move towards a global maxima taking suboptimal path and greedily making it better (But no guarantees of it being true.Will be happy if someone can confirm it.)

          Then I proved that answer will exist on diameter by exchange argument.

          Then sliding window is kind of searching complete space.

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

      Yes, the center. Thanks.

      So, after finding the center, do we maintain a priority queue with ascending order of sums of distances the children of a node have to travel to the parent of the node(the parent will have an ice cream store for sure)?

      In the PQ, we first insert the neighbours of the center, then take one node out of the PQ, set an ice cream store there, then insert it's neighbours, and keep doing this until we don't have any stores left to set up?

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

        I believe that should work, as long as you are checking that the stores form a valid segment at every point in time.

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

Too long statements. Surprised with the problem B.

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

I had one interesting idea for E which I want to share, I am really curious will it pass all testcases. I think I have a little strange background of my solution, so it possible I have bug. Anyway here is idea with randomisation:

In case we know one node in the result path, we will always go in subtree which contains furthest node from that node ( if we have two ends, we will choose node with 'better; subtree...)

Now if k < const and diametaroftree < const we can explore paths from each node and calculate best result. Otherwise we can choose const random nodes, investigate them in O(k) and choose best result. For const near 1000 , probability for mistake should be really small.

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

What was the solution for F?

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

How did you solve Div 2 D ?

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

    Hint: Given n and m, if you know the maximum element in the list and the smallest element x whose frequency is not 4*x, you can determine the position of zero in the matrix(if solution exists for given n and m).

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

      I have an interesting idea. let mx=highest value of the elements. if it is odd than 0 will be in (mx/2+1,mx/2+2) position if it is even than 0 will be in (mx/2,mx/2) position now try to build the matrix with 0 in that position for all divisors of n. example: 18 2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1 mx=4 0 will be in (2,2) divisors of 18 are 1,2,3,6,9,18 so we will try to build the matrix where m*n= (1*18) /(2*9)/ (3*6)/(18*1)/(9*2)/(6*3) and position of 0 is (2,2) (I think this solution will work but not sure. just sharing my idea with you. :D Let me know if you find anything wrong in this idea)

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

        if frequency of maximum element is 3 it will fail 0 1 1 1 2 2 3 3 3

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

          It can't be 3. There is no solution for your test case.

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

      how ?

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

        Assume zero appears on the bottom right quadrant, maximum element appears on the top-left corner and element x-1 lies to the extreme right of zero. (You can flip any other solution to get this configuration).

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

Is there a reasonably short way to solve D? My idea was to watch the growth of the sequence of counts of different numbers, predicting what the next number should be assuming that the corresponding rhombus does not hit the edge of the matrix. Then, if the prediction turns out to be wrong (the actual count is lower than the expected one), consider the different cases of edge positions. But those predictions and subsequent pattern matching have tons of corner cases and are ridiculously tedious to implement.

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

    I actually used the same thing. Yes it was hard to implement. But not as many edge cases as you might think. n and m can be interchange. if i,j is center then m-i,n-j being center is also a solution etc. So quite a few cases get handled together.

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

      In problem D,if matrix of i x j gives me correct ans,then,I think j x i will give me correct ans too.Correct me if I am wrong?

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

        Ya that was actually what I meant when I said n and m can be interchanged.

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

    I wasn't sure about TL but it passed. My solution was to stop once you hit first edge, let's call that distance s.

    Now let's look at the biggest number m and iterate over all possible splits m = a + b. Then one edge of rectangle is a+s+1, and if that divides n there's only one possible position for 0. Now let's check that it's correct with bruteforce approach.

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

For those who passed D with >1000ms. Try test n = 840, m = 858, cx = random(1, n), cy = random(1, m).

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

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

what the hell is testcase 4 in D..!!Can't debug..

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

My ratings to me after not solving B. :(

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

Can we solve E by choosing K consecutive segment of nodes in the largest path of tree? Like sliding a window of size K

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

    I think so. Though I used binary search after finding the longest path, not sliding a window.

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

    Yes. https://codeforces.me/contest/1004/submission/40007113

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

    could you please tell me the proof for this idea?

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

      Suppose that you don't choose the K nodes in the maximum weighted path, it means that at a particular node you chose a path that was smaller than the largest path. Now this means that the farthest distance of the node with ice cream will increase. The best way to visualise this is by arranging the tree structure such that it looks like the most weighted path is a straight line and all other sub paths are hanging from each of the nodes in the max weighted path.

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

Did anyone actually solve problem B with a solution different from "01010101..."? That would be hilarious.

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

Unhackable round ! xd

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

    Though that +1 hack really saved my rating... it gave me like 200 ranks.

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

      Lucky you. Some people did not have wrong solutions in their room.

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

    i hacked +1.

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

    D was hackable :D

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

A quick system test considering the number of participants and even quicker ratings update.

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

Why is this code getting TLE in test 52 in problem E? 40007267

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

    Imagine star graph (one vertex connected to other n — 1 vertices). For example lets consider center vertex numbered 1. You will call function llenaDist(1, p) n — 1 times. And function llenaDist(1, p) working in O(n). So complexity is O(n2)

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

legendary speed system test and rating update

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

elijahqi was 4th in standings. After system tests, he is not in the rankings at all. what happened here?

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

Why are long and int of the same limits on the compiler used in Codeforces? In other websites long has wider range than int and equal range as that of long long.

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

Why the answer of problem E for the second sample is 7 and not 6?

If the shops are in : 3, 4, 5.

The minimum distance of node i to any shop is:

Junction 1: Shop 4 — Minimum distance is 6

Junction 2: Shop 3 — Minimum distance is 6

Junction 3: It is a shop — Minimum distance is 0

Junction 4: It is a shop — Minimum distance is 0

Junction 5: It is a shop — Minimum distance is 0

Junction 6: Shop 4 — Minimum distance is 6

Junction 7: Shop 5 — Minimum distance is 2

Junction 8: Shop 3 — Minimum distance is 1

Junction 9: Shop 4 — Minimum distance is 6

Junction 10: Shop 4 — Minimum distance 5

In this way, the answer is 6, isn't it? What is wrong in this solution?

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

Problem B was kind of a one-shot problem. You need to wait till you realise the answer is alternating zeros and ones.

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

easy problems B, C

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

how to solve problem D?

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

Can anyone explain me, why one submission gets AC, and other TL4, they seem to have near the same complexity and idea?

AC code — http://codeforces.me/contest/1004/submission/40000703 My code(TL) — http://codeforces.me/contest/1004/submission/40004156

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

I think there was a mistake in my source code for problem A. But my solution got accepted. Here is the link to my solution: http://codeforces.me/contest/1004/submission/40001844 If i input 4 as hotel number and 2 as difference and 1 2 4 and 40 as the hotel locations,should there not be all locations in between 6 and 38 and the additional 2 locations for two ends? i think my solution did not cover this part. I hope it can be checked and clarified. Thanks

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

    The problem description created this confusion to me also as it said the minimum distance must be d.But when I asked about the same they replied "The distance from new point to the nearest existing point should be exactly d."I wasted a lot of time in this :(.

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

    However, it works because when you compare c[n] — c[n-1] (j = 0, 1, ... n-1) and d * 2, c[n]-c[n-1] is bigger, because c[n] can be everything, something like 1006547729 for example.

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

I'm surprised the rating change was shown in just about one hour after contest end. Thank you to the Codeforces team for reducing the waiting time. Hope to see this improvement in future contests!

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

When you skip B because you have no idea of the right greedy strategy, spend 1h30 on D and at the 1h55 mark understand what B was really asking for...

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

I'm not gonna say this contest is bad because I'm always grateful when there is a new contest, but the problems' difficulty distribution makes no sense: A, B, and C were all the same difficulty (actually A is probably the hardest). It doesn't even test programming skill, just write fast and pray there aren't any bugs and you get +100 rating.

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

    Especially with a troll problem like B. :/

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

how to solve A?

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

    Just open the list "standings", click on anyone's solution and be happy (you'll very soon find the clear to you solution).

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

Problem F is very similar to COCI 2017/18 Round 2, last problem (link to the codeforces blog). The difference is that that there we want the number of ranges with gcd(A[L;R]) = 1, but the same idea will pass (you can look at the comments).

So if anyone doesn't want to wait the editorial, he can check it out.

Link to my code for that problem.

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

Am I the only one who thought about Codeforces Round 439 (Div. 2) and people, who solved B and C but did't solve A which was even more funny than today's B?

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

    I was stuck on A as well. I was really sad that I couldn't even solve A in a contest was thinking of leaving the contest but then saw B and faith were restored. I solved A with a time penalty of 110 (around) points and 150 points attempt penalty.

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

Your crafting.oj.uz ratings are updated!

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

I think pC should replace pA and there should be another pC which reduces the gap between pC and pD. I don't know why contestant are calling pB troll problem because it was nice simple problem. I don't like pA and pC(as C). Also this was my first contest and I learned that "Implementation is a part of competition and it should be a part of preparation".

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

    B was a troll problem because of the answer which wasn't any way dependent on input. There was no need of input of l,r segments, the only n was sufficient to generate the pattern. Even if you didn't know that answer should be alternate 0 and 1, you could prove it mathematically to maximize to the fact that in any segment (even number of elements), there should be the equal number of two type of roses for the function to yield the maximum result.

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

      It's a competition. I bet that many people have wasted time thinking about l & r. Also it requires finding maximum value attained by downward parabola which I think is okay for Div2 pB .

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

        The problem was tricky. Very very simple differential calculus is required for mathematical proof. After thinking of approach, the main time wasted was checking under various test cases if approach really is correct or not.

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

          Why check for various test case if you have proof

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

            Could not believe that the answer could be this simple.

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

I was able to solve problems A and B but not the problem C. I know it is quite easy. But I somehow couldn't explain myself the logic in my mind. All I could think was of a prefix array will the ith index in it denoting the no. of the unique elements to the left of it in the array. Can someone explain the solution to C? It can be short too, I kind of have a rough idea after looking at the codes of other participants who used sets and maps for the same.

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

    You probably have guessed it right. I first created a prefix array which gives me the unique elements to the right of an index i. Then we iterated from i=0 to i=n-1, and for each unique element I added the prefix sum from it. Here's the pseudo:

    for(i=0 to n-1)
{
if(!marked[a[i]]){
ans+=pre[i]
marked[a[i]]=true
}
}
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i too figured it but unable to implement it .......it sucks if this happens

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

I face a problem with Pypy on CF.

I got RE with exit code is 13131313 if I import random library. The same code is AC with python

http://codeforces.me/contest/1004/submission/40007659 — AC with pypy3. http://codeforces.me/contest/1004/submission/40007677 — RE with pypy3 because of import random. Exit code is 13131313 http://codeforces.me/contest/1004/submission/40018157 — AC with python3, (has import random also).

Any help?

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

After 2 years of python I forgot that I have to use long long instead of long. :-D good bye good rating.

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

Editorials are not here....

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

guys can anyone help me with problem C because in that problem i m getting a TLE but still after going through the editorial also i m unable to figure it out...........PLz help

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

    Iterate from last element. Keep track of number of different elements before current element and also make sure not to count pairs (*,y) multiple times you can do it having a boolean array

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

    The complexity of your solution is (1e5*1e5).It will give you TLE.

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

      can u let me know a simple way of doing that becoz i m new so dont know much tricks to over come these issues

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

101010101 = LOLOLOLOL

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

Editorial here...

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

Can anyone tell me what is wrong with this submission? http://codeforces.me/contest/1004/submission/40022548

→ Reply