Блог пользователя arsijo

Автор arsijo, 3 месяца назад, По-русски,

Всем привет!

Лето... Прекрасная пора для поездок на отдых, прогулок с друзьями, новых открытий и, конечно же, написания новых увлекательных контестов на Codeforces. Поэтому, я предлагаю к вашему вниманию мой новый Codeforces Round #495 (Div. 2) с интересными задачами и не менее интересными разборами, который состоится в 05.07.2018 19:35 (Московское время). Если ваш рейтинг меньше 2100, этот раунд будет для вас рейтинговым, иначе — вы можете участвовать вне конкурса.

Хочу поблагодарить Михаила MikeMirzayanov Мирзаянова за помощь в подготовке и за системы Codeforces и Polygon. Также Ильдара 300iq Гайнуллина, Дмитрия _kun_ Саютина, Даниила danya.smelskiy Смельского, Chin-Chia eddy1021 Hsu и Kevin ksun48 Sun за тестирование задач.

Вам будет представлено 6 задач и 2 часа на их решение. Разбалловка будет объявлена ближе к началу раунда.

В этом раунде вам предстоит помочь девочке Соне с ее ежедневными проблемами. Удачи вам в этом!

UPD. Разбалловка 500-1000-1500-2000-2500-3000.

UPD. Поздравляем победителей!!!!

Место Ник Баллы
1 EZ_fwtt08 7892
2 milisav 5550
3 VisJiao 5294
4 Jatana 4832
5 wasyl 4762
 
 
 
 
  • Проголосовать: нравится  
  • +379
  • Проголосовать: не нравится  

»
3 месяца назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится -75 Проголосовать: не нравится

i hope good statement and many hacks

»
3 месяца назад, # |
  Проголосовать: нравится -38 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится -112 Проголосовать: не нравится

Is it rated??????

»
3 месяца назад, # |
  Проголосовать: нравится -58 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +144 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Unimaginably, they've mentioned Mike.

»
3 месяца назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится -66 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится -38 Проголосовать: не нравится
  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 месяца назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится -20 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

kun? Another Mathforces round?

»
3 месяца назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

I hope codeforces work properly today.

»
3 месяца назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

Where is KAN for help to prepare the round.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

I smell math for this round either

»
3 месяца назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

who is sonya??

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Down voting contest is going on. :v

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

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

see my graph

»
3 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Problems are loading very slow. Is it just me?

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится +23 Проголосовать: не нравится

#define int long long

Are you serious?

»
3 месяца назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

very confusing statement

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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 месяца назад, # |
Rev. 2   Проголосовать: нравится +101 Проголосовать: не нравится

Attempting Problem D after successfully submitting Problem C:

»
3 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Простите, но это было очень скучно, т.к. проблемы D и E остановили почти всех, а A B C были достаточно простые.

»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    No, you are not alone

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      "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 месяца назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        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 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          "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 месяца назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            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 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          "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 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      Kill me :')

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

What was Pretest 4 in D?

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What an awesome contest. Thanks!

»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

how to solve C

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is quite easy with sets in c++.

»
3 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

What could be testcase 4 of D ?

»
3 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    You mean center of the tree? Yes.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится

          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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Too long statements. Surprised with the problem B.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the solution for F?

»
3 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

How did you solve Div 2 D ?

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      how ?

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 месяца назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Чето в последнее время див 3 это див 2, див 2 это див 1, а див 1 это тоже див 1, но с еще более плохими задачами.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Согласен. С появлением div. 3 задачи div. 2 стали сложнее. Очень даже.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      div3 никак не влияет на div2, сомневаюсь, что это два явления связаны.

»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

My ratings to me after not solving B. :(

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    could you please tell me the proof for this idea?

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Unhackable round ! xd

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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)

»
3 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

legendary speed system test and rating update

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

easy problems B, C

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve problem D?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

test9 on problemE is so danteng

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I'm surprised rating change was given in just about one hour. Thanks to the Codeforces team for reducing the waiting time.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve A?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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 месяца назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Your crafting.oj.uz ratings are updated!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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".

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 .

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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
    }
    }
    
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I suppose I have a relatively easy way to solve D. First of all, let d be the distance from zero to the nearest side of the rectangle. Then we can find it as following: numbers 1, 2,... d must occur exactly 4, 8,... 4*d times, while d+ 1 will occur less then 4*(d+1)

Next, notice that the max numbers is the distance to the furthest corner. Now check all pairs (m, n) such that mn=area. Notice that we can find position of zero By distance from nearest rectangle side and distance from furthest corner. Now simply check if that position is ok (I had a special function for checking if specific m, n, x, y were ok. That's it

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Editorials are not here....

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone help me with problem C

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 .

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Почему в Е нельзя взять позицию, с минимум из максимумов дистанций, затем жадно брать вершину с наибольшей оставшейся дистанцией (k-1) раз?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Разобрался, это решение ищет ответ с не простым путем.

»
3 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

101010101 = LOLOLOLOL

»
3 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Editorial here...

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

разбора не будет?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?