Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

By 300iq, 5 weeks ago, translation, ,

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

• -252

 » 5 weeks ago, # |   0 Sounds amazing!
 » 5 weeks ago, # |   +31 Please write English version of the blog
 » 5 weeks ago, # | ← Rev. 2 →   +32 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
•  » » 5 weeks ago, # ^ |   0 Just to be sure, I won't get ratings change from both of them right ?
•  » » 5 weeks ago, # ^ |   +3 There is an option to cancel registeration. you can use that
•  » » » 5 weeks ago, # ^ |   0 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.
•  » » » » 5 weeks ago, # ^ |   +13 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)
•  » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 If problems are intersecting then will it not be counted in both divisions even if I submit from anyone of them ?
•  » » » » » » 5 weeks ago, # ^ |   +6 I am pretty sure (but can't explain why) it won't be counted as submit in both
 » 5 weeks ago, # |   +3 Finally the announcement!
 » 5 weeks ago, # |   -6 OK..You absolutely deserve thanks for this round ..#300iq
 » 5 weeks ago, # |   +17 Thanks for the contest to gain back lost rating from Morning div2. :p
 » 5 weeks ago, # |   0 can I participate if I have not participated in previous rounds?
•  » » 5 weeks ago, # ^ |   +20 Yeah you can register
 » 5 weeks ago, # |   -15 02:05 am. nice.
 » 5 weeks ago, # |   +3 Have someone noticed the blog was posted 22 hours ago!! :o
 » 5 weeks ago, # |   +5 xiuxian competition
 » 5 weeks ago, # | ← Rev. 2 →   0
 » 5 weeks ago, # |   +10 I am not seeing any contest for div2 in contest page. is it only me? https://codeforces.com/contests/1298,1310,1314,1315,1311
•  » » 5 weeks ago, # ^ |   +1 Use this link: https://codeforces.com/contests/1310,1314,1315
•  » » 5 weeks ago, # ^ |   0 Yes it's only you
 » 5 weeks ago, # |   0 i have registered for the contest but its not showing in registration list..is this contest rated for me??
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # | ← Rev. 10 →   +11 When submitting I keep getting this error ... you have submitted exactly the same code beforeI tried changing browser, cleaning cookies still the same error, I can't ask for clarifications alsoMikeMirzayanov is there a problem with my account ?
•  » » 5 weeks ago, # ^ |   0 Add a comment and the resubmit
•  » » » 5 weeks ago, # ^ |   +3 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
•  » » 5 weeks ago, # ^ |   0 I had that error in a previous contest, never solve it
 » 5 weeks ago, # |   0 For me Div2 was even more unbalanced than the one from this morning. Quickest was C, then A and D, hardest was B, again ;)
•  » » 5 weeks ago, # ^ |   0 How was B hard?
•  » » » 5 weeks ago, # ^ |   0 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.
•  » » » » 5 weeks ago, # ^ |   0 Ok, in terms of implementation.
•  » » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   +13 How to solve Div 1 D?
•  » » 5 weeks ago, # ^ |   +44 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.
•  » » » 5 weeks ago, # ^ |   0 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)?
•  » » » » 5 weeks ago, # ^ |   +16 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).
•  » » » » 5 weeks ago, # ^ |   0 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.
•  » » » » » 5 weeks ago, # ^ |   0 Can you suggest some problems for practice that use a similar randomized approach?
•  » » 5 weeks ago, # ^ |   +139 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.
•  » » 5 weeks ago, # ^ |   +29 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.
 » 5 weeks ago, # | ← Rev. 2 →   +16 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.
•  » » 5 weeks ago, # ^ |   +3 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
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +6 IMO Div1B is easier than Div1D (to solve, not to understand :Dd), but I do agree that Div1D is a very standard problem.
•  » » » 5 weeks ago, # ^ |   0 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.
•  » » » » 5 weeks ago, # ^ |   +10 What is the simple solution to B?
•  » » » » » 5 weeks ago, # ^ |   +19 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.
 » 5 weeks ago, # |   +3 How to solve Div2 D?
•  » » 5 weeks ago, # ^ |   0 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.
•  » » 5 weeks ago, # ^ |   +1 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.com/contest/1315/submission/71724533
•  » » » 4 weeks ago, # ^ |   0 I did exactly what you described and still TLE on test 15. TLE code
•  » » 5 weeks ago, # ^ |   +6 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
•  » » » 5 weeks ago, # ^ |   +3 Thank you, I solve the Div.2 D finally according your explanation. It stuck me for one day!
 » 5 weeks ago, # |   0 How to do Div2 D?
 » 5 weeks ago, # |   0 Thanks for the contest <3 I have learnt many things
 » 5 weeks ago, # |   -6 How to solve Div 1 B....is there any greedy solution exists like to take any team in upper side or lower side ??
 » 5 weeks ago, # |   +295 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?
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   +49 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)$.
•  » » » 5 weeks ago, # ^ |   0 This TLEd for me — choosing the vertices for the bipartite graph takes $n\choose k/2$ iterations, right?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +10 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).
•  » » » 5 weeks ago, # ^ |   0 Do you assume that everybody knows, what fixed-parameter tractable is?
•  » » » » 5 weeks ago, # ^ |   +24 Nah, just kidding :)
•  » » » 5 weeks ago, # ^ |   -16 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.
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   +18 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.
•  » » 5 weeks ago, # ^ |   +166 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.
 » 5 weeks ago, # |   +536 Authors: please refer to the picture for better understanding Picture:
•  » » 5 weeks ago, # ^ |   0 It would be much better if they grouped each level of upper brackets and lower brackets.
 » 5 weeks ago, # |   0 How to solve Div2 D ?
•  » » 5 weeks ago, # ^ |   0 Generate optimal final value set and start matching from highest time to lowest one to this set using lower bound function.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 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.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 Can you guys have me on DMy algo like this -- sort (number first = high -> low)(time second = high -> low) ---- for i = 1 -> n — 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#include #include #include #include #include using namespace std; #define fi first #define se second typedef pair pi; typedef vector vi; typedef vector vpi; bool cmp(pi a, pi b) { if (a.fi != b.fi) return a.fi > b.fi; else return a.se > b.se; } void out(vpi a) { cout << " "; for (int i = 0; i < a.size(); ++i) { cout << a[i].fi << ' ' << a[i].se; if ((i + 1) % 4 == 0) cout << endl; cout << " "; } cout << endl << endl; }  Main()int main() { int n; cin >> n; vpi a(n); for (int i = 0; i < n; ++i) cin >> a[i].fi; for (int i = 0; i < n; ++i) cin >> a[i].se; std::sort(a.begin(), a.end(), cmp); int res = 0; map free; map sft; free[a[0].fi + 1] = n; sft[a[0].fi + 1] = a[0].se; // int v = free.begin() -> fi; // int f = free.begin() -> se; // int s = sft[v]; // int t = a[0].se * (v - a[0].fi); // cout << "[" << 1 << "]: " << v << ' ' << f << ' ' << s << ' ' << t << endl; // cout << "New " << a[0].fi << " = " << n << " | res = " << res << endl; // out(a); int prev = a[0].fi; vpi b = a; for (int i = 1; i < n; ++i) { /// Free position - Free space - Shift Price - Move Price int v = free.begin() -> fi; int f = free.begin() -> se; int s = sft[v]; int t = a[i].se * (v - a[i].fi); // cout << "[" << i + 1 << "]: " << v << ' ' << f << ' ' << s << ' ' << t << endl; if (a[i].fi == a[i - 1].fi) { /// Using shift all element to closest free position if (s < t) { // cout << a[i].fi << " Shift" << " -> "; res += s; a[i].fi = v; // cout << a[i].fi << " | res = " << res << endl; } /// Move element to closest free position else { // cout << a[i].fi << " Move" << " -> "; res += t; a[i].fi = v; // cout << a[i].fi << " | res = " << res << endl; } /// Update new free position if (--free[v] <= 0) { free.erase(v); sft.erase(v); } /// Update free range / shfit price else { free[v + 1] = free[v]; sft[v + 1] = sft[v] + a[i].se; free.erase(v); sft.erase(v); } } else { /// Add free range new position / new shift if (a[i].fi + 1 != b[i - 1].fi) { int newp = a[i - 1].fi + 1; // cout << "New " << a[i].fi << " = " << a[i - 1].fi - a[i].fi << " | res = " << res << endl; free[newp] = a[i - 1].fi - a[i].fi; sft[newp] = a[i].se + sft[v]; free.erase(a[i].fi); sft.erase(a[i].fi); } /// Update shift price else { // cout << "Update " << a[i].fi << " | res = " << res << endl; sft[v] += a[i].se; } } // vpi b = a; //sort(b.begin(), b.end(), cmp); //out(b); } cout << res << endl; return 0; } 
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 [Deleted]
 » 5 weeks ago, # |   -7 Hit like if you think Div2 B has weak Pretests !
•  » » 5 weeks ago, # ^ |   -6 Anyway B was pathetic, such a confusing statement !
•  » » 5 weeks ago, # ^ |   0 omg the total value can go to long long and I failed the tests :(
•  » » » 5 weeks ago, # ^ |   0 Try to put long long int instead of int in almost all integer numbers. That has saved me a lot of times.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +4 #define int long long // peace
 » 5 weeks ago, # | ← Rev. 2 →   +5 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!
•  » » 5 weeks ago, # ^ |   0 And weak pretests :)
 » 5 weeks ago, # |   0 where did i went wrong in div2 d? https://codeforces.com/contest/1315/my
 » 5 weeks ago, # | ← Rev. 2 →   +39 The feeling when you finish debugging your code 3 minutes after the contest :( CThe answer is some substring of the string. Let's binary search it.To do this, first order the substrings, which can be done recursively in $\mathcal{O}(n^2 c)$.To check if there are at least $k$ ordered strings lexicographically at least some string $tar$, first find for any position $i$ in the string the first position $r[i]$ in the string such that the string $str[i, r[i])$ is lexicographically at least $tar$. Then count the number of ways to partition the array such that every partition is lexicographically at least $tar$ by the recurrence\begin{equation*} DP[i][k] = \sum_{j = r[i]}^{n} DP[j][k-1] \end{equation*}which can be computed in $\mathcal{O}(n^{2})$. Since we only make additions, we can at every point take maximum with the target value $k$ to ensure no overflows happen.Total complexity: $\mathcal{O}(n^{2} (c + \log n))$.71731373
 » 5 weeks ago, # |   0 Can anyone help me in solving Div2-D ? I was getting TLE in testcase 15.My solution — [submission:71720686]https://codeforces.com/contest/1315/submission/71720686Thanks, in advance.
•  » » 5 weeks ago, # ^ |   0 I failed once at 15, too. For me it was int overflow on sum of costs. Fixed by defining it long long.
•  » » » 5 weeks ago, # ^ |   0 but mine was a TLE.
 » 5 weeks ago, # | ← Rev. 2 →   0 I came out with an O(nlogn) solution for div2Dsort by pair (a[i], -t[i])each round add 1 to the min values if there are multiple of themthere 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 answerwhere l r can be determined easily(hard to code, though)then set the max in max(l,r) query to 0but 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!
•  » » 5 weeks ago, # ^ |   +6 For templates/pre-coded algorithms, see the Implementations section.Personally, I recommend KACTL.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 A great listcan't thank you more for sharing :)
 » 5 weeks ago, # |   +6 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.
 » 5 weeks ago, # |   -21 Nice questions, nice contests
 » 5 weeks ago, # |   0 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?
•  » » 5 weeks ago, # ^ |   +8 Check editorial to Radewoosh&mnbvmar contest. If you want to keep multiplying by the same number, you can do a preprocesing on this number.
•  » » » 5 weeks ago, # ^ |   0 Do you have it published anywhere?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +20
 » 5 weeks ago, # |   -27 Awesome contest 300iq!
 » 5 weeks ago, # | ← Rev. 2 →   +7 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?
•  » » 5 weeks ago, # ^ |   +10 Contest duration was 2:30, so drain is adjusted to this duration
 » 5 weeks ago, # |   +12 When will the ratings change?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 i also want to ask and can't wait to become expert
 » 5 weeks ago, # |   +5 I literally devoted 1 hr in B,just later to have it fail on the system test. :(
 » 5 weeks ago, # | ← Rev. 2 →   0 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?
•  » » 5 weeks ago, # ^ |   +3 Yeah it does. In past contests it always took some time, at least a few hours.
•  » » » 5 weeks ago, # ^ |   0 cheers, good to know
 » 5 weeks ago, # | ← Rev. 2 →   +308 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
 » 5 weeks ago, # | ← Rev. 2 →   -8 Would be great if somebody could provide a testcase that helps to identify testcase 4 of Div2 D Thanks!
 » 5 weeks ago, # |   +84 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)).
•  » » 5 weeks ago, # ^ |   +48 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.
•  » » » 5 weeks ago, # ^ |   +20 What should we use instead?
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +6 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 #include 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.
•  » » » » » 5 weeks ago, # ^ |   +18 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.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 Doesn't look safe for me, but ofc I don't guarantee that get_time() is.
•  » » » » » 5 weeks ago, # ^ |   0 Difference between 6.9 and 7.1 is not that significant :)
•  » » » » 5 weeks ago, # ^ |   +8 I guess high_precision_clock<> or whatshisface, I don't remember how all these chrono clocks are called.
•  » » » » 5 weeks ago, # ^ |   +61 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."
•  » » » » » 5 weeks ago, # ^ |   +17 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.
•  » » » » » » 4 weeks ago, # ^ |   0 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 Differenceconst auto start = std::chrono::high_resolution_clock::now(); auto end = std::chrono::high_resolution_clock::now(); std::chrono::duration diff = end-start; return diff.count(); 
 » 5 weeks ago, # |   +156 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???
 » 5 weeks ago, # |   +74 When will the editiorial be published?
 » 5 weeks ago, # |   0 Very weak pretests on B. Counter overflow passed pretests and failed on test 56
 » 5 weeks ago, # |   +84 But still, thank you very much for the round.
•  » » 5 weeks ago, # ^ |   -11 I thought that B was pretty straight forward?
•  » » » 5 weeks ago, # ^ |   +4 He is talking about div1 B.
•  » » » » 5 weeks ago, # ^ |   +18 Ah ok my bad
 » 5 weeks ago, # | ← Rev. 3 →   -8 Hacking div1A solutions with test200000 1 1 1 ... 1 1000000000 ... 1000000000
 » 5 weeks ago, # |   0 How to calculate the probability in 1D if randomized algorithm is used?
•  » » 5 weeks ago, # ^ |   +30 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.
•  » » » 5 weeks ago, # ^ |   +47 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.
 » 5 weeks ago, # |   +168 Maybe it's better to put the problem like "You are given a field, implement Pohlig-hellman algorithm on it" to an educational round.
•  » » 5 weeks ago, # ^ |   +8 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.
 » 5 weeks ago, # |   -46 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 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,greater >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-11){ 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); } } 
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ |   0 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.
•  » » 5 weeks ago, # ^ |   0 There are so many downvotes in my comments.Maybe because my code occupied so much space.Sorry for that.
 » 5 weeks ago, # |   0 for Div2D, if the problem condition changes: we can delete one publication for one category using the same cost as addingHow to solve this problem?
•  » » 5 weeks ago, # ^ |   0 It looks like Slope Trick.
 » 5 weeks ago, # |   0 Div2C in O(nlogn) https://codeforces.com/contest/1315/submission/71743843
 » 5 weeks ago, # |   +14 Finally negative!
 » 5 weeks ago, # |   +37 Why so many downvotes?
 » 5 weeks ago, # |   +4 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.com/contest/1315/submission/71753055Original Submissionhttps://codeforces.com/contest/1315/submission/71721239
 » 5 weeks ago, # |   -9 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.
 » 5 weeks ago, # |   +53 When the editorials will be available?
 » 5 weeks ago, # |   +23 ying ying ying I wonder when the tutorial will be available? I struggled with div.2E and gave it up finally.
 » 5 weeks ago, # |   -12 I don't think so the contest was unbalanced or there were grammatical errors. The contest was although great. Still Waiting for the tutorial.
 » 5 weeks ago, # |   +23 How to solve E div 1?
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   +18 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.
 » 5 weeks ago, # |   +80 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!
 » 4 weeks ago, # | ← Rev. 2 →   0 Can someone explain the solution of problem D ?
 » 4 weeks ago, # |   +5 https://codeforces.com/blog/entry/74214This is the editorial of this contest.
 » 4 weeks ago, # |   0 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!