Recent actions

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

Thanks!

It's a nice surprise after 3 weeks :)

Created or updated the text

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!

Created or updated the text

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

I believe that my results are correct, so now they're official.

If anyone has comments about the code, please comment.

can you give some tutorial/link on Implicit Treap

The list places are the same for me. I didn't use scripts, just went through the scoreboards manually, marked off ineligibles and then added 1 to list places for each smaller ineligible place; maybe I added incorrectly for place 131.

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.

I wrote some scripts to make the process of winners determining easier, and they produce results slightly different then Xellos's. Here are my results (not official yet):

List place Contest Rank Name
19 827 19 zeliboba
42 827 42 kevinsogo
114 827 115 triploblastic
125 827 126 lexuanan
138 827 140 alex256

The seed is 5581, the length is 213. The output of the generator is 19 42 114 125 138. The scripts I used are below. Xellos, have you used any scripts? If so, can you see where the difference came from?

python code
c++ code

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

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.

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

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.

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.

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

With seed 5581, 200 people with 3+ problems in div1, 13 people with 5+ problems in div2 (isn't that difference too big?), the winners are places 19, 42, 115, 127, 139 in div1:
zeliboba
kevinsogo
triploblastic
soimae
pitfall

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 ?

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

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

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.

:)

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

I failed bin search because of l=1=)))

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

Nice Solution :)

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 :()

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.

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.

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.

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

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

Finally done man..Thanks all for your support..

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.

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

    If you are interested in clean top-bottom DP implementation,you may check mine.(http://codeforces.com/contest/831/submission/28530870)

    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)

    can you tell me about your dp state

    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.

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

    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

    Yes, you are right. The proof will be in the editorial.

    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

    I implemented the same idea but getting TLE Once can you check it plz http://codeforces.com/contest/831/submission/28539653

    28516949

    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.

    Thank you so much for sparing your time .I understood it well

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

    Can anyone explain how to solve DIV-2 E?

    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.

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

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

    Yes, you are right. I solved it using the same method.

    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 .

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

    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

    Can you please elaborate on it, send_nodes :^)

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

    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.

    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

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

    Could anyone explain how to solve Div1.C ? thanks

    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 .

    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 :\ !!

    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

    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

    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.

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

    I'm so sad :(

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

    Div2 C Accepted by unodered map code

    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.

    I thought you forgot sorting at all like I did lol

    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 << ' ';
    }
    

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

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

    Yep, I failed this problem because of typo.

    lel. you mean sort(b+1, b+1+k)? or is it not Office Keys problem?

    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;
    }
    

    And? Who won? :D

    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.

    One more FYI (of course there would be much more) http://codeforces.com/blog/entry/43880

    Yes

    On KANVK Cup 2017 Finals, 2 months ago
    +15

    Is it rated? :)

    Upd. Oh, that was fast! :)


    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

    Solution to Div1 B using just multiset 28517177.

    Shouldn't it give TLE? Hmmmm.

    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.

    Friendly Div2C,my friend.

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

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

    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?

    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

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

    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 ?