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

Всем привет!

В четверг 13 июля 2017 года в 18:05 по московскому времени состоится Codeforces Round #424 для обоих дивизионов. Часть задач будет совпадать с задачами Финала VK Cup 2017, кроме того, команда Codeforces подготовила еще несколько задач для проведения полноценного раунда.

Во втором дивизионе будет предложено шесть задач, в первом — пять, три из этих задач будут общие. Задачи этого раунда предлагали, готовили и тестировали: send_nodes, akvasha, ilya_the_lamer, fcspartakm, Perforator, MikeMirzayanov, PavelKunyavskiy, qwerty787788, Belonogov, izban, tourist, vepifanov, AlexFetisov, winger, Errichto, Gassa, naagi, ashmelev, Endagorion, ifsmirnov, Arterm и я. Большое спасибо всем, кто помогал с задачами!

В этом раунде также будут разыграны призы от компании ВКонтакте! А именно, среди тех участников раунда, которые решат хотя бы пять задач во втором дивизионе, или хотя бы две задачи в первом дивизионе, будут случайным образом выбраны пять, и они получат сувениры чемпионата. Нет никаких ограничений на страну или язык для получения приза. Требования участия в чемпионате тоже нет, приз может выиграть любой участник раунда. Точный алгоритм определения победителей опубликуем до начала раунда.

Удачи!

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

Div. 1:

  1. TakanashiRikka
  2. moejy0viiiiiv
  3. Petr
  4. anta
  5. matthew99

Div. 2:

  1. ccz181078
  2. repeating
  3. ioyeoa
  4. ReaLNero
  5. beet

Разбор тут.

Соответствие задачам с VK Cup 2017 - Финал:

Определены обладатели сувениров, поздравляем!

Место в списке Соревнование Место Хендл
65 830 65 halin.george
69 830 69 Neil
153 830 153 BigBag
265 830 266 whczr
320 830 323 Rydberg
 
 
 
 
  • Проголосовать: нравится  
  • +235
  • Проголосовать: не нравится  

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

I wonder if it is frowned upon to compete in a codeforces round during work? I guess we'll find out, I can't miss VK Finals!

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

Errichto is back!

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

By the way, the algorithm for choosing winners is the same as in the previous round. The winners of the previous round will be chosen with the use of the first place score in this div. 1 round!

  1. List all participants from div. 1 who solved at least two problems from top to bottom of the standings, ties broken by the time of last AC.
  2. List all participants from div. 2 who solved at least five problems from top to bottom of the standings, ties broken by the time of last AC.
  3. Append the second list to the back of the first list.
  4. Use the following code to generate the indices of the winners in the resulting list. The seed is the score of first place in the next div. 1 contest. The length is the length of the list.
code
»
4 месяца назад, # |
  Проголосовать: нравится -112 Проголосовать: не нравится

send_nodes is involved? Damn, hope it won't be unrated :)

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

    Hope, history will not repeat because in this contest, there are 22 problem setters and testers.

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

Upvote this comment if you want high rating!

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

Proposed, prepared and tested by 22 :3

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

I used binary search to pass div1.E (have been accepted). but later, I found it was probably wrong. Can someone provide me with a data or prove it is right? thanks! code goes here: http://codeforces.com/contest/827/submission/28488942

Sorry, the question i asked in the wrong place. The contest i mentioned above is div1 #423

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

Am I the only one who can't open any other user's submission page like submissions

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

This contest is not listed for some reason at clist.by

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

Third round by send_nodes .. hope that it won't end up unrated. xD

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

    I'm sorry dude, but it is how cf works in community...
    You get tones of downvotes if your rating's low...
    You can't hold a contest because your rating's low...
    There might be some issues if you hold a contest and your rating's low...
    I don't have an idea how to improve my rating after years being on this website, Nor to be better in community. Hope someone help me in some new ways... . And something else, please think about it before starting downvote with millions of account(fake or real :()

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

if @tourist tested the problems then round will not have any issues(like the rounds 420 & 421). :3

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

I already participated two days ago in the VK contest. When I uploaded my solution the system showed that it passed the tests, but after the contest it said that it exceeded the time limit. Does it work always the way, that you don't see a time limit exeeding during the contest or was it due to the fact that I was an unrated participant?

Anyway, best luck and fun to all of you today :)

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

    It was because you solution was not fast enough to pass the remaining system tests ! during contest only pretests are tested that's why it shows pretest passed ! hope you got it

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

    During the contest, your code is tested on a subset of the final tests, called PRETESTS. After you have passed the pretests, you can lock your solution and then view other participants' codes and try to hack them. Others who have locked their solutions can view your code irrespective of whether or not you have locked your code. Once the coding phase is over, your solutions will be tested on the entire set of tests. This phase is called system testing.

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

    It is the system testing, in the round, the judge runs only about 15 cases on your code, if your code passed you got PREtests passed. And after the contest, they run around another 100 test on your code and give you your final verdicts. You can also learn about hacking a solution.

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

22 problem setter & tourist among them ... this contest must be super good.

Best of luck to all participants in both divisions, i'll try to read all problems this time ^^

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

    Why does people downVote your comments without any reason (maybe even without reading your comment) ?

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

hope there will be no delay of 10 minutes.

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

People who code correct in their first attempt, how do you do it?

I know how to solve A, B, C, D, E but I can't code D in 25 minutes, even though it's so simple, and I've done similar problems so many times!

Btw is E too easy, or am I missing something?

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

    Can you share your solution to E

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

      You can simulate it using binary indexed tree and std :: set.

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

      Calculate distance from i to i+1 on it's right and left. Then add answer from right and left for each i sequentially. Remember to decrease count of alive elements on left and right. You can use segment tree.

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

    E is pretty easy. It's a standard fenwick tree problem. I'm ashamed I couldn't solve C though T_T

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

Please check OlRed2017's submissions. It doesn't look like only one person is participating.

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


Hi guys! Unfortunately CF API is turned off, so CF-Predictor couldn't obtain data from codeforces and make rating change prediction. API should be enabled back after this round, so I hope CF-Predictor will work fine:)

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

Can someone provide me hack testcase for my solution A div 1.

Hacked code : https://pastebin.com/0hYtTQcP

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

sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
Rip rating :(

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

Hack Case for Div2 A ?

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

How to solve C and D (Div 2)?

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

    Eagerly waiting for the replies:) Can someone explain there idea please

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

    D is very simple question of basic DP. sort all men and keys on the basis of their positions and then u have dp state as dp[men][key] = min(max(time taken to that men after picking that key , dp[men+1][key+1]) ,dp[men][key+1]). and after all recursive calls ...your final answer is dp[0][0].

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

      can you please tell why the dp solution works only when you sort the arrays? not able to figure out how does that helps in finding out the optimal answer

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

        if you don't sort the arrays than after allotting a key to a guy you have to iterate from starting among all the available keys thus your solution would be of O(n*k*k) but after sorting u can do it in O(n*k)...

        Let see how it works, suppose you have two guys at x1 and x2 (x1<x2) and keys at k1 and k2 (k1<k2) and y be your final destination.. the total time you will need from keys to y will be same i.e abs(k1-y)+abs(k2-y) no matter which key you give to whom.. but if u assume all cases like k1<=y<=k2 ,y>k2 ,y<k1 then you can see in each case it is optimal to give k1 to guy at x1 and k2 to guy at x2.. you can generalize it...I can proof it generally but it is hard to write here ..try yourself to generalize it..

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

    I solved D using binary search + Maximum matching

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

      Can you please elaborate .

      Initially I thought the problem was an instance of Assignment Problem , but then realised that we need to minimise the maximum instead of the sum.

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

        Do a binary search for the answer, for each value mid you need to construct the graph as following:

        if the man at index i can reach the key at index j and then return from the key at index j to the office, then you can add an edge between the man at i and the key at j now you just need to do a maximum matching on the resulting bipartite graph, and check if this matching is equal to the number of people.

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

      Hi, can I ask you about time complexity of your code?

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

        The matching works in O(n*k) so you just need to add log because of the Binary Search.

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

          Which algorithm do you use for finding maximum bipartite matching? if you use hopcroft-karp algorithm your code's time complexity will be O(sqrt(V) * E). Maximum of E in worst case is n * k. I think test cases was weak.

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

    For problem D:

    I guess that the chosen key should be a consecutive n keys segment.. I don't know whether it will pass, but it seems pretty simple..

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

    I solved D as follows: It's optimal to use a set of keys that are neighbours. Sort the keys, sort the people. Let the rightmost person go get the rightmost key, etc. Try every key as rightmost key.

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

      Yup this is actually correct and by far the simplest solution of D.Can anyone please give me the proof of this solution and why this always works irrespective of the location of the office.

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

      I think it can be done faster using trinary search over choices where leftmost key from set of keys that are neighbours is. For i-th person, if we will look how length of his path to key and then to office is changing while we are changing leftmost key from set of keys that are neighbours, that length should decrease while i-th key from chosen set of keys is on the left of office, and then increase when i-th key from chosen set of keys is on the right of office. So length of path of i-th person is increasing first and decreasing later. So time when all people get to office (which is maximum of lengths of paths over all persons) also is increasing first and decreasing later, so we can use trinary search. It should work in O(n*log(k)) (not including sorting). I didn't implemented that solution during contest because O(n*k) worked.

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

How to solve C ??? I am so ashamed I could not solve it whole contest :(

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

    Lets say your path starts at 0. Create array for its values (adding a_i). Now make some path value to b_0.

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

      Sorry But I do not get it :( Please explain in a bit detail !!

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

        Lets make array k[n] k[0]=0; k[i]=k[i-1]+a[i]. When you know you will pass thru b[0]. So lets iterate j (0, n) and now you will have possible route c[i]=k[j]-b[0]+k[i] or smth. similar. Check if route is good. I did use some sets so it was O(kklogk)

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

    You know b[0] must be after some judge i, so check for every position i, if this could work in linear time

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

      Height of stupidity of mine !!! I was checking for every b,instead should have checked only for a single b !!!! That is too much stupidity :( Anyways Thanks yassin- and tautsjasiunsas

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

        That is exactly what i was thinking( checking for every b) and i knew it was gonna TLE so i didn't code it cus it was obv k*n*n :C

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

    let us get the prefix sum for all A's, now sort them. then get the value of all B's and sort them. now let us say the max value in B is x, now for x to be at position i, the initial value will be x — pref_sum[i]. then using this initial value generate the the array and check whether all numbers come in b.

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

      I just got it accepted !!!! I was so close .. Due to C ,I did not try D and D was easier than C :( (Atleast DP solution was ... ) Anyways Thanks satylogin

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

very tight time limit for div1 D :(

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

    Yeah. I got TLE on pretest 12 :(

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

    You can preprocess it?

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

      Do you think this was intended to compute 400 numbers and write them on the source code?

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

        You are making it sound as it is some rocket science, but in fact it is very common technique

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

          very common technique but was not intended in this problem, and there's no point let participants do it instead of just submitting their dp solution.

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

    There's a k^2 log k solution though

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

      What do you imply? if my O(n^3) sol should get TLE then all participants' O(n^3) sol should get TLE too. but that the same solution gets TLE with some people while gets AC with others is too unfair.

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

        It's awkward that 400 initially ran under the time limit, but 399 failed in main tests later. Has anybody managed to make O(N^3) pass in Java?

        (Yes, you can preprocess or you can use FFT to speed things up, but n<=400 suggests n^3 is fine.)

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

      Can you please elaborate on it, send_nodes :^)

      I am very curious how you change the DP to be k^2 log k

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

        Normal dp is like dp(i,j) giving number of ways to choose j non-intersecting paths in a tree with height i. Slowest part of computing the DP is finding out the number of ways to get x non-intersecting paths from the left and right subtrees. It's important that you can multiply all the dp values for trees of height i-1 with itself in a polynomial mult. fashion to get these number of ways, and you can use these results for dp(i,p) for all p. So it's just k^2 log k with FFT

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

What a weak set of pretests are there in A.

for (int j = 0; j <= k - n; j++) {
    int t = 0;
    for (int i = 0; i < n; i++)
        _max(t, abs(b[j] - p) + abs(a[i] - b[j]));
    _min(res, t);
}

Verdict: Pretests passed. Should be

abs(b[j + i] - p) + abs(a[i] - b[j + i]).

Noticed my mistake after a solution was blocked.

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

    Pretests are so weak that my solution without sorting passed. And even wasn't hacked :( RIP rating

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

    For Div 1A / Div 2D Not only pretests, I saw a wrong solution passing the system test.

        ll res=INT_MAX;
        sort(a,a+n);
        sort(b,b+k);
        for(int i=0;i<k;i++)
        {
            ll ans=0;
            for(int j=0;j<n;j++)
            {
                ll tmp = abs(a[j]-b[i+j]) + abs(b[i+j]-p);
                ans=max(ans,tmp);
            }
            res=min(res,ans);
        }
    

    It can be seen that for array b index will reach to n+k whereas b can have max index possible till k.

    Link to Code

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

For D could you do DP with the states being the number of people that got to the office and the hashed state of the array of keys? That was the only solution I could think of in contest.

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

Is this idea correct for div2 D? you binary search for the answer. for a certain value m, you call a function that returns true if the total number of keys such as the distant from a dude to the keys <= m, otherwise false? tried to implement it but didnt make it and i dunno if it's correct

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

    I just did sort :D Use some interval of keys and map each key to people :D

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

      So the best case is always the one where we're allocating n keys lying next to each other? How to prove that?

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

        Its yasy to see what if a wants key B and b wants key A and a>b and A>B whay need to swap keys. Ok, no intersecting lines. Lets say we need a keys left to the office. if some key from a to the left is not used, you can simply shift every to the left of that key to one in the right of those and get (maybe) better result. Same with the right. So we just get some segment of size n around the office.

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

          Thanks for the explanation. It's still not super obvious thing to me (I have to look over some different cases to check your first point for example) but it's much better than "You have to understand" part in official analysis :) Looks like I'm really not good with greedy tasks like this.

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

    I think your approach is wrong. Try this test.

    2 2 1000
    1 1000
    1 2
    

    Notice that both keys are close to the first "dude" but the second "dude" is far away from keys and he needs to pick one of them.

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

      what if we count the number of distinct keys?

      EDIT: ok, i understand what i did wrong, thank you!

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

        What do you mean by count the number of distinct keys. Notice that the problem you need to solve if you perform binary search is a maximum matching between keys and "dudes". But the graph is not random enough so you can perform a greedy. For each of the "dudes" you have an interval where he can look for the key. You need to cover all the intervals with keys inside it. It is a classical greedy problem. The overall complexity will be O(n * m * log(L) )

        Probably that solution fits in time, but there is a dynamic programming approach where each state dp[i][j] represent the best solution for the first i "dudes" using the first j keys. (This works after sorting the "dudes" and the keys). The overall complexity of this solution is O(n * m) since each state can be computed in O(1) if all previous states are already computed.

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

          can you please tell why the dp solution works only when you sort the arrays? not able to figure out how does that helps in finding out the optimal answer

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

            Lets say there are any two person (a and b) and two keys (c and d) and we want to link this two persons with this two keys. Denote pi and kj as the positions of person i and key j respectively. If pa < pb and kc < kd the following inequality holds:

            |pa - kc| + |pb - kd| ≤ |pa - kd| + |pb - kc|

            So person a will take key c and person b will take key b. Extending this argument to the whole group, we claim that if person i is linked with key j all persons before i need to be linked with keys before j, and now you may apply dynamic programming. 28508775

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

              let's say people are at = pa=10 & pb=20 and the keys are at ka=50 kb=60 kc=70. Now according dp solution if i decide to take kb for pa, i must choose kc for pb(or any other key after kb). But here choosing ka for pb should be optimal, isn't it ?

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

      Answer 1996?

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

What is pretest 5 div2e?

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

Am I the only one who tried to solve Div2D using greedy approach?(sort each man by max distance from p and select best possible key)

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

So, after contests, can someone provide mapping between those problems and VK Cup ones?

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

Could D div1 be solved computing recursively the number of paths and the number of pairs of paths for each height? :((

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

    No. Informally, for pairs of paths you need triples of paths. Consider following situation: you want to count pairs of non-intersecting paths where both are in the same subtree except one of them touches root and goes down again (to the same subtree). If root is removed, this construction becomes a triple of non-intersecting paths.

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

      You're right, thanks, I got lost in contest hype + too many cases not well ordered. Thanks

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

why this submission of DIV2A didn't fail test '1 2'
shouldn't condition w[r] < w[r-1] be checked before 'r > 0' and throw ArrayOutOfBounds?

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

Hack Cases for div2 A 3

10 8 8 output — NO

4

1 2 3 4 output YES

7

1 2 3 4 3 3 1 output : NO

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

Is WA in a sample which is not a pretest 1 costs WA ?!!!!

KAN

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

it's like this is the slowest system test ever |:

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

Can someone describe the solution for D?

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

    Consider the following (more general) problem:

    For every T from 1 to K and for every P from 1 to K, calculate how many different sets of P disjoint paths there are in a tree of size T.

    It turns out that you can calculate these values easily using answers for smaller trees.

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

    dp[i][j] means number of sets of j disjoint paths in a tree of height i

    The final answer is dp[n][1], now to compute dp[i][j] you have to consider many cases:

    1- select total of j-1 paths from the left and right subtrees and let the root be the j-th path

    2- select total of j paths from the left and right subtrees and either let the root be at start/end of some of the paths or let the root be not involved in any path

    3- select total of j+1 paths from the left and right subtrees and merge two paths into one path using the root node as a node between those two paths

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

I can't believe I failed to pass div2 A. This is quite embarrassing

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

Div1 A could be solved in O((n + k)*logp):
We can run binary search on answer. For fixed time we can for every person define the reachable segment where he can come and then return to the office. Then we need check if we can assign different keys for each segment. It can be done greedy in O(n).
Accepted solution

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

    Can you please explain the greedy part a bit more in detail. I tried a similar method but then messed up in the greedy to submit a stupid code.

    Suppose I am checking whether time 'x' is possible, I just concluded "true" if there are "n" distinct keys which can be collected in 'x' time and "n" people can reach office using come key in 'x' time. "n" is the number of people.

    Thanks in advance :)

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

      We can sort keys and segments by left end, then iterate over segments and assign to current segment leftmost unassigned key that lies inside it. If there isn't such key, chosen time is not enough.
      Also we even don't need to sort segments every time. We can just sort people at the beginning, because all segments are linearly expand while time changes.

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

For God Sake when you wanna add pretests, add them strong not so easy and stupid, for Div.2 D, I wrote:

match[node]=1;
match[nx]=1;

instead of:

match[node]=nx;
match[nx]=node;

And still I got it pretests passed :\ I can't believe it

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

Can anybody please tell me what's wrong with my submission on E problem? Getting WA on 5th pretest. 28522539

UPD: Nevermind, stupid mistake

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

How to solve Div 1 C ?

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

    Basically problem is asking to maximize d such that:

    We can do some algebra to get:

    The right hand side doesn't depend on d, so basically we can consider it some constant C and just try to find the maximum d such that .

    Now, if this were monotonic, we could find d easily using binary search. Unfortunately, it's not, because is decreasing while d is increasing.

    The trick here is that there aren't many distinct values of . In fact, for any such ai there are only such distinct values. Anyway all the possible distinct values are given by i and for all .

    So what we can do is get all the possible distinct values of and also the bounds l and r such that l ≤ d ≤ r gives that specific value. Now, intersect all these ranges. (It seems like a lot, but actually it's only about different ranges.) The new ranges will be [l, r] for which all are constant.

    Now, for each range, we can now binary search d within the range; since all are constant, we know will be monotonically increasing. Actually we don't even need binary search at this point, but at least binary search requires less thinking. (Make sure to preprocess all the sums for each range before doing the binary search.)

    The runtime should be or something along these lines.

    If it helps, here's my code. 28521138

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

      Hi! Thanks for provided analysis of this problem. I looked into you code and I have a question about its complexity.

      It looks like your solution is actually.

      You have ranges (I'm pretty sure this value is much smaller after perfoming unique, but I can't see obvious reasons why it should be ). After you compute just iterating through initial array for every range. This is the slowest part of your algorithm and it takes .

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

        You're right; thanks for pointing this out! My code specifically is actually with very low constant factor, so it still passes.

        But actually there is a way to knock out the extra n factor make it run in around , with some log factors, using some clever bookkeeping.

        First we will need to find all the ranges with all constant like before. Now we initialize all the sums to zero, then we can do the  + v,  - v prefix sum trick; for each ai we find all the possible values of and the ranges [l, r] giving each of these values. For each range, we can then just add to l and to the one after r in the sum array. We can find locations of these l and r in the sum array using binary search.

        Afterwards, we can cumulate all the values, it will give the same sum array but in with some log factors, instead of .

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

          Actually, it can be shown that your solution (and my solution) runs in time (A is the maximum of {ai}i). That is, the number of distinct values is instead of .

          To see that, for a number x, we can count the number of values that are less than or equal to x and greater than x separately. The first part is obviously O(x) size. And the second part is size because for each input ai, in order to , should be satisfied.

          Then we can set to minimize the quantity.

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

        Yeah, I think the complexity of the code should be .

        There is some way to optimize this to , though; you don't need to recalculate the whole stuff, before performing unique, every range corresponds to a single changing, so the sum can be updated in O(1).

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

I mistook the starting time and couldn't participate, but D and E are very interesting problems! Thank you for the writer!

Here is my solution for E.(It may contain mistakes, since I haven't tested it yet.)

-If there are circle, assign 1 for all node which is contained in circle.

-If there is a vertex v s.t. deg(v)>=4, assign 2 for the center and 1 for the neighbor.

-If there is a connected component which contains 2 vertices u,v s.t. deg(u),deg(v)>=3, assign 2 on the u-v path and 1 for the 4 neighbor of u and v.

-If there are only paths, the answer is no.

-Then, there is only one vertex v s.t. deg(v)=3 for each component. Let's denote the tree as a tuple of integer, s.t. each integer is the length of path which go out from v.

-If it is (2,2,2), (1,3,3) or (1,2,5) or more, we can construct the tree and otherwise not, since we can prove that in the optimal solution, the value on each path will be arithmetic progression.

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

    I think your solution is correct.

    The connected graphs for which the problem doesn't hold are known as Coxeter-Dynkin diagrams.

    I didn't have time to finish implementing this though :(

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

      I implemented it. But I forgot there could be several connected components :(

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

      And do you know is this just a coincidence or there is some meaning of that?

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

        Well, if the variables are x1, x2, ... xn, then the condition is equivalent to the matrix being positive definite, which is one definition of the Dynkin diagram. (We take cij to be if there is an edge between i, j, and 0 otherwise.)

        However, DEGwer's solution is essentially the same method that classifies Dynkin diagrams.

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

    Proof of last sentence:

    Let us name the value on the path, from leaf to the v, x_1, x_1+x_2, x_1+x_2+x_3, ...,x_1+...x_n=value(v). Then the sum of score of the edges and vertices on this path is -sum_{i<j}(x_ix_j) = -(value(v)-sum(x_i^2))/2, then the optimal value is -(1-1/n)value(v)/2. It just means (2,2,2), (1,3,3), (1,2,5) or more is YES and otherwise NO.

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

    akvasha and me, as the authors of Div1E problem, are pleased to hear this from you. :)

    Moreover, there is strict criterion whether 3-tuple (a, b, c) is good. It will be stated in the editorial.

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

      Presumably something like: Let f(n-1) = 1/2 * (1-1/n). Then the tuple is good iff f(a)+f(b)+f(c) >= 1?

      Edit 2: Equivalently, in more readable form, 1/(a+1) + 1/(b+1) + 1/(c+1) <= 1

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

    Regarding to last part. I know that for a particular tree (even any graph) we can check if it is ok by checking if corresponding matrix is positive-definite using Sylvester's theorem, and for a case of (1, 1, k) it can be easily proven manually, so that's some way to prove whole correctness. However I am not fine with your "otherwise not, since we can prove that in the optimal solution, the value on each path will be arithmetic progression." argument. The thing is, "optimal solution" is kinda useless notion here, it is either -infty or 0 and in second case you do not know if 0 is achieved with only zero weights. I also noted during contest that if some value is different than half of sum of its neighbours then we can optimize result by changing only that value, but for vast majority of cases it is not possible to achieve a stable set of values. How your argument goes for trees (2,2,1) and (2,2,3)? You can't achieve local optimality in neither of them, but one is fine other one is doesn't.

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

      Ok, I got it, center value has to be something and then rest is determined and we directly check if such assignment is ok, no need to explain xd.

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

How to solve div2 C?

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

Will we be able to view our submissions page after this contest?

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

Когда ожидать оглашение счастливчиков которым дадут сувениры чемпионата?

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

That moment when you are unable to solve Div1 C and see this solution :P

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

why CF-predictor dosen't work ?

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

When will the ratings be updated?

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

Codeforces api is down

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

http://codeforces.com/contest/831/submission/28526420

Why does this code time out? I have seen multiple N2 * logN solutions that passed for this problem.

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

28522257
28522581
28523125
Can someone help me why some submissions for Div2 C TLE on pretest 11 ?
With O(NK) (in the latest submission) I was not expecting it to TLE :/
Please ignore if the solution is correct or wrong I am just concerned with the TLE for the moment

Feeling bad I wasn't able to solve it, RIP ratings :(

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

    did you checked the condition "If Polycarp messes something up and there is no options, print "0" (without quotes)."

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

      The solution is supposed to terminate correct or not, I can't see anything falling into infinite loop in my code, is there?

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

    It's O(n * k * log2k). map and set are not O(1).

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

      By the third submission I switched to unordered_map and unordered_set which should reduce the complexity to O(NK)

      But really an anti-hash test in pretests ?

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

This is high time now.Somebody please help. Earlier in one codeforces contest ,I solved a problem using unordered map ,it gave TLE,then I used map on that question it gave accepted. Now in today's contest I used map in place of unordered map in problem C and it gave TLE, & when I used unoredered map ,it gave accepted. Somebody please tell me should Unordered map worst case be considered O(n) or O(1) in competitive contests and what should be considered while calculating time complexity at interview round of any company.

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

    Div2 C Accepted by unodered map code

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

      Hi @oo7rm.Can you explain your idea ,If you don't mind. Thank You!

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

        let x be the initial score , for the value x to be the valid initial score x + a[i] must match all the b[i]'s . Now x+a[i] can be equal to some b[i] , x+a[i]+a[i+1]..a[j] must be equal to some other let us say b[j],so

        b[i]=x+a[i]+a[i+1]..a[j] 
        
        x = b[i]-a[i]-a[i+1]..-a[j]

        so i am subtracting the values one by one from every b[i] and incrementing their count in a map. At last i iterate through the map and all the values >=n will be my ans. I have used other map to ensure that the all the x found out in the inner loop are counted only once.

        Complexity is O(k*k*log(k))

        With Fast I/O and unodered map you may get accepted. Hope it's clear.

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

    In most programming contests, you can treat them as O(1) with good probability (*usually* setters don't try to break hashes, since it's generally not easy to break a hash without knowing what it is). However, in codeforces, in the solution, you effectively make your hash public, so it is possible (especially if you use the stl hash) that someone will specifically target the hash to give its worst O(n) performance. Hence, on codeforces, it's usually better to use map rather than unordered_map.

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

How is N^2logN getting TLE in div 2 C? Or did I miss something? http://codeforces.com/contest/831/submission/28516440

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

    I think your constant value is high! I solved in (n^2)logn as well, to be precise mine was O(n(n + nlogn)) and coupled with fast input and output,I JUST managed to pass the system test(1500 ms).. So I guess your constant value is high and also,why did you not use cin.tie(0)?I thought it was important for fast input output,correct me if I am wrong please,still learning..

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

Awesome rounds! Thanks! The scoring is a bit screwed but for Div2 but still a good round

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

Before systest: I'm quite worried about my C. There may be some case that I didn't handle. I'm 100% sure that A and B will pass though.

After systest: C passed, A failed...

Btw, when will the winner of the prizes be announced?

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

    You can deduce it yourself, the code's given below. Thing is, the seed is defined as the maximal score for a contestant on the next Div1. There's no Div1 posted on the contest notice-board thingy, so it'll probably take a week. The only people who may get a prize are Div1 with >= 2 tasks solved, and Div2 with >= 5 tasks solved.

    #include "testlib.h"
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        rnd.setSeed(<seed>);
        
        set<int> winners;
        while (winners.size() < 5)
            winners.insert(rnd.next(1, <length>));
        
        for (auto winner: winners)
            cout << winner << " ";
        cout << endl;
        
        return 0;
    }
    
»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Friendly Div2C,my friend.

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

Solution to Div1 B using just multiset 28517177.

Shouldn't it give TLE? Hmmmm.

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

    It should. 99999 cards with 2 and one card with one in the middle is a hack.

    #include <iostream>
    using namespace std;
    int main()
    {	
    	cout << 100000 << endl;
    	for(int i = 1; i <= 49999; i++)
    		cout << 2 << ' ';
    	cout << 1 << ' ';
    	for(int i = 1; i <= 50000; i++)
    		cout << 2 << ' ';
    }
    
»
4 месяца назад, # |
  Проголосовать: нравится +91 Проголосовать: не нравится


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

When will the winners of the prizes be announced and how you'll pick them randomaly ??

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

28521929
28520986
This looks like cheating to me(If I am wrong, sorry). Because I think nobody will use variable names like nnnn and aa, with unnecessary splay tree template.

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

    Sadly, with this kind of solution it's kind of hard to tell. The actual code you submit is about 3 lines long, and involves an exhaustive list. Additionally, he did have an earlier "skipped" submission without the splay tree code and strange variable names (probably because it was the flagged as equal to someone else's code). My personal stand is that there is totally not enough evidence to flag him as a cheater here.

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

      1) What's wrong with the first submission? I don't understand.

      2) I suspect that the code is skipped because he resubmitted instead. Also, the strange naming of nnnn is from the compilation error that he got.

      program.cpp:173:5: error: redefinition of 'int n'
       int n;
      

      So he just add a few n to solve the issue, I would do that too. The thing I don't understand is why he resubmit with a unnecessary splay tree template...

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

How to solve Div2E??I've already seen that it has a solution using fenwick tree..but could anyone elaborate??Thanks in advance

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

    Use set for every card weight and use BIT to store how many cards is left. iterate thru cards sets from lowest to highest weight and for every set go to lower_bound of current index, if it==end it=set.begin() add the answer from BIT from current to new. Update the BIT with -1 at *it and charge curr=new. Check my solution: 28522814

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

I'm so sad :(

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

By the way, it looks like some top-placed users from div.2 are also cheaters. So we are going to remove them and recalculate ratings, it will take some time.

The algorithm of announcing souvenirs' winners is posted, but it will take some time for me to implement (the seed for the current contest it not known yet, but the seed for round #432 should be ok right now).

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

    Why you didn't update all the information about the new standing !!

    My graph and contest page show that I'm the 4th place , but actually I'm the second :\ !!

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

    Thanks, i got +3 :D Still div2 :(

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

Could anyone explain how to solve Div1.C ? thanks

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

Can any one give a DP solution for Div2 D.Please keep it sweet and simple..Thanks.

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

When will the list of winners of championship souvenirs be published ?

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

Can anyone explain how to solve DIV-2 E?

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

    As for me, the easiest way to solve it is Implicit Treap (but I saw solutions with other data structures)

    We can use Implicit Treap as an array in which we can cut some part, join parts and find index of minimum (all of this in O(logn) time)

    So we can do this while Treap is not empty:

    1. Find index of minimum (name it id)

    2. ans = ans + id

    3. First id - 1 elements place to the back

    4. Erase element id

    Answer will be in ans

    Time complexity is O(nlogn) because our Treap will be empty after n iterations (on each iteration we erase only one element)

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

    Let's see what is actually happening — Each time,the array is rotated to the first smallest no and then,this no is removed.

    1) To keep a track of the rotation ,we only need the beginning position.
    2) Keep an array of sets(set < int > val[size]) to store the positions of each number in a sorted manner and erase this position once the no is removed.
    3) Sort the array.In the ith-iteration, look for a[i] in the rotated array.
    4) Let beginning position -> l, position of a[i] is .

    1. r=val[arr[i]].lower_bound(l) or
    2. r=val[arr[i]].lower_bound(1)
    5) No of times that you read a no is
  • r-l+1 or (n-l+1) + r
  • 6) There is a catch here.The above formula doesn't exclude the removed numbers.To do this,keep a fenwick tree to store and query the no of removed postions in a range and do the appropriate correction.
    7) At last,update the beginning position to r.(or r+1) Complexity — O(nlogn)
    Link to my solution : http://codeforces.com/contest/831/submission/28528292
  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    Alternative solution (runs in linear time since bucket sort is possible):

    Consider the problem in the following light: We don't cycle the cards. We simply look from top to bottom and remove each minimum card. Then we sum up the round number in which each card was removed. We may track the round each card was removed by iterating through values of a_i in increasing order. Summing up across all cards, we may get the answer.

    Example: 3, 2, 3, 1, 2

    Firstly, we remove the '1'. Then consider the 2 '2's. The last '2' to be removed will be the one in position 2. A few details later, we get that the numbers are removed in rounds:

    ?, 2, ?, 1, 1

    By considering the '3's, we will fill the array as:

    3, 2, 2, 1, 1 for a total of 9.

    Edit: http://codeforces.com/contest/830/submission/28544566

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

      My solution involving BIT uses same amount of time :D Because we are using BIT for every number O(1) times it is about O(Nlog*N), but i don't know what exactly what logarithmic factor it has. 28545844

      edit: btw, my friend used balanced binary search tree to get its subtrees size's :D.

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

        I wasn't trying to say my solution was better. It just avoids Fenwick and may be conceptually simpler/interesting to some people.

        Besides, it's pretty hard to tell O(N) from O(N lg N) in practice, especially with relatively large input. I believe the time mainly comes from reading input, since that generally has high constant.

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

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

Did anyone solve DIV2 C using Dynamic Programming?
I searched a lot but didn't found any.

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

Mere mortals are still not able to view VK Finals contest.

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

Editorial is waiting for winter to come.
Winter is coming and so is the editorial.

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

Glad to visit your blog, I seem to be forward to more reliable articles and I think we all wish to thank so many good articles, a blog for sharing with us. Call Girls in Delhi

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

рандомные сувениры будут разыграны?

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

And the souvenir winners are determined (seed = 3954, length = 394).

List place Contest Rank Name
65 830 65 halin.george
69 830 69 Neil
153 830 153 BigBag
265 830 266 whczr
320 830 323 Rydberg

Congratulations!

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

    Thanks!

    It's a nice surprise after 3 weeks :)

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

    Thanks!Wow,I'm really excited to become the luckydog and looking forward to the special souvenir!

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

So where's the souvenir?It has been 2 months but I haven't heard of anything about it.Am I ignored? :D