arsijo's blog

By arsijo, 3 months 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 _kun_ 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  

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

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

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

i hope good statement and many hacks

»
3 months 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.

»
3 months 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)

»
3 months ago, # |
  Vote: I like it -112 Vote: I do not like it

Is it rated??????

»
3 months ago, # |
  Vote: I like it -58 Vote: I do not like it

I hope problem statement will be as short as the announcement. By the way best of luck to all the contestant. :)

»
3 months 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 .

»
3 months 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

»
3 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Unimaginably, they've mentioned Mike.

»
3 months 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.

»
3 months 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...

  • »
    »
    3 months 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?

»
3 months 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.com/blog/entry/59942?#comment-436969.
»
3 months ago, # |
  Vote: I like it -20 Vote: I do not like it

It is shortest and best announcements according to that contest will be better.....

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

Hope to the problem statement will be too much interesting. Best of luck for all.

»
3 months ago, # |
  Vote: I like it -21 Vote: I do not like it

I hope we will get some flavor of Football. It will be more interesting not in just watching the game but also solving some problem related to them. Who knows, we may score better :p

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

kun? Another Mathforces round?

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

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

»
3 months ago, # |
  Vote: I like it -19 Vote: I do not like it

I hope codeforces work properly today.

»
3 months ago, # |
  Vote: I like it -24 Vote: I do not like it

Where is KAN for help to prepare the round.

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

I smell math for this round either

»
3 months ago, # |
  Vote: I like it -28 Vote: I do not like it

who is sonya??

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

  • »
    »
    3 months 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.

»
3 months 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.

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

Down voting contest is going on. :v

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

Most of the comments are hidden!! I feel something is 'not usual' gonna happen today

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

After looking so many disappeared comment.Now i realised Thanos did right.Half of earther don't deserve to live on this earth

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

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

»
3 months 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....?

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

    you have chosen wrong handle maybe :)

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

    -ve infinity is still king of the negatives.

»
3 months 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

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

    they prefer easy ones, :/ thinking they will be tourists one day and they wont :/

»
3 months 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

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

Problems are loading very slow. Is it just me?

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

#define int long long

Are you serious?

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

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

»
3 months 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

»
3 months 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.

»
3 months 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

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

very confusing statement

  • »
    »
    3 months 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 :(

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

Attempting Problem D after successfully submitting Problem C:

»
3 months 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? -_-

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

    No, you are not alone

  • »
    »
    3 months 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

    • »
      »
      »
      3 months 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?

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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".

          • »
            »
            »
            »
            »
            »
            3 months 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.

        • »
          »
          »
          »
          »
          3 months 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.

»
3 months 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.

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

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

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

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

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

      Kill me :')

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

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

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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.

        • »
          »
          »
          »
          »
          2 months 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.

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

            i thought the same way

          • »
            »
            »
            »
            »
            »
            2 months 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.

  • »
    »
    3 months 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.

  • »
    »
    3 months 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.

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

What was Pretest 4 in D?

  • »
    »
    3 months 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.

»
3 months 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?

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

    answer B:"01010101010101..."

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

      Nooooo

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

      But what if

      Input

      2 1

      1 2

      • »
        »
        »
        »
        3 months 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).

        • »
          »
          »
          »
          »
          3 months 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 >_< .

          • »
            »
            »
            »
            »
            »
            3 months 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

      • »
        »
        »
        »
        3 months 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.

      • »
        »
        »
        »
        3 months 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.

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

    the answer is 01010101.... I hope this clears main tests.

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

    B=1010101

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

    F: Nope segtree on bits I think

    • »
      »
      »
      3 months 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.

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

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

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

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

  • »
    »
    3 months 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.

  • »
    »
    3 months 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 ;) laonianrencaozuo BeardAspirant noobied samyakjain Renaats JustInCase adityakumar3811

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

    I think greedy solution works, alternate one's and zero's are the best way to split, irrespective of every thing.For any given number n,product is max when the numbers are equal(n is even) or n/2 and n/2 +1

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

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

    • »
      »
      »
      3 months 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

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

What an awesome contest. Thanks!

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

how to solve C

  • »
    »
    3 months 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.

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

      this will be O(n^2). That is why didn't even try this approach

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

        You can do this in O(nlogn)... Initially traverse from right to left keeping track of unique elements using set. And then traverse from left to right, (using a new set) for every unique element just add the value of the number of unique elements to right of it.

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

        I passed using binary search, for every unvisited element start from left say index 'i', find the number of elements on the right(>i) such that their first occurrence(considering from right) is not equal to or before current our index i, i.e their first occurrences should always come after current index 'i'.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it
  • »
    »
    3 months 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.

  • »
    »
    3 months 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]

    • »
      »
      »
      3 months 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?

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

    It is quite easy with sets in c++.

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

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

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

What could be testcase 4 of D ?

»
3 months 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)

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

    You mean center of the tree? Yes.

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

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

      • »
        »
        »
        »
        3 months 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.

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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.

    • »
      »
      »
      3 months 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?

      • »
        »
        »
        »
        3 months 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.

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

Too long statements. Surprised with the problem B.

»
3 months 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.

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

What was the solution for F?

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

How did you solve Div 2 D ?

  • »
    »
    3 months 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).

    • »
      »
      »
      3 months 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)

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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.

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

            yes but his algorithm doesn't check for impossible test cases

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

      how ?

      • »
        »
        »
        »
        3 months 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).

»
3 months 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.

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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?

      • »
        »
        »
        »
        3 months 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.

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

    I could not solve the question but thought something.
    One(or all) of corner/s will have the maximum element, hence the maximum element can occur either 1,2 or 4 times only.
    if it's frequency is 1 then it will occur at corner and we can get the coordinates of (0,0)
    if it's frequency is 4 then (0,0) will in the center of the matrix
    if it's frequency is 2 then we have some possible combination where i got stuck.
    If anyone thinks this can be , it would very helpful

  • »
    »
    3 months 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)

  • »
    »
    3 months 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.

»
3 months 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).

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

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

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

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

My ratings to me after not solving B. :(

»
3 months 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

  • »
    »
    3 months 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.

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

      how did you write check function of bs?

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

    could you please tell me the proof for this idea?

    • »
      »
      »
      2 months 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.

»
3 months 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.

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

    not entirely different but I sorted ranges based on l and r. Then for each ranges from l to r put alternation 0/1 based ans[l].
    feeling stupid now

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

    I solve it with different idea.

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

      Only difference i recognize that your code writes 101010... instead of 010101...

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

        yeah u are right.... But i told that "I solved it with a diff idea" .

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

    let us hope that the author's solution gives the same output as in sample test cases, otherwise, they are just camouflage, and let us pretend that the problem is more of solved using logical proof rather than scratch and win strategy

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

Unhackable round ! xd

  • »
    »
    3 months 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.

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

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

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

    i hacked +1.

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

    D was hackable :D

»
3 months 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.

»
3 months 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

  • »
    »
    3 months 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)

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

      Thanks! Do you know how can i calculate this distances more efficiently?

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

legendary speed system test and rating update

»
3 months 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?

»
3 months 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.

»
3 months 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?

»
3 months 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.

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

easy problems B, C

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

how to solve problem D?

  • »
    »
    3 months 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)

»
3 months 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.com/contest/1004/submission/40000703 My code(TL) — http://codeforces.com/contest/1004/submission/40004156

»
3 months 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.com/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

  • »
    »
    3 months 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 :(.

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

      Well they specified minimum distance. So it should cover the points in between. I submitted considering to be exactly d but then i realized that all ppints should be there for large difference

  • »
    »
    3 months 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.

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

      Thats a good point to consider,but still i think my code won't work. Cause i specifically increased only 2. That means the locations added can never be more than 2 at a time for a single case of difference

»
3 months 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!

»
3 months 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...

»
3 months 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.

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

    Especially with a troll problem like B. :/

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

how to solve A?

  • »
    »
    3 months 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).

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

    you can use xi + d , xi — d for i = 1..n without overlapping

    xi + d must be < x[i+1] so it is good

    just you have to find if the space between tow xi is fitable

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    int n,d;
    int a[200];
    set < int > st;
    int main()
    {
        speed;
        cin >> n >> d;
        ff(i,1,n) cin >> a[i];
        int ans = 2; // x1 - d , xn + d
        ff(i,1,n-1)
        {
            if(a[i]+d<a[i+1]-d) ans += 2; // xi + d , xi+1 - d
            else if (a[i]+d == a[i+1]-d) ans += 1;
        }
        cout << ans << endl;
    
        return 0;
    }
    
»
3 months 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.

»
3 months 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?

  • »
    »
    2 months 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.

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

Your crafting.oj.uz ratings are updated!

»
2 months 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".

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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 .

      • »
        »
        »
        »
        2 months 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.

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

          Why check for various test case if you have proof

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

            Could not believe that the answer could be this simple.

»
2 months 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.

  • »
    »
    2 months 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
    }
    }
    
    • »
      »
      »
      2 months 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

»
2 months 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.com/contest/1004/submission/40007659 — AC with pypy3. http://codeforces.com/contest/1004/submission/40007677 — RE with pypy3 because of import random. Exit code is 13131313 http://codeforces.com/contest/1004/submission/40018157 — AC with python3, (has import random also).

Any help?

»
2 months 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.

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

Editorials are not here....

»
2 months 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

  • »
    »
    2 months 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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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

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

        Okay, The first thing you have to do , "Learn how to calculate time complexity". The complexity is more important than the solution. Watch it on YouTube or google it .

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

101010101 = LOLOLOLOL

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

Editorial here...

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

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

»
2 months ago, # |
  Vote: I like it -13 Vote: I do not like it

The comment is hidden because of too negative feedback, click here to view it

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

Problem A, in the second sample test case, why aren't cities with coordinates 14 and 15 part of the cities Sonya can build hotels on?

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

    distance of 14 from 11 is 3, and distance of 15 from 18 is 3, but minimum distance should be 2.