VK Cup 2019-2020 — Отборочный раунд Engine и Codeforces Round #623 (Div.1 & 2)
By 300iq, 5 years ago, translation, In English

The elimination round of Engine VK Cup 2019-2020 will take place at Feb/23/2020 19:05 (Moscow time). This contest is intended for people who qualified earlier.

As usual, there will be two parallel rounds, one for each division, for everybody who can't take part in official round.

Thanks lperovskaya, MikeMirzayanov, PavelKunyavskiy, izban, Kurpilyansky, YakutovDmitriy, 300iq for preparing the contest.

All three rounds will last 2 hours 30 minutes, and they will be rated. They will have six tasks, and you will be able to see the score distribution when the round starts.

  • Vote: I like it
  • -246
  • Vote: I do not like it

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

Sounds amazing!

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

Please write English version of the blog

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

I had registered for div1 when i was in div1 and now after I became a div 2 participant, I registered for div2 as well. Now from which one should I participate ? Because I am registered for both div1 and div2 rounds. MikeMirzayanov

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

    Just to be sure, I won't get ratings change from both of them right ?

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

    There is an option to cancel registeration. you can use that

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

      I just realized that after few mins of writing comments, thanks. But avoided deleting comment to know what will happen if I don't cancel it.

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

        if you don't submit you don't get rating changed. And if you submit to both, you should be banned (but probably you won't be)

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

          If problems are intersecting then will it not be counted in both divisions even if I submit from anyone of them ?

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

            I am pretty sure (but can't explain why) it won't be counted as submit in both

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

Finally the announcement!

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

Thanks for the contest to gain back lost rating from Morning div2. :p

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

can I participate if I have not participated in previous rounds?

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

02:05 am. nice.

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

Have someone noticed the blog was posted 22 hours ago!! :o

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

xiuxian competition

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

I am not seeing any contest for div2 in contest page. is it only me? https://codeforces.net/contests/1298,1310,1314,1315,1311

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

i have registered for the contest but its not showing in registration list..is this contest rated for me??

→ Reply
»
5 years ago, # |
← Rev. 10   Vote: I like it +11 Vote: I do not like it

When submitting I keep getting this error ... you have submitted exactly the same code before

I tried changing browser, cleaning cookies still the same error, I can't ask for clarifications also

MikeMirzayanov is there a problem with my account ?

https://imgur.com/a/zb7tkma

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

    Add a comment and the resubmit

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

      I did just that, same error, I submitted with a file same error.

      I also tried submitting through m2.codeforces.com apparently the system thinks i'm in another contest

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

    I had that error in a previous contest, never solve it

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

For me Div2 was even more unbalanced than the one from this morning. Quickest was C, then A and D, hardest was B, again ;)

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

    How was B hard?

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

      I had to fiddle with indexes for like an hour to get it right. Since A was more than 20 Minutes I did not submit at all.

      Then, later, C+D turned out to be simpler, I submitted all four of them after two hours.

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

      Can agree more. Too hard for me. Time taken for solving A,B,C,D for me are 4, 53, 8, 32. Seems like B was trickiest at least for me.

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

How to solve Div 1 D?

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

    Pick 4 vertices + the vertex 1 as white, color the rest black. We can now calculate, for two white vertices their distance "through a black vertex". Now we can solve the problem with cycle length $$$k / 2$$$ and without the bipartite condition on this small 5-vertex graph.

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

      Isn't the complexity of this algorithm n^5 * c (n^4 to choose 4 vertices, n to calculate distances through black vertices, c to solve a smaller graph problem)?

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

        I precalculated for every pair of vertices (a, b) several "best" vertices v, such that path a->v->b is less or equal than a->u->b for any other vertices u. Since we can't use path a->v->b only if we chose v, and we can't choose more than 4 vertices, we can find the minimal length of the current cycle with O(4 * 4) instead O(n).

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

        Something like that. I had to optimize a bit. First we pick only 3 white vertices + the vertex 1, calculate two best distances between all pairs of the 4 vertices, now iterate over remaining vertices to pick the 5th.

        Not sure how much it helped. But my program should always take the same amount of time (I add virtual vertices until we have 80), so "Pretests passed" should mean that it gets accepted.

        Randomized approach is much nicer indeed.

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

          Can you suggest some problems for practice that use a similar randomized approach?

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

    You'll visit at most $$$10$$$ vertices (including $$$1$$$) on your way. No odd cycles -> you can assign each vertex a color, black or white, such that no two vertices connected on your path via an edge have the same color. For optimal path, there exists some coloring, so we can try to guess it. Assign the colors randomly and run a simple dp. Repeat as many times as you have time.

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

    To guarantee no odd cycles, every vertex must be visited with the same parity of number of moves every time. Notice that we don't need more than 5 vertices of every color. Starting vertex is always even, iterate over the remaining 4.

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

Why is Div1D so much easier compared to Div1B and C?

Edit: I suspect that the writer of Div1D intended that it be solved using a randomized algorithm, but incorrectly chose the constraints, leading to it being solvable using a much simpler method.

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

    I don't know is it true, but it's reason can be they don't want to put no more easy tasks to div.2

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

    IMO Div1B is easier than Div1D (to solve, not to understand :Dd), but I do agree that Div1D is a very standard problem.

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

      I didn't know div1D at all and it took me much less time to figure it out than div1B. B has a simple solution, but there are so many ways to try something wrong.

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

        What is the simple solution to B?

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

          DP: "when the sub-tournament for people $$$[a \cdot 2^b, (a+1) \cdot 2^b)$$$ is finished, there's one person remaining in the upper bracket and one in the lower; if we choose which of them are among the initial $$$k$$$, what's the max. number of games?". Basically, the tournament structure is sufficiently tree-like, but it doesn't seem so at first.

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

How to solve Div2 D?

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

    At first let's find out what will be the final size of all means find a set of size such that any pair are not eqaul.You can find it by a simple dp.iterate by sorting given array. Then next size should be max(cnt+1,a[i]) where cnt is size of the last index.

    Then greedily give size to all. To minimize the cost the element of maximal cost should be increase minimum number of times.

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

    You can put list of categories by size into a map.

    Then for every size remove the most expensive category of that size, and buy for all others one more instance, so they "move up" one size.

    To do this eficiently maintain a set of categories, sorted by cost of categories. Then per "move up" add the costs for the whole set. see https://codeforces.net/contest/1315/submission/71724533

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

    Group categories with same number of publications. Starting from the group with smallest publications, ignore the one with maximum time and increment all the others by 1. If the next category has same count, add it to the group and repeat the same thing.

    My submission 71721239

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

      Thank you, I solve the Div.2 D finally according your explanation. It stuck me for one day!

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

How to do Div2 D?

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

Thanks for the contest <3 I have learnt many things

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

How to solve Div 1 B....is there any greedy solution exists like to take any team in upper side or lower side ??

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

The statements were pretty bad. There are some really basic mistakes like "looses" (I'm sure you've seen this word a million times so write it correctly), the statement of B overloads $$$k$$$ and doesn't mention how the teams are paired ("see the images below" isn't an explanation) and they're overall just clumsy, kinda tough to read.

Was D some improved bruteforce?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +49 Vote: I do not like it

    D is a traditional FPT problem. Partition the vertices into two disjoint sets randomly, then find a best path in bipartite graph. Repeat. The probability of success is exponentially small of $$$k$$$ (I guess $$$2^{-k}$$$), so overall complexity is $$$2^k poly(n)$$$.

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

      This TLEd for me — choosing the vertices for the bipartite graph takes $$$n\choose k/2$$$ iterations, right?

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

        You get the wrong idea. I am not bruteforcing the partition. I'm selecting a partition randomly (there are $$$2^n$$$ partitions in total), and repeat the whole stuff $$$2^{k} * const$$$ times (well, actually as many times as it fits in TL).

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

      Do you assume that everybody knows, what fixed-parameter tractable is?

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

      In the end, I figured out the deterministic solution by MrDindows below by myself easily. Too bad I didn't check D before getting brutalised by B (instead of 5 minutes before the end), I would've just swapped these two problems if it was up to me.

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +18 Vote: I do not like it

    D. Go over all possible vertices on even positions (2, 4, 6 and 8) in the path. For the odd positions choose greedily from unused vertices. $$$O(N^{K/2 - 1}K^2)$$$, or just $$$O(N^4)$$$ assuming k is constant.

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

    Agree. Grammar and spelling was bad. Also trying to explain B with a weird drawing was a terrible idea. Yet, I think the biggest problem with the statements was ambiguity. Here are some of the most embarrassing examples:

    -Div1A:

    The targeted algorithm can find a single interesting publication of i-th category within t_i seconds. What is the minimum total time necessary to add publications to the result of batch algorithm execution, so all categories have a different number of publications? You can't remove publications recommended by the batch algorithm

    Why not:

    You can add as many publications as you want to the batch algorithm, but you're not allowed to remove any of the existing ones. Adding one publication of category i takes t_i seconds. Let the final amount of publications of category i be f_i. You want to make f pairwise distinct in the minimum possible time.

    -Div1B

    Teams are split into games by team numbers

    Why not:

    On each elimination round, the teams involved are matched up as follows: The team with smallest index plays the team with the second smallest index. The team with the third smallest index plays the team with the fourth smallest index, and so on.

    It's a longer statement but it's good to clear out exactly how the matching happens, even if you have a drawing.

    • Div1D

      Formally, if you can select visited by Masha city v, take odd number of routes used by Masha in her journey and return to the city v, such journey is considered unsuccessful.

    Why not something like

    Formally, if Masha visits city v twice, the amount of routes travelled between the first and second visit has to be even.

    You could've also not include that sentence, just leaving

    Masha doesn't want her journey to have odd cycles.

    Which is actually less confusing.

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

Authors: please refer to the picture for better understanding
Picture:

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

    It would be much better if they grouped each level of upper brackets and lower brackets.

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

How to solve Div2 D ?

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

    Generate optimal final value set and start matching from highest time to lowest one to this set using lower bound function.

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

    Let's say $$$p_i$$$ is the value which $$$a_i$$$ gets, this has cost $$$t_ip_i - t_iai$$$. We have to minimize $$$\sum_{i=1}^nt_ip_i - \sum_{i=1}^nt_ia_i$$$. Last part is constant, so me must minimize first part. We can use a greedy algorithm to do that.

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

    Can you guys have me on D

    My algo like this

    -- sort (number first = high -> low)(time second = high -> low)
---- for i = 1 -> n &mdash; 1
------ if (2 concussive numbers is equal)
-------- move price = price to move to closest free position
-------- shift price = price to shift all element up and move number to next position
-------- min {move price, shift price)
-------- update free position
-------- update shift price
------ else if (2 concussive have different = 1)
-------- make new free position
------ else 
-------- update shift price
    Detail
    Main()
    → Reply
»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Hit like if you think Div2 B has weak Pretests !

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

    omg the total value can go to long long and I failed the tests :(

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

      Try to put long long int instead of int in almost all integer numbers. That has saved me a lot of times.

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

Day of terrible B's... B's statement is like...

well, is it ok if bus stops near tram station? what is crossroad and why the word "crossroad" was used? My imagination was totally broken here.

And more than that B was much more complicated than C again!

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

where did i went wrong in div2 d? https://codeforces.net/contest/1315/my

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

The feeling when you finish debugging your code 3 minutes after the contest :(

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

Can anyone help me in solving Div2-D ? I was getting TLE in testcase 15.

My solution — [submission:71720686]https://codeforces.net/contest/1315/submission/71720686

Thanks, in advance.

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

I came out with an O(nlogn) solution for div2D

sort by pair (a[i], -t[i])

each round add 1 to the min values if there are multiple of them

there are O(n) round (correct me if this is wrong)

each round take O(logn) to add sum(l,r)-max(l,r) to the answer

where l r can be determined easily(hard to code, though)

then set the max in max(l,r) query to 0

but its too complicated to implement for me in 2.a.m. :(

Also, wondering if there are good segment tree templates or other templates.

Hope somebody can provide, thx!

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

I had a really hard time trying to understand what Div2B statement was trying to say and wasted a lot of time on that. What a shame.

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

So, what's the most efficient way to multiply two nimbers? I kind of know the solution in 7kk multiplications, but calculating nimber product in $$$64^2$$$ takes too long. Any suggestions?

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

Awesome contest 300iq!

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

How are the points scored for a problem decided? I read long time ago in one of the blogs that points are reduced per minute (2, 4, 6, 8, 10 for A, B, C, D, E). If so, my solution C which was submitted at 10:09, should have gotten 1500-60=1440, ( or 1434 if you consider that 11th minute). However, it got 1452. Same story for other problems as well. I am guessing this is so because the contest was of 2 hours 30 minutes, but what is the formula then?

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

    Contest duration was 2:30, so drain is adjusted to this duration

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

When will the ratings change?

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

I literally devoted 1 hr in B,just later to have it fail on the system test. :(

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

It is the first time in a long while that I am participating again, a bit confused though if it was a rated contest. I cannot see it in the list of participated contests on my profile, Does it take a while to appear?

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

    Yeah it does. In past contests it always took some time, at least a few hours.

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

I have successfully hacked some solutions in D (tourist, for example) with this test:

3 10
0 8 3
3 0 1
9 2 0

Will you do something with this?

UPD: about 10 solutions from top40 have failed on this test

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

Would be great if somebody could provide a testcase that helps to identify testcase 4 of Div2 D
Thanks!

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

I don't know why this submission 71710714 by Um_nik worked only 15ms on test 37. So currently, it is under investigation. I'll try to understand why it happened and I'll rejudge it if needed. In this case, ratings and places will be recalculated (only in VK Cup 2019-2020 - Отборочный раунд (Engine)).

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

    Well, I guess that many contestants know that $$$clock()$$$ is very dangerous and kind of unstable on CodeForces, so it might be a bigger investigation.

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

      What should we use instead?

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

        Don't know, I'm not an expert, it just an observation :P I usually check $$$clock()$$$ not so ofter, for example after every $$$500$$$ iterations, but I don't know if it is a good idea.

        On marathon matches I use this:

        #include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

double rem_time;

void init_time()
{
    timeval tv;
    gettimeofday(&tv, 0);
    rem_time=tv.tv_sec+tv.tv_usec*1e-6;
}

inline double get_time()
{
    timeval tv;
    gettimeofday(&tv, 0);
    return tv.tv_sec+tv.tv_usec*1e-6 - rem_time;
}

int main()
{
    init_time();
    cout << get_time() << endl;
    return 0;
}

        Maybe on CF it also works well.

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

          Your code measures wall time, not CPU time. I'm not sure (I'm not sure about anything after that WA 37 tbh), but I think that it is not good for algorithmic competitions, because testing system can pause execution or something.

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

        clock()

        my get_time()

        Doesn't look safe for me, but ofc I don't guarantee that get_time() is.

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

          Difference between 6.9 and 7.1 is not that significant :)

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

        I guess high_precision_clock<> or whatshisface, I don't remember how all these chrono clocks are called.

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

        I think the issue could be that you assumed clock() starts from 0.

        According to https://en.cppreference.com/w/cpp/chrono/c/clock, "Only the difference between two values returned by different calls to std::clock is meaningful, as the beginning of the std::clock era does not have to coincide with the start of the program."

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

          Yes, but other sources say that it is "implementation-defined" which means that it shouldn’t be different between runs on the same compiler?

          Also, can you please provide a way to get the same behaviour with probability higher than that of "testing machine went crazy"?

          I understand that the quote from reference is enough to not rejudge my solution. But I still think that there may be a problem.

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

            Even difference in std::clock() is not safe. Case 72364466 ran for only 1s. Same submitted again runs for 2s and gets an AC. @dorijanlendvaj stress tested it a lot of times for finding counter test case during testing of Today's rounds and found clock() works incorrectly about 4/100 times.
            Right now only possible soln I see is —

            High Resolution Clock Difference
            → Reply
»
5 years ago, # |
  Vote: I like it +156 Vote: I do not like it

About div1B: "Second input line has k distinct integers" Well apparently there was no second input line if k = 0, got RTE by doing input() in Python 71711503. Why would you even have case k = 0 in the first place???

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

When will the editiorial be published?

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

Very weak pretests on B. Counter overflow passed pretests and failed on test 56

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

But still, thank you very much for the round.

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

Hacking div1A solutions with test

200000 1 1 1 ... 1 1000000000 ... 1000000000

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

How to calculate the probability in 1D if randomized algorithm is used?

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

    Assume there is only one optimal cycle. We have probability $$$p = \frac{1}{2^{k-1}}$$$ of assign colors in the correct way because the color of vertice 1 is fixed.

    To compute the probability of finding the solution in the first $$$T$$$ iterations, we actually compute the complement of not find the solution in the first $$$T$$$ iterations.

    So the randomized solution works with probability $$$1 - (1 - p)^T$$$, for $$$k = 10$$$ and $$$T = 5000$$$ that's 0.999943155.

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

      One more thing... there are 129 test cases, so you'd better calculate the $$$(1 - (1 - p) ^ T) ^ N$$$ where $$$N$$$ is the number of test cases. So the answer for $$$T = 5000, k = 10, N = 129$$$ should be $$$0.9927$$$.

      In fact I implemented with $$$T = 3000$$$, where the probability is about $$$0.69$$$. My hands didn't stop shaking after realising the fact at the end of the contest until the solution was accepted with fairly good luck.

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

Maybe it's better to put the problem like "You are given a field, implement Pohlig-hellman algorithm on it" to an educational round.

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

    I've never heard about this algorithm before, and coming up with it from the basics (the fact that all finite commutative groups are products of Z/nZ) was quite enjoyable, even though I needed about 15 more minutes after the end of the contest to finish my code.

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

Who can help me calculate the time complexity of my program?I just can't figure out. It's the code of problem D.

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
typedef long long ll;
struct node{
    int a,b;
    friend bool operator <(node a,node b){
        if(a.a==b.a)return a.b<b.b;
        return a.a<b.a;
    }
}a[N];
ll ans;
int b[N];
int m,n;
priority_queue<int,vector<int>,greater<int> >q[N];
void discrete(){
    sort(a+1,a+n+1);m=0;
    for(int i=1;i<=n;i++){
        if(i==1||a[i].a!=a[i-1].a){
            q[++m].push(a[i].b);
            b[m]=a[i].a;
        }
        else{
            q[m].push(a[i].b);
        }
    }
}

int main(){
    while(~scanf("%d",&n)){
        ans=0;
        for(int i=1;i<=n;i++){
            while(q[i].size())q[i].pop();
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i].a);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i].b);
        }
        discrete();
        for(int i=1;i<=m-1;i++){
            if(q[i].size()>1){
                int s1=b[i],s2=b[i+1];
                int h=q[i].size()-1;
                int ct1,ct2;
                if(s2-s1-1<h){
                    ct1=h-(s2-s1-1);
                    ct2=s2-s1-1;
                }
                else{
                    ct1=0;
                    ct2=h;
                }

                while(q[i].size()>1){
                    int x=q[i].top();q[i].pop();
                    if(ct1){
                        ans+=(ll)x*(s2-s1);
                        q[i+1].push(x);
                        ct1--;continue;
                    }
                    if(ct2){
                        ans+=(ll)x*ct2;
                        ct2--;
                    }
                }
            }
        }
        int ct=q[m].size()-1;
        while(q[m].size()>1){
            int x=q[m].top();q[m].pop();
            ans+=(ll)ct*x;
            ct--;
        }
        printf("%lld\n",ans);
    }
}
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Instead of using a min-heap, why not using a max-heap, you can easily calculate the delta for answer and forward in each iteration by pop the maximum element.

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

      Thanks a lot.When the round ends,I was trapped in my thoughts and not aware of the right solution.So that's it.Thanks again for answer my question.

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

    There are so many downvotes in my comments.Maybe because my code occupied so much space.Sorry for that.

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

for Div2D, if the problem condition changes: we can delete one publication for one category using the same cost as adding

How to solve this problem?

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

Finally negative!

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

Why so many downvotes?

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

Hi if anyone wants solution of div2 D. I have added comments in my solution. I copied the solution from someone as i was not able to solve it. But i have added comments if anyone else wanna understand.

https://codeforces.net/contest/1315/submission/71753055

Original Submission

https://codeforces.net/contest/1315/submission/71721239

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

This contest didn't deserve downvotes, feels like something is wrong with intent of contestants. Div2 E was hard to understand tough, but my Iq < 80 so I understand.

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

When the editorials will be available?

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

ying ying ying I wonder when the tutorial will be available? I struggled with div.2E and gave it up finally.

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

I don't think so the contest was unbalanced or there were grammatical errors. The contest was although great. Still Waiting for the tutorial.

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

How to solve E div 1?

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

    Suppose we are given a multiset $$$a'_1 \geq a'_2 \geq ...$$$ and wish to know if $$$f^K(a) = a'$$$ for some $$$a$$$ containing no more than $$$N$$$ elements. In general the preimage of any multiset under $$$f$$$ contains multiple options, but the most efficient way to "undo" $$$f$$$ is to select the multiset containing $$$a'_1$$$ 1's, $$$a'_2$$$ 2's, and so on. Define $$$f^{-1}(a)$$$ to be that multiset. We can compute the size of $$$f^{-K}(a')$$$ for any particular $$$a'$$$ through straightforward simulation.

    A key observation is that the number of possibilities for $$$f^K(a)$$$ shrinks very quickly as $$$K$$$ grows. One way to observe it is to notice that if $$$f^2(a)$$$ contains $$$x$$$ elements, the sum of the elements in $$$f(a)$$$ is at least $$$1 + 2 + \dots + x$$$, which means that $$$a$$$ contains at least $$$\frac{x \cdot (x + 1)}{2}$$$ elements. The size and sum of $$$f^K(a)$$$ both shrink exponentially as $$$K$$$ grows.

    In fact, the final answer for the input $$$N = 2020, K = 3$$$ is only $$$451945$$$. So for $$$K \geq 3$$$ we can do an exponential search on $$$a'$$$ for which $$$|f^{-K}(a')| \leq N$$$.

    To handle the $$$K = 1$$$ and $$$K = 2$$$ cases, notice $$$|f^{-1}(a')| = \sum a'$$$ and $$$|f^{-2}(a')| = \sum_{i} ia'_i$$$. In both cases we can count $$$a'$$$ for a given $$$N$$$ with some straightforward DPs.

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

Many years ago I added a purple (or even blue) user SoMuchDrama to the friends just because of his funny nickname — I believe that people often dramatize too much. For a long time this user was the only in my friends list didn't know in the real life. It seems that one day I deleted him from the friends list accidentally, but I always remembered him and told about him to my students when they complain instead of training.

When the VK Cup elimination round finished I have found SoMuchDrama in the final standings — several positions above me. Now he has red color and have advanced to the finals! SoMuchDrama, I'm proud of you!

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

https://codeforces.net/blog/entry/74214

This is the editorial of this contest.

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

I think there are some bad translations in the statements and tutorial. I nearly cant read it fluently, which gives me a bad experience. Problems will be nicer with good translation!

→ Reply