By Errichto, 3 years ago,

Hey, hi, hello.

Codeforces Round #584 - Dasha Code Championship - Elimination Round (rated, open for everyone, Div. 1 + Div. 2) starts on Sep/14/2019 16:05 (Moscow time) and lasts 2h30m. The score drain will be adjusted for longer contest duration. It's a combined rated round with around eight problems. It is open and it is rated for everybody. Yes, it's rated. There are Dasha t-shirts for top 30 competitors (not counting later-to-be onsite finalists).

As an extra, this is an elimination round for those who live in/near SPb/Novosibirsk. More info about the championship is in the other blog. Thanks to Dasha.AI for making such an event for the community!

Problems are prepared by MikeMirzayanov, FieryPhoenix, dragonslayerintraining and Errichto. One of these setters also created Codeforces, thanks for that! And huge thanks to cdkrot for coordinating the round, to Merkurev, isaf27, KAN and me for testing, and finally to mareksom, Radewoosh and Marcin_smu for some small help.

I wish you more fun than bugs. Enjoy the contest!

PS. I recorded the process of preparing one problem with commentary, will publish it on Youtube after the contest. EDIT: https://www.youtube.com/watch?v=IaViSV0YBog

UPDATE, points: A 500, B 500, C 1250, D 1500, E 1000+1500, F 2500, G 1500+2250, H 4000. There are 8 problems and 2 of them are split into two versions. Good luck!

UPDATE, huge congratulations to winners!

I was the author of last two problems: Into Blocks (but thanks for cdkrot for preparing it!) and Walkways, hope you liked them.

UPDATE, editorial is out.

• +583

 » 3 years ago, # |   -15 Finally Codeforces Round #584 is here. Can't wait to participate the contest. It's been a long time since Codeforces hosted the last contest.
 » 3 years ago, # |   -93 Rated?
•  » » 3 years ago, # ^ |   -23 Yes. It is rated. Rated for everyone both div 1 & div 2.
 » 3 years ago, # |   +71 PS. I recorded the process of preparing one problem with commentary, will publish it on Youtube after the contest. This is something I've wanted to see for some time now, thanks for doing it!
•  » » 3 years ago, # ^ |   +23 how come your name is mango lassi?
•  » » » 3 years ago, # ^ |   +74 how come your name is ankitsinha3005 ???
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +52 He's probably asking because lassi is a famous drink from India (which I personally enjoy a lot over caffeine loaded drinks) and he wants to know how Antti got to know about it. :)On the other hand, ankitsinha3005 is a pretty easy name to deconstruct — with good probability, his name is Ankit Sinha and his birthdate is 30th May.
•  » » » » » 3 years ago, # ^ |   +16 I think lassi isn't unknown outside India, just fairly obscure. Even I know what it is because I've seen it on random Asian takeaway menus here. So it's not unreasonable that someone from Finland would discover it.
 » 3 years ago, # |   +24 Wow. It's great. We will get the recorded process of problem. Thanks, Errichto for your big-hearted sharing+teaching mind.
 » 3 years ago, # |   +392 wish everyone high rating!
•  » » 3 years ago, # ^ |   +269 ratist :D
•  » » 3 years ago, # ^ | ← Rev. 3 →   +96 So the guy likes Petr's daughter :p
 » 3 years ago, # |   +68 Huge thanks to ... and me for testing lol
 » 3 years ago, # |   +42 Hope I get up early tomorrow for the contest!BTW, I found “Small help” funny, it made me laugh.
•  » » 3 years ago, # ^ |   +5 wake up now..its about time
 » 3 years ago, # | ← Rev. 3 →   +68 Don't get offended :)
 » 3 years ago, # |   +16 "publish it on Youtube" reminds me of Codeforces Round #543.
 » 3 years ago, # |   0 Limak is back ʕ •ᴥ•ʔ
 » 3 years ago, # |   -8 Good Luck everyone.
 » 3 years ago, # |   -10 Wish everyone high rating GL HF
 » 3 years ago, # |   +12 1410 appearing in sample output O_o. Errichto I love you.
 » 3 years ago, # |   -248 What's wrong with tourist today? He didn't perform well! And even a student from our school, aged $14$, has got a better rank than him!
•  » » 3 years ago, # ^ |   -9 It's not you who got a better rank than tourist, why R U so excited?
 » 3 years ago, # |   -11 How to solve E2?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 E1 was bitmask dp with complexity $O(3^n*m)$, I tried to improve it to $O(2^n*m+3^n*n)$ by only considering top 12 results for every bitmask, but somehow got TLE.
•  » » » 3 years ago, # ^ |   -8 Wow, could you outline the idea? My solution is O(mn + n^n), unfortunately...
•  » » » » 3 years ago, # ^ |   +1 Oops, my solution is $O(4^n*n)$. The idea is: for a prefix of columns and bitmask of rows store the answer.
•  » » » 3 years ago, # ^ |   0 Did you also consider we have $t \leq 40$ as the number of test cases. I had a same idea but I didn't start implementing it. Considering the number of test cases, I assumed such an idea would have no chance to pass the system tests.
•  » » » 3 years ago, # ^ |   0 I passed pretests in E1 with $O(t * (n * m ^ 3 + m * n ^ 2 * 2 ^ n))$code link
•  » » 3 years ago, # ^ |   +29 First realize you'll need at most N columns (with the N largest elements), then do a DP on all columns:f(x,mask) = max sum you can do for rows in mask (it is a bitmask), starting from column X
•  » » » 3 years ago, # ^ |   0 Does it hold if some of the largest N is in the same column?
•  » » » » 3 years ago, # ^ |   0 I meant this: sort columns by their largest number, and take the N biggest.
•  » » » » » 3 years ago, # ^ |   0 Okay, now it makes sense.
•  » » » 3 years ago, # ^ |   +5 Could you prove it? Sorry for my dumb mind...
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +3 Yes, if you get these maximal columns, you're sure that you can rotate them in such a way that you get the maximal number of each column in its own row. Like:2 11 4So, if you took one more row, its maximal value would be less than the maximal values for each of those columns. So, with the above configuration, you can't use it to improve the configuration.
•  » » » » » 3 years ago, # ^ |   0 Got it, thank you.
•  » » 3 years ago, # ^ |   +24 I think I solved it in $O(2^n n^3)$, by taking only the $n$ columns with largest maximum, and during a bitmask dynamic programming, transferring grid by grid.
•  » » » 3 years ago, # ^ |   0 I have a solution in $O(3^n*n)$, what was your optimization to make the base $2$?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Transfer grid by grid instead of column by column.
•  » » » » » 3 years ago, # ^ |   +13 cell by cell*And it's called broken profile, https://cp-algorithms.com/dynamic_programming/profile-dynamics.html
•  » » 3 years ago, # ^ |   +16 Same as E1, just notice that you only need to sort columns by their maxima and take the top min(N, M) (if the sorted order isn't unique, just pick one). Proof: let's assume $M > N$, assign a column to each row maximum in the final solution and look at the smallest of these columns (in the picked order) that's not among the top $N$. If there's just one row maximum in this column, you can replace it by a column from the top $N$, suitably shifted. If there's more than one, you've chosen less than $N$ columns, so you can just add a column from the top $N$ and move one row maximum to it. Both cases result in one more of the top $N$ columns being chosen, so if you repeat this as long as possible, you'll either end up with the top $N$ columns all containing row maxima or no other columns containing row maxima. However, the former also implies there are no other columns containing row maxima, since there are just $N$ of them.
•  » » » 3 years ago, # ^ |   0 Got it, thank you.
 » 3 years ago, # |   +23 Give us more problems next time pls.
 » 3 years ago, # |   +31 How are you sure that your solution to H is numerically stable?
•  » » 3 years ago, # ^ |   -31 While Errichto didn't answer you, try watching his video of preration of problem H.https://www.youtube.com/watch?v=IaViSV0YBog
•  » » 3 years ago, # ^ | ← Rev. 2 →   +6 My solution involves division only at the beginning and at the end, the rest is obviously numerically stable: Codeprivate double solveOne(List segments) { int n = segments.size(); for (int i = 0; i < n; ++i) { TaskH.Segment s = segments.get(i); s.ptr = i; s.curEnergy = 0.0; s.maxEnergy = (s.right - s.left) / s.s; s.minEnergy = -(s.right - s.left) / (s.s + 2); } List segmentsByS = new ArrayList<>(segments); Collections.sort(segmentsByS, new Comparator() { public int compare(TaskH.Segment o1, TaskH.Segment o2) { int z = Double.compare(o2.s, o1.s); if (z == 0) { z = Integer.compare(o2.left, o1.left); } return z; } }); TreeSet available = new TreeSet<>(new Comparator() { public int compare(TaskH.Segment o1, TaskH.Segment o2) { return o1.ptr - o2.ptr; } }); available.addAll(segments); for (TaskH.Segment s : segmentsByS) { if (s.s == 0.0) break; s.alive = false; available.remove(s); NavigableSet after = available.tailSet(s, false); double capacity = s.maxEnergy - s.curEnergy; double spent = 0.0; while (!after.isEmpty()) { TaskH.Segment t = after.first(); if (t.alive) { double t1 = t.curEnergy - t.minEnergy; double t2 = capacity - spent; double transfer = Math.min(t1, t2); spent += transfer; t.curEnergy -= transfer; if (t1 <= t2) { available.remove(t); } else { break; } } } s.curEnergy += spent; } double res = 0.0; for (TaskH.Segment s : segments) { double v = (s.right - s.left - s.curEnergy * s.s) / (s.right - s.left + s.curEnergy); res += (s.right - s.left) / (s.s + v); } return res; }
•  » » » 3 years ago, # ^ |   0 Can you wrap that in a spoiler? :)
•  » » » 3 years ago, # ^ |   -9 Spoilerif (t1 <= t2) { available.remove(t); } else { break; } How is this numerically stable?
•  » » » » 3 years ago, # ^ |   0 It doesn't matter how this comparison is resolved when t1 and t2 are close.
•  » » » » » 3 years ago, # ^ |   0 I can say the same about all the 14 codes I submit, but they do occasionally receive different verdicts, so I'm trying to understand why.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +6 In short, there is no issue with catastrophic cancellation because incorrectly computing some sum as $S + e$ instead of $S$ gives us a new value $V - e$ instead of $V$ and the errors cancel out. And the formal proof of the whole thing should use absolute errors only but that's fine because we never get huge numbers.
•  » » » 3 years ago, # ^ |   0 60573091 this gets WA 19. You can press "Compare" and look at the changes from solution that gets WA 15. Really?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +4 I'm not sure what you're talking about. My solution is different, it doesn't use any epsilon (well, only to check if something is 0 or greater than 0.1).EDIT: I want to compute energy computed/saved for every walkway. I build a segment tree over that. Sort walkways by speed and in this order maximize energy used there without getting below $0$. I use a segment tree to get prefix sum and min prefix sum.
•  » » » » » 3 years ago, # ^ |   -17 Does your solution use sets, comparisons of doubles, or something similar?
•  » » » » » » 3 years ago, # ^ |   +11 No, it doesn't. code#include using namespace std; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge range(c i, c j) { return rge{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " using ll = long long; struct Walkway { int start, end; double speed; void read() { scanf("%d%d%lf", &start, &end, &speed); } int len() const { return end - start; } bool is_zero() const { // any precision better than the one from the input return speed < 1e-11; } double max_saved() const { if(is_zero()) { return 0; // we walk at least 1m/s on 0-speed walkways and thus save no energy } else { return len() / speed; // energy saved while just standing on this walkway } } double max_used() const { return len() / (speed + 2); // energy used on running 2m/s here } }; struct Node { double sum, min_pref; void init(double delta) { sum = min_pref = delta; } void merge(const Node& L, const Node& R) { sum = L.sum + R.sum; min_pref = min(L.min_pref, L.sum + R.min_pref); } }; vector tree; int BASE; // tree base (power of 2) //const double eps = 1e-6; int main() { int n, L; scanf("%d%d", &n, &L); vector walkways; int last_end = 0; for(int i = 0; i < n; ++i) { Walkway nxt; nxt.read(); assert(last_end <= nxt.start); if(last_end < nxt.start) { walkways.push_back(Walkway{last_end, nxt.start, 0}); } walkways.push_back(nxt); last_end = nxt.end; } if(last_end < L) { walkways.push_back(Walkway{last_end, L, 0}); } n = walkways.size(); // because some new 0-speed walkways appeared BASE = 1; while(BASE < n) { BASE *= 2; } tree.resize(2 * BASE); for(int i = 0; i < n; ++i) { tree[BASE+i].init(walkways[i].max_saved()); } for(int i = BASE - 1; i >= 1; --i) { tree[i].merge(tree[2*i], tree[2*i+1]); } // sort by speed vector> indices; for(int i = 0; i < n; ++i) { indices.emplace_back(walkways[i].speed, i); } sort(indices.begin(), indices.end()); double answer = 0; for(pair pp : indices) { int me = pp.second; double pref = 0; // sum over delta[0..me-1] for(int i = BASE + me; i > 1; i /= 2) { if(i % 2 == 1) { pref += tree[i-1].sum; } } debug() << imie(pref); // assert(pref >= -eps); // non-negative double min_pref = pref; for(int i = BASE + me; i > 1; i /= 2) { if(i % 2 == 0) { min_pref = min(min_pref, pref + tree[i+1].min_pref); pref += tree[i+1].sum; } } // spending more than 'min_pref' energy would put as below 0 at some point // min_pref could be negative what means that this walkway needs to provide savings double wanna_spend = min(min_pref, walkways[me].max_used()); debug() << imie(wanna_spend); tree[BASE+me].init(-wanna_spend); for(int i = (BASE + me) / 2; i >= 1; i /= 2) { tree[i].merge(tree[2*i], tree[2*i+1]); } // energy spent = (s - 1) * t where s is my walking speed and t is time // t = len / (s + me.speed) double X = walkways[me].speed; debug() << imie(X); // (s-1)/(s+X) = en_spent / len // 1 - (X+1)/(s+X) = en_spent / len // (X+1)/(s+X) = 1 - en_spent / len double s = (X + 1) / (1 - wanna_spend / walkways[me].len()) - X; debug() << imie(me) imie(wanna_spend) imie(X) imie(s); // assert(-eps <= s && s <= 2 + eps); double t = walkways[me].len() / (s + X); answer += t; } printf("%.12lf\n", answer); // assert(tree[1].min_pref >= -eps); }
 » 3 years ago, # | ← Rev. 4 →   -52 poor:<
 » 3 years ago, # | ← Rev. 2 →   +9 this problem is simillar to D https://codeforces.com/gym/102268/problem/F (code which got AC at D got AC at this problem)
 » 3 years ago, # |   +19 Bessie the Cow has come to Codeforces :)
 » 3 years ago, # |   -21 Very nice problemset! Thank you for the contest.
•  » » 3 years ago, # ^ |   -8 Could E1 have been solved entirely with implementation, or did it require dp?
•  » » » 3 years ago, # ^ |   +6 It could. I found the 4 columns with the biggest max.value and bruteforced every possible combination of shifts.
 » 3 years ago, # |   -8 how to solve B? all i can think is simulating the condition one by one
•  » » 3 years ago, # ^ |   0 Yes, exactly.
•  » » » 3 years ago, # ^ |   0 Can you explain, how to simulate Problem B...?
•  » » » » 3 years ago, # ^ |   0 We simply start with the initial configuration and run X trials. In my code, X = 50K, but I think that's overkill, some solutions use as little as 200, but better safe than sorry :) I haven't gotten around to a formal proof, though I'm sure there is one.Anyway, on a single trial we go through all of the candles and check whether the i-th candle needs to be toggled. It boils down to the following equation:current_time = a + bkorcurrent_time — a = bkorcurrent_time — a = 0 (mod b)We check that condition for every candle, and, if it is true, toggle it. On every trial we update the maximum number of lighted candles. After the trials are over, we output the maximum.
•  » » » » » 3 years ago, # ^ |   0 Would it be correct to argue that, since $lcm(2,3,4,5) = 60$, every bulb will repeat after $60$ time steps. So you don't need to check times after $60+5$. But like you said, I didn't try a small amount to stay on the safe side.
•  » » » » » » 3 years ago, # ^ |   +14 Same, but lcm (2,4,6,8,10) = 120 and + 5 so I iterated from 0 to 125 exclusive and got accepted. Then tested for 0 to 124 to be sure and got wrong answer. You need twice those numbers because you are looking for a period, and full period is time on + time off, thus multiply by 2.
•  » » » » » » » 3 years ago, # ^ |   0 Yeah, I was also thinking that maybe we'll need twice of the lcm. Thanks for clarifying!
 » 3 years ago, # |   0 is D greedy ? I've tried to put the guests that has 2 types others have first but I think I'm missing something
•  » » 3 years ago, # ^ |   +12 I used DSU to solve D.
•  » » 3 years ago, # ^ |   +22 Create graph, for each connected component with x vertices you can satisfy x-1 guests.
•  » » » 3 years ago, # ^ |   0 Wow.I basically did the same thing, but I made that observation only for cycles, so I had to do additional work for non-cycles.That explains how there were solutions for D for several minutes :)
•  » » » 3 years ago, # ^ |   0 for each connected component with x vertices you can satisfy x-1 guests.Can u explain more??
•  » » 3 years ago, # ^ |   0 D is just M — (sum of sizes of connected component — number of connected components)... so yes, if you count any graph traversal to be greedy
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 [my bad]
•  » » » » 3 years ago, # ^ |   +2 At this point, no.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Can you help me see what's wrong with simply sorting given food preferences as pair ( also keeping minimum in pair as first ) and greedily calculating answer? I understand how people have done graph approach, but don't (yet) see what's wrong in mine.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +3 I tried the same first, mine was failing with: 4 3 1 3 2 4 3 4
 » 3 years ago, # |   0 How to solve F? I had an idea with Dijkstra and then greedy on the shortest path DAG but it's WA on test 10.
•  » » 3 years ago, # ^ |   0 Did you sort the DAG adjacency lists by the lexicographical order of numbers or by value? The latter is wrong.
•  » » » 3 years ago, # ^ |   0 Oh crap, you're right I sorted by value xD Thanks!
•  » » 3 years ago, # ^ |   0 I thought about fast Dijkstra with smth like trie and overloading comparator in set using this trie and binary jumps on it (LCA). But don't have enough time to finish idea and implement
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +8 I did it, but WA62UPD: It works, I have made a silly bug
•  » » 3 years ago, # ^ |   0 Store numbers in trie lca can be used to compare them.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 If one simply 1) compute minimum number of digits for reaching each node using Dijkstra; and 2) sort adjacency lists by lexicographical order; and 3) perform a greedy DFS on the resulting graph, making sure that the number of digits used is always equal to the minimum, one will get WA on test 47. (https://codeforces.com/contest/1209/submission/60551210)For example, if there existed an edge between node 1 and 2 with number 1, between 2 and 3 with number 2, and between 1 and 3 with number 11, this algorithm will choose 1->2->3, not 1->3.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +39 First, let's add some fake nodes on every edge separating number written on it by its digits. For example for the edge AB with 123 on it you create two more nodes and connect them like A-1-F1-2-F2-3-B. After that you can assume that you need to find the shortest path by the number of edges in this graph for each initial vertex, and choose the lexicographically smallest one among all paths with the smallest length, because numbers with bigger length in digits are like bigger). To do so you can run some sort of bfs. Suppose that you want to maintain all classes of equal by value paths with length x. To add one more edge, you iterate over all nodes in current level of bfs and add an ordered pair of (current class of node, digit on edge to the node in the next level) to current possibilities of going further. After that you need to select the smallest pair lexicographically for each node in the next level and update your classes just like in a suffix array building in O(n log n).
•  » » » 3 years ago, # ^ |   +18 If you traverse the edges in ascending order (all 0 edges then all 1 edges and so on) then you only need to care about the first time you visit a node (basically normal BFS).
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +18 Heh, seems that you got your point~ It's so simple and accurate idea. But at least the suffix array bfs sounds way more cooler)
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +10 I'am not sure, but it doesn't seem quite true. If there are two vertex with the same path to them, 0-edge from the second of them is preferable to us than 1-edge from the first, but we will consider them in the reverse order.
•  » » » » » 3 years ago, # ^ |   +10 Egor already mentioned this in his comment: Suppose that you want to maintain all classes of equal by value paths with length x. In normal BFS, you pop one node at a time and find new nodes by going from the node you just popped. For this problem, you will have to tweak it such that you will pop all nodes with same distance at a time. You can check my implementation here 60576572.
•  » » » » » » 3 years ago, # ^ |   0 Thanks, I understood, considering the component really fixes it.
•  » » » » » » 3 years ago, # ^ |   0 Hi. I saw your code and for the graph like this: your code would generate a graph like this one: whereas my code was trying to do something like this: but it's getting WA. Can you please tell why we cannot reuse existing vertices?
•  » » » » » » » 3 years ago, # ^ |   0 I used one vertex multiple times and got accepted.
•  » » » » » » » » 3 years ago, # ^ |   0 Thanks. Then there might be something wrong with my implementation. I'll try to see what's wrong with it.
 » 3 years ago, # | ← Rev. 2 →   -15 [DELETED]
 » 3 years ago, # | ← Rev. 2 →   -14 [DELETED]
 » 3 years ago, # |   -9 Can anyone tell me why the codeforces generate different output for problem C ? It is continuously generating wrong output for pretest 1 which is the given testcase. I tested my code on my local and every online IDE I could find and it was generating same correct output . I request to rejudge my problem C solution . Due to this I ended up submitting my code 4 times which would deduct so many points of mine . It is just unfair as hell . If you want I will post my code you can check for yourself.
•  » » 3 years ago, # ^ |   +3 UB.
•  » » 3 years ago, # ^ |   +11 You should test it in custom invocation tab.
•  » » » 3 years ago, # ^ |   0 I tested my code in custom invocation tab and its generating wrong output same as before . I tested my code multiple times on online ide and my local machine and its giving correct output. What should I do in this case?
•  » » » » 3 years ago, # ^ |   0 Run it locally under Valgrind/Memory Sanitizer/Address Sanitizer/UB Sanitizer. Alternatively, use custom invocation with "Clang++17 Diagnostics".Also, proofread the code to make sure it does not have undefined behavior (which is typically the reason behind different behavior on different machines).
•  » » » » » 3 years ago, # ^ |   0 seems like it was my fault after all . there was a bug in my code where I was trying to access negative index . But it would have been nicer if was my local machine also gave same output as codeforces.
 » 3 years ago, # |   +95 Bad difficulty distribution again :/ 141 people solved F, while G2 and H were only solved by 5 people each. Problems A-G1 were relatively easy too, so I'm very surprised four LGM-level testers didn't recognize the far-too-high difficulty jump.Also, G1 gives way too many points for how easy it is. More people solved it than E1, E2 or F, yet it gave more points than E1 and the same amount as E2. Additionally, since it was so much easier than F, the optimal strategy would have been to solve it before writing F. I think this trend of easy subtasks with inflated scores needs to stop, if not getting rid of subtasks altogether.
•  » » 3 years ago, # ^ |   +21 Agreed, my code for E2 took like an 30-40 minutes of coding+debugging, while I needed <10mins to read, code & submit G1. And I didn't even read G1 until quite late, because I expected it to be more like G-level problem
•  » » 3 years ago, # ^ |   +36 E1 is fine because I can optimize its code for E2. G1 however should not exist.
•  » » 3 years ago, # ^ |   -10 I believe subtasks are good at differentiating people who 1) cannot solve neither E1 nor E2, 2) those who can solve only E1, 3) those who solve E1 and after an hour come up with a solution for E2, and 4) good programmers who solve E2 in the first place.
•  » » 3 years ago, # ^ |   +5 G1 took me longer to figure out than E1+E2. I looked at E2, "hmm if $N=M$ then just subset DP in $O(4^N)$ and seems like I can sort the columns and take top $M$", then I checked if the second observation holds, wrote a solution, submitted, done. F killed me, I barely submitted and I'm really not sure if it's going to pass systests.
•  » » 3 years ago, # ^ |   +46 Very true, I don't see any point in these subtasks except for wasting participant's time on solving some partial cases of the problem. Yet for some reason they become more and more popular on codeforces. This has to stop.
•  » » » 3 years ago, # ^ |   +36 I would like to understand this topic more to make smart decisions in the future. Why don't you like subtasks? any point in these subtasks the goal was obviously to provide an easy problem for beginners and at the same time not waste much time of top participants who can just skip easy version. That's not necessarily true today in this particular contest but you clearly complain about subtasks in general. Right?
•  » » » » 3 years ago, # ^ |   +30 I don't like subtasks in general because if part 2 is sufficiently hard, you have to write (usually quite boring) first part to get more optimal points on the problem.It's less bad in contests where you only care about last submission time such as GCJ.
•  » » » » 3 years ago, # ^ |   +63 To be honest, they simply irritate me in codeforces rounds. I usually don't like solving partial cases of the problem to earn few points as I don't see this points to be "fair". Subtasks are acceptable in some long rounds (like codechef long) or rounds with really small amount of problems (like ioi and stuff). You have the time to investigate the problem and solving subtasks usually advance you to the solution of the bigger problem or, at least, of some bigger subtasks. In codeforces it's often not the case and when you solve smaller subtask, you basically have to start from scratch in solving harder one (at least, I feel it this way). And you don't have time to investigate the problem, you're under constant pressure of clocks going too fast and round being too short.Subtasks might be used in codeforces rounds in some exceptional cases, but now it is hard to find recent div. 1 round without subtasks and I clearly don't like it.
•  » » 3 years ago, # ^ |   +26 "Additionally, since it was so much easier than F, the optimal strategy would have been to solve it before writing F." — and what is wrong with that? Recommended strategy is solve problems in increasing number of points so of course you should try reading and solving G1 before F.
•  » » 3 years ago, # ^ | ← Rev. 4 →   +23 And G1 makes it kind of 'unworth' solving G2, as it's much more difficult than F and deserves more points. QwQBy the way, it leads to a result that solving H offers 4000 points while solving G only results in 2250. Just look at the scoreboard: ABCDEFG1H always ahead of ABCDEFG.UPD: The problems themselves are quite awesome, though. Just hope a better score distribution.
 » 3 years ago, # |   0 How to solve C？ just DFS? i trid,WA on pertest 4，im so weak...
•  » » 3 years ago, # ^ |   0 I'm not sure but maybe finding the longest non-decreasing subsequence and marking all elements in it as 1 and if the rest of the elements aren't in sorted order there's no solution otherwise mark others as 2.
•  » » » 3 years ago, # ^ |   0 I copy the array of characters and sort it. Then, I compare with the original characters and find them according to the order of the sorted characters. If they do not follow the order, then it is impossible. Maybe the test cases are not strong, my submission is accepted. Here is my solution: 60555056
 » 3 years ago, # |   0 Is there an easier way to solve G2 than maintaining 2-edge-connected components?By the way, very nice problemset! C was really cool.
•  » » 3 years ago, # ^ | ← Rev. 2 →   -6 Create a sequence X with zeros. For every set of positions of the same value, for the segment between first and last occurrence add +1 in X. Then, we're looking for minima in X and between every two consecutive minima: a number that occurs most times. If for first occurrence of a value you store the number of occurrences of this value then the whole thing can be done with a segment tree.Marcin_smu did it easier, without any interval operations. I don't know how though. my code#include using namespace std; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge range(c i, c j) { return rge{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " struct Node { int small, lazy; int max_pref, between, max_suf, any_max; void merge(Node& L, Node& R) { assert(lazy == 0); any_max = max(L.any_max, R.any_max); if(L.small == R.small) { max_pref = L.max_pref; between = L.between + max(L.max_suf, R.max_pref) + R.between; max_suf = R.max_suf; } else if(L.small < R.small) { max_pref = L.max_pref; between = L.between; max_suf = max(L.max_suf, R.any_max); } else { // L.small > R.small max_suf = R.max_suf; between = R.between; max_pref = max(L.any_max, R.max_pref); } small = min(L.small, R.small); } void increase(int by) { small += by; lazy += by; } void set(int x) { // I am leaf max_pref = 0; between = 0; max_suf = x; any_max = x; } }; vector tree; int BASE; const int SET = -1, ADD = -2; void rec(int id, int low, int high, int q_low, int q_high, int type, int x) { if(high < q_low || q_high < low) { return; } if(q_low <= low && high <= q_high) { if(type == SET) { debug() << "set" imie(id) imie(x); assert(low == high); // leaf tree[id].set(x); } else if(type == ADD) { tree[id].increase(x); debug() << "increase" imie(id) imie(x); } else { assert(false); // unknown type } return; } for(int c : {2 * id, 2 * id + 1}) { tree[c].increase(tree[id].lazy); } tree[id].lazy = 0; int last_left = (low + high) / 2; rec(2 * id, low, last_left, q_low, q_high, type, x); rec(2 * id + 1, last_left + 1, high, q_low, q_high, type, x); tree[id].merge(tree[2*id], tree[2*id+1]); } const int nax = 2e5 + 5; set pos[nax]; // positinos with this value void turn_off(int value) { if(!pos[value].empty()) { int L = *pos[value].begin(); int R = *pos[value].rbegin(); if(L < R) { debug() << "-1 " imie(L + 1) imie(R); rec(1, 0, BASE - 1, L + 1, R, ADD, -1); } debug() << "SET" imie(L) imie(0); rec(1, 0, BASE - 1, L, L, SET, 0); } } void turn_on(int value) { if(!pos[value].empty()) { int L = *pos[value].begin(); int R = *pos[value].rbegin(); if(L < R) { debug() << "+1 " imie(L + 1) imie(R); rec(1, 0, BASE - 1, L + 1, R, ADD, +1); } debug() << "SET" imie(L) << pos[value].size(); rec(1, 0, BASE - 1, L, L, SET, pos[value].size()); } } void add(int i, int value) { debug(); debug() << "add" imie(i) imie(value); turn_off(value); pos[value].insert(i); turn_on(value); } void rem(int i, int value) { turn_off(value); pos[value].erase(i); turn_on(value); } int main() { int n, q; scanf("%d%d", &n, &q); BASE = 1; while(BASE < n) { BASE *= 2; } tree.resize(2 * BASE); for(int i = 0; i < 2 * BASE; ++i) { tree[i].small = 4 * n; } vector a(n); for(int i = 0; i < n; ++i) { scanf("%d", &a[i]); add(i, a[i]); } for(int tt = 0; tt <= q; ++tt) { if(tt != 0) { int i, x; scanf("%d%d", &i, &x); --i; rem(i, a[i]); a[i] = x; add(i, a[i]); } debug() << imie(tree[1].max_pref) imie(tree[1].between) imie(tree[1].max_suf) imie(tree[1].any_max); printf("%d\n", n - (tree[1].max_pref + tree[1].between + tree[1].max_suf)); } debug() << imie(a); }
 » 3 years ago, # |   -11 hahaha
 » 3 years ago, # |   +14 Is G1 simply merging the intervals?
•  » » 3 years ago, # ^ |   +6 A DSU based implementation of G1, https://codeforces.com/blog/entry/69791?#comment-542689
 » 3 years ago, # |   +221
•  » » 3 years ago, # ^ | ← Rev. 2 →   -19 This meme suggests that it was good to have subtasks in E and G. Was that intended? ;p (I messed up)The goal of subtasks for E and G was to make the qualification (for the event) nice and without difficulty gaps. I agree that G1 should be lower-scored or non-existing, sorry about that. I don't think there was any tester that solved all problems to find the difficulty gap between F and G. I asked some of my friends to test G or H, and other testers mainly solved easier problems. There just aren't usually strong people that have enough time to test everything :( and this contest was kind of rushed so we didn't have time for an editorial, sorry for that too.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +24 You can estimate difficulty by explaining solutions to testers after they've tried all problems they can and letting them give input based on that. When I tested 580, I gave input based on my intuition even for problems I couldn't solve. This meme suggests that it was good to have subtasks in E and G. Lurk more on /b/. The usual template is that the guy that gets thrown out of the window offers an obviously good or asked for but not really tried idea while the other two propose stuff nobody asked for or ideas that were tried but didn't work (not bad per se, but considered worse by the author). Example. I'm not counting ironic meme and antimeme variations.
•  » » » » 3 years ago, # ^ |   +23 Yup, I agree it needs to be done more often. But here G was quite easy to come up with a solution and only hard to implement. We still realized that it's hard and gave half more points than for F. That's like a jump from 2000 to 3000 points.
•  » » » » » 3 years ago, # ^ |   +1 Sure. I don't mind the difficulties, G2 probably should have had a greater portion of G's points but it's not a big deal, at least it made difficulty jumps less steep.
•  » » » 3 years ago, # ^ |   -13 Actually, I change my mind. G1 should not be lower-scored. It isn't easier than D and for sure not much easier (enough to make an issue out of it). Obviously, G2 should get more points.
 » 3 years ago, # | ← Rev. 3 →   +4 Who suggest subtask for G? Such thing is bullshit. Looking at scoreboard, G2 < F LOL while > 100 people solve F, what is for G2?
•  » » 3 years ago, # ^ |   +32 I was one of people that agreed for that subtask and explained a reason above. Indeed, the scoring was bad though.
 » 3 years ago, # |   +44 Could you let us see other participants' solutions?
 » 3 years ago, # |   +22 Codes still closed , reason ?
 » 3 years ago, # |   +8 Still not able to see the test cases
 » 3 years ago, # | ← Rev. 2 →   +17
•  » » 3 years ago, # ^ |   0 can't see video.
•  » » » 3 years ago, # ^ |   0 It is still processing, also the link was wrong in the first edit.
•  » » 3 years ago, # ^ |   0 Yay, now I can watch you fail F!
•  » » » 3 years ago, # ^ |   +16 Knock yourself out.
 » 3 years ago, # |   -17 Really good problem set.
 » 3 years ago, # |   0 The announcement of the Dasha Code Championship says this about the first round: The round will be rated, open to all members of the Codeforces community. Top 30 competitors will receive official Dasha t-shirts! While this blog states There are Dasha t-shirts for top 30 competitors (not counting later-to-be onsite finalists). Which of these is correct? Will the top 30 contestants who choose not to attend the onsite-event receive shirts, or will the shirts be given to the top 30 contestants, regardless of whether they participate in the onsite?
 » 3 years ago, # |   0 How to get a tight upper bound for the simulation in problem B? Also, is there any other approach other than simulation?
 » 3 years ago, # |   0 Can anyone hack my randomized solution for E1?
 » 3 years ago, # | ← Rev. 2 →   0 svf
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 #
 » 3 years ago, # | ← Rev. 4 →   +23 G2 accepted by $O(m\cdot n^\frac{2}{3})$ (sqrt decomposition) and SIMD optimizations of GCC: 60577013
•  » » 3 years ago, # ^ |   +3 What a beautiful time complexity XD
 » 3 years ago, # |   0 First three were easy ones. Naive implementation required only :)
 » 3 years ago, # |   +47 I was debug-submitting my solution for F with incorrect idea and got AC. Although it should have TL and WA. Hello to problemsetters and testers. Here is idea of INCORRECT solution: Let's launch Dijkstra from 1, where weight is equal to the length of value of the path and also build tree of shortest paths simultaneously and support online LCA on it. So now we will update shortest path for vertice $to$ if we go from vertice $v$ if length of value of the path is smaller or if length of value of the path is equal and prefix of some length of path from $LCA(v, to)$ to $v$ is smaller than prefix of some length of path from $LCA(v, to)$ to $to$. In debug submit prefix length is equal to 500 edges. It's possible to find the test with TL and WA. I wonder why there are no test when there are 2 paths from 1 to $v$ with same lengths and with LCP of $O(n)$ length. For me it seems like obvious test.https://codeforces.com/contest/1209/submission/60576721
 » 3 years ago, # |   +9 Can anyone help me with G1?
•  » » 3 years ago, # ^ |   -27 NO!! become purple first
•  » » » 3 years ago, # ^ |   0 Thanks bro
•  » » 3 years ago, # ^ |   +3 Check out this explanation using DSU, https://codeforces.com/blog/entry/69791?#comment-542689
 » 3 years ago, # |   -15 Errichto Is there any way to solve problem E1/E2 by max flow?
•  » » 3 years ago, # ^ |   +5 I'm not aware of any and I didn't think about it. The only thing I did there was to write some randomized approach to break tests.
 » 3 years ago, # |   0 I tried to solve E2 using randomization, and finally I got AC :360578430
 » 3 years ago, # |   0 Could someone help me figure out whats wrong in my solution 60578600. Basic idea was to maintain 2 vectors one and two and both satisfy the condition of maintaining elements in increasing order, at some point of time if I can't place in the 1st array I try to relocate elements by popping from the first and moving into the second until I find a suitable place. If at some point I am not able to do the above I report answer as NO.
 » 3 years ago, # |   +3 Any proof of D ?
 » 3 years ago, # | ← Rev. 2 →   +8 Errichto How to choose the upper limit for time in problem B? if they have periods T1, T2,... they would repeat after LCM of T1,T2, ... ,but with a shift I don't know a formula for that!!I see 1000 would pass the test.
 » 3 years ago, # | ← Rev. 2 →   +20 I am writing this post to say a thank you to Errichto and others who helped him for this contest. I believe preparing 10 problems in a short amount of time is a tough task, and I believe they did a great job . We should be thankful to Codeforces and everyone who made this happen. I am 31 years old and decided to start practicing competitive programming problems again after being inactive in some years. During the last 3 months, I learned a lot from great problems, and I am always glad to have the chance to practice in such a wonderful platform, i.e. Codeforces.I am really surprised why some (even some red coders which I suppose to behave more maturely based on their experience in contests) complain about some small things such as 250 points difference between problems G2 and F. In some cases, they question everything, and posts are getting more aggressive. This is not what we expect from this wonderful community.
 » 3 years ago, # |   +22 When will the tutorial be published ?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +8 It is out now! Hope you enjoyed the contest!Editorial
•  » » » 3 years ago, # ^ |   0 OK, thank you and really I enjoyed the contest.
 » 3 years ago, # |   0 In problem D , How to get hint from the problem that dsu will be used in it ?
•  » » 3 years ago, # ^ |   0 There's no DSU in the optimal solution.
 » 3 years ago, # |   0 Could someone explain the idea of Problem C. Thanks in advance.
 » 3 years ago, # |   0 after reading problem C,i understood nothing.please explain the problem in a better way
 » 3 years ago, # |   +11 I can not warp my mind around problem E. To me it seems like if we just select n maximum numbers from the matrix and put them in our desiring rows by just shifting them, then the result would be the sum of those maximum n numbers. Can any one point to me how this is wrong?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +9 Try this 4 21 110 1010 11 10There is no way to get 40, in fact the answer is 31. Your approach works only with N<=3.
•  » » » 3 years ago, # ^ |   +3 Yes, I think I got it, thanks a lot man.
 » 3 years ago, # |   0 Fast system testing, fast rating changes, good problems. Best contest ever
 » 3 years ago, # |   -8 It was my first contest at Codeforces !!Unfortunately, I used ideone.com with the default setting, and someone copied my code... ;(but, contest was so good :)
 » 3 years ago, # |   +24 When there will be the list of onsite finalists?
 » 3 years ago, # | ← Rev. 2 →   +3 ai luv purupulem efu
 » 3 years ago, # |   0 Can someone explain how the complexity for E1 was calculated and if the possible the logic of bit masking in this problem. I solved it by brute forcing the different permutation for the n columns container the largest elements but cannot solve it using dp
 » 3 years ago, # | ← Rev. 2 →   0 Deleted
 » 3 years ago, # |   +10 When will T-Shirt winners announce ?
 » 3 years ago, # |   +37 Congratulations to the winners of T-shirts! :)30 best participants, except for the participants of onsite rounds. 1. Petr 3. LayCurse 4. zeliboba 5. 300iq 6. sunset 7. djq_cpp 8. maroonrk 9. LHiC 10. Um_nik 11. tourist 12. Endagorion 13. Anadi 14. Kostroma 15. webmaster 16. neal 18. zx2003 19. lumibons 20. zemen 21. RAVEman 22. Batrr 23. ko_osaga 24. Shayan 25. danya090699 26. Swistakk 27. _h_ 28. Panole233 29. inaFSTream 30. gisp_zjz