Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### cdkrot's blog

By cdkrot, history, 3 years ago,

Problem D2A (New Building) was authored and prepared by Burunduk2.

Problem D2B (Badge) was authored and prepared by me, the version in SIS's olympiad contained the version with n ≤ 105.

Problem D1A (Elections), D1B (Hat), D1D (Large Triangle) were authored by achulkov2, with D1A prepared by Schemtschik, D1B by achulkov2 and D1D prepared by achulkov2 and kraborak.

Problem D1C (Sergey's Problem) was authored and prepared by Morokei.

Problem D1E (Raining Season) was authored and prepared by izban.

Editorials were written by izban and VArtem

• +89

 » 3 years ago, # | ← Rev. 2 →   -7 problem elections can be solved using ternary search, how ??i already solved it in O(n2) how to solve it in nlog(n) ??
•  » » 3 years ago, # ^ |   0 no way
•  » » » 3 years ago, # ^ |   +3 this is one of the solution for same problem but in another contest http://codeforces.com/contest/458/submission/7416845
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 This problem isn't the same. that problem is like problem from round 503 with m = 2, but with m up to 3000 there are no such solution (i think)
•  » » » » » 3 years ago, # ^ |   0 what m = 2, look read both problems carefully they match!!! in old elections problem number of parties and voters are much bigger but with less constraints on cost
•  » » » » » » 3 years ago, # ^ |   -7 oh i misread, sorry
•  » » » » » » » 3 years ago, # ^ |   0 i understand a solution using fenwick tree but based on low constraints on cost. but i can't understand any solution on a high cost like 1e9. please if you know can you explain it ?
•  » » » » » » » » 3 years ago, # ^ |   0 i don't know any solution on high costs(
•  » » » » » » » » 3 years ago, # ^ |   0 could you tell me how i can solve it in O(nlgn) with fenwick tree?i am weak in data structure :(
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 3 →   +4 you use two fenwick arrays, fen1[i] is how many voters exist with cost  ≤ i.fen2[i] is what is the total cost of all the voters that have cost  ≤ i.now as editorial said, iterate through all K from n to 1, select every party that has voters  ≥ K and add them to your party and make the following fen1[cost[i]] -  = 1; fen2[cost[i]] -  = cost[i];now if you still have less than K just make binary search on fen1 to find needed voters with least costlook and trace my submission http://codeforces.com/contest/458/submission/41572445
•  » » » » » » » » » 2 years ago, # ^ |   0 Harolinch, your solution won't work in this problem as the cost can be upto $10^9$, and you can't make an array that long.
•  » » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +1 yes, sure, this solution works for the exact same problem with different constraints..
•  » » 3 years ago, # ^ |   +15 For Div2 C, one can also see this editorial also(round 2(c)). nlog(n) solution is described there. link to editorial
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +1 i don't understand the editorial, if you understand it, can you please make it clear here ?
•  » » 3 years ago, # ^ |   +11 It can be solved in by priority queue.The main idea is to enumerate the vote of party 1 as k, then all voters whose ci's rank in party pi is not less than k should be selected, and then select some minimum ci until voters are selected. Increasing k and use a priority queue to maintain the latter part.https://codeforces.com/contest/1019/submission/41524142(In the contest I came up with a wrong solution and found it wrong while testing samples, then I deleted the whole code and wrote O(n2) solution, after debugging I cost 28min to pass A...)
•  » » » 3 years ago, # ^ |   0 thanks so much, this was so helpful for me
•  » » » » 3 years ago, # ^ |   0 Can you explain me the reasoning? Thanks in advance..
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 consecutivelimit, I don't understand your code. I understand what's happening (somewhat) in your code, but I don't understand the "why". Especially the second for loop, which has intertwined relationships between i, tot and pos. Both pos and tot depend upon i, which I think represents the number of unprocessed non "our party" voters (not sure if correct). SoCan you explain the working of the second for loop?
 » 3 years ago, # |   +31 What a beautiful task div.2 E was.Amazing!!!!
 » 3 years ago, # |   0 I don't understand the logic begind "A. Elections". Could someone explain it to me please ?
 » 3 years ago, # | ← Rev. 3 →   +1 By the way I solved the B problem in O(N) time, the solution I use was: If a node belong to a cycle his end in himself. If a node does not belong to a cycle ends in the first cycle node his traverse visit.So I did something like Topological Sort and DSU to get the answer in O(N).My code solution for Div2 B. Code#include using namespace std; #define endl '\n' typedef long long int ll; const int MAX = 1005; int p[MAX], deg[MAX], ans[MAX]; int res(int i){return (i==ans[i] ? i : ans[i] = res(p[i]));} int main() { ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n;cin>>n; for(int i = 1; i<=n; ++i) { cin>>p[i];++deg[p[i]];//read and indegree count for each node } //init the topsort and dsu table queue q; for(int i = 1; i<=n; ++i)ans[i] = i; for(int i = 1; i<=n; ++i)if(deg[i]==0) q.push(i); //doing the topsort until the only remainning nodes are in cycles while(!q.empty()) { int nn = q.front();q.pop(); --deg[p[nn]];ans[nn] = p[nn]; if(deg[p[nn]]==0)q.push(p[nn]); } //and finally the funny part print your solution for(int i = 1; i<=n; ++i) cout << res(i) << ' '; return 0; } 
•  » » 3 years ago, # ^ |   0 hey can you please comment out your code that would be very helpful
•  » » » 3 years ago, # ^ |   0 mangat my code is commented, under the code spoiler. For space safe reasons.You only have to click in the Code part. Thanks
•  » » » » » 3 years ago, # ^ |   0 Done, if you have any doubt ask me via Talks, I response to you
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Looking at it again and again, i finally understand.
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 your res() function may run in linear time in worst case...so overall complexity may be quadratic in some case but I can't think of a test case right now... can you provide the proof that:- Your code here... //and finally the funny part print your solution for(int i = 1; i<=n; ++i) cout << res(i) << ' ';  this above part of your code run in linear? if yes. how??
•  » » » 23 months ago, # ^ |   0 Is linear cause res func ask if calculation on I is done if is it he answer in O(1) now with that and dsu you can prove that you won't visit a node twice so overall O(n)
 » 3 years ago, # |   0 A trivial doubt, if the constraints allowed, just printing the vertices which don't have an edge between them would have sufficed for Div 2 (E)?
 » 3 years ago, # |   +88 Div.1 C is really a good problem.In the contest, I thought about some greedy algorithms but they failed on my stress test, then I thought about solution on DAG, on SCC, or inserting the vertices one by one, but no one works.After the contest more than 50 people passed C except me, however, most of people who passed C FST, at last only 7 people passed, so I didn't lose my rating accidentally.Some contestants in National Training Team discussed about this problem, but no one found the right solution. Even fateice, fjzzq2002, yjq_naiive didn't pass C either.It's very amazing that such a hard problem can be solved by a simple algorithm, with about 20 lines' program.I like this type of problems, which is hard to think and easy to implement. I'm curious about how problem C is created.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +16 I have tried to solve this problem by 2-sat for a long time during the contest. But I finally found 2-sat is wrong after the contest.
•  » » » 2 years ago, # ^ |   0 Mind if I ask more specifically why 2-sats cannot work? Thank you so much :D
•  » » 3 years ago, # ^ | ← Rev. 4 →   -25 No! I think C is bad. It is an implementation version of a graph theorem. Even very high rating users can't come up with during contest. Especially, in the IOI style, it should never appear.
•  » » » 3 years ago, # ^ |   +35 It just means it's a hard problem... I think it could be a fine D or E, it's not like people have seen the theorem (or else they would have solved it).
•  » » » » 3 years ago, # ^ |   -24 I'm uncomfortable when can't solve a problem, then it turns out to be a theorem.
•  » » » » 3 years ago, # ^ |   -16 I think it is hard or not depend on where it place. In programming, people will try some ways like SSC, greedy, ... While in mathematics, induction is straightforward then it maybe easier.
•  » » » 3 years ago, # ^ |   +1 In IOI there are many hard problems which can be solved by a short code, for example, IOI2017 D1T3 (Toy Train), IOI2014 D2T2 (Friends).
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 The graph is a DAG. So why wouldn't topological sort work? I mean, we first sort it topologically and then add the first node if it's not visited and start BFS from that node. We only add alternate nodes to our answer set. Shouldn't this work? consecutivelimit
•  » » » 3 years ago, # ^ |   0 Nevermind, it's not a DAG. I misread the question. It's graph without self-loops, not without cycles:)
 » 3 years ago, # |   +44 Regarding E: This might be a bit pedantic, but I'm surprised no one seems to have mentioned it. When you add 105 points with coordinates (105, 109), the sum looks like (1010, 1014). If you then multiply the two coordinates, you get 1024, which overflows a long long. So a solution that computes convex hulls by checking something like ll(a)*d - ll(c)*b > 0 will behave unpredictably on some test cases.In particular, this generator seems to hack Radewoosh's solution. code#include using namespace std; #define rep(i,a,b) for(int i = a; i < (b); ++i) const int bl = 1e9, al = 1e5; int main(){ int x = 267; int a = 10, b = 20, c = 8, d = 5; a *= x, b *= x, c *= x, d *= x; int n = 1 + a+b+c+d, m = 10001; cout << n << ' ' << m << endl; rep(i,0,a) cout << i+1 << ' ' << i+2 << ' ' << 0 << ' ' << bl << endl; rep(i,0,b){ int s = i ? i+a+1 : 1; int t = i+2+a; cout << s << ' ' << t << ' ' << al << ' ' << 0 << endl; } rep(i,0,c) cout << i+a+b+1 << ' ' << i+a+b+2 << ' ' << 0 << ' ' << bl << endl; rep(i,0,d){ int s = i ? i+a+b+c+1 : 1+a+b; cout << s << ' ' << i+a+b+c+2 << ' ' << al << ' ' << 0 << endl; } } (It's a tree with only 3 leaves and vertex 1 in the middle. The distances are chosen to be large enough to result in overflow, and such that at t ≈ 104, the node which is actually furthest from 1 might be missed, since it is between to other nodes on the convex hull of distances.)To fix this, you could either use higher precision arithmetic when calculating a*d and c*b, or you could use long longs to compute the continued fraction expansions of a/b and c/d, and then compare the expansions.
•  » » 3 years ago, # ^ |   +19 Yes, I thought that I need numbers up to A·B·n (that's why I have unsigned long longs in one place in code), but I need numbers up to A·B·n2. Good that codeforces is modern programing site and have int128.
•  » » » 3 years ago, # ^ |   +9 Oh, wait... Nevermind, at least rand() generates numbers up to 231.
•  » » » » 3 years ago, # ^ |   +10 Hmmm, maybe just there isn't a penalty for WA on sample other that the first one?
•  » » » » » 3 years ago, # ^ |   +10 I'm not sure what you mean. I think the reason that you got AC is that for overflow to occur, there needs to be a very long path in the tree, and even then, you might well get the right answer by chance anyway. I would guess that the test data wasn't generated with overflow in mind, and that the constraints should really have been a bit lower, so that we wouldn't have to worry about overflow.Anyway, good job on solving this problem so quickly!
•  » » » » » » 3 years ago, # ^ |   +34 I was joking with second and third commend, but the first one was about the fact, that I wasn't able to use int128, because codeforces doesn't support them.
•  » » » » » » » 3 years ago, # ^ |   0 I was like wtf! since when does codeforces support int128 it wasn't available the last time I checked.
•  » » 3 years ago, # ^ |   +8 So I wrote an "int96" to deal with multiplication. I want to know if there is a more convienient way to deal with it.
•  » » » 3 years ago, # ^ |   +26 I have a trick, can one verify that: int cmp(long long a, long long b, long long c, long long d) { long double dif = (long double) a * b - (long double) c * d; if (abs(dif) > 1e18) return sign(dif); return sign(a * b - c * d); } 
•  » » » » 3 years ago, # ^ |   0 It seems correct.
 » 3 years ago, # |   0 In large triangle can someone explain what they mean by radius vector of third point?
 » 3 years ago, # |   +3 Could anyone write the optimized solution O(n) of problem B div 2 ?
•  » » 3 years ago, # ^ |   0 Construct the graph, it will be some amount of cycles and trees that grow from some vertex of cycle. If the vertex is on the cycle , then anser for this vertex is this vertex. If the vertex isn't on the cycle, the answer for it is the nearest vertex on the cycle, it can be precalculated in O(n) time.
•  » » » 3 years ago, # ^ |   0 I got it,thank you
•  » » » 11 months ago, # ^ |   0 Can u write the code of B?
•  » » » » 11 months ago, # ^ |   0 Yes
 » 3 years ago, # |   0 What's the full form SIS in SIS Olympiad?
•  » » 3 years ago, # ^ |   0 Summer Informatics School
 » 3 years ago, # |   0 can anyone help with explanation of div 2 c for easily understanding, got stuck in this problem for 3 days
•  » » 3 years ago, # ^ |   0 Hey!You can have a look on the comment I wrote below!
•  » » » 3 years ago, # ^ |   0 thanks.
 » 3 years ago, # |   -8 Can someone please help me with div 2 problem E (Sergey's problem) I didnt understand the solution I got the induction proof but I didnt get the implementation.
 » 3 years ago, # |   0 Another solutions for div2 C:Set Up:First, let me describe the set up. We create a 2D array where we store the voters' costs of each party in descending order (big to small) (partyVoters) and a single array where we store pairs of a voter's cost and the party they support and we sort it based on costs in ascending order (small to big) (moneySorted).Task:We need to get more voters (not equal!) than any other party. Let's say there are three parties with the following composition: 1 -> 0 voters 2 -> 3 voters 3 -> 5 voters In our case we need to get more voters that parties 2 and 3. Please note that when we buy a voter from another party, the number of voters of that party decreases, while ours increases (always by one). So, if we buy 4 votes from the 3rd, we have the following: 1 -> 4 voters 2 -> 3 voters 3 -> 1 voter (that means we won!) Solution:I solved the problem using a greedy algorithm. First of all, I created the arrays that I describe on the Set Up section as well the following variables: - curr -> it stores our current number of voters and - target -> it stores the number of votes we need to get in order to win the elections (note that this — variable stores the number of voters of the largest party(s) )After that, I created a while loop. On each iteration, after we check if we ensure that we have not reached the target yet (if we have, we just show the result!), we find all the parties (let's call their amount numParties) that have the most voters (equal to target) and we store their indexes. Now it comes the greedy part. We always have 2 optimal choices: 1. Either we can buy the cheapest voter from those parties. (and the target will be decreased by one and our votes are increased by numParties) 2. Or we can get numParties + 1 voters (note that from above that the fact that the target is -1 is equivalent of getting one more voter).So, we calculate the costs of both of the two cases the we choose the cheapest one. If the optimal choice is 1, we get rid of the last element from the 2D array for each party). On the other hand, if optimal is 2, we get rid of only the cheapest voter among all of them, as there is a possibility that on the next iteration the other option to be the optimal one and therefore we don't want to buy all of them now! :)And we repeat until the curr reaches the target! :)Solution:http://codeforces.com/contest/1020/submission/41604370 (it is a mess, but I will try to upload a better, cleaner one soon :) )
•  » » 3 years ago, # ^ |   0 thank you!
 » 3 weeks ago, # |   0 O(N) solution for problem B div 2 (1020B - Бейджик) for those interested: code#include using namespace std; int N; vector adj, ans; vector> radj; void fill_radj(int x) { for (auto &child : radj[x]) { /* * As all nodes in the cycle are processed in function floyd, * the recursive call will only start at the nodes which * combine the cycle with the acyclic part of the connected component * where one of its outgoing arrows points to the node that is not processed yet. */ if (ans[child] == -1) { ans[child] = ans[x]; fill_radj(child); } } } void floyd(int x) { int y = x; do { // find a cycle using Floyd's algorithm x = adj[x]; y = adj[adj[y]]; } while (y != x); do { // set ans[x] = x for all x along cycle ans[x] = x; x = adj[x]; } while (y != x); do { // set ans'es for all x not along cycle fill_radj(x); x = adj[x]; } while (y != x); } int main() { cin.tie(0)->sync_with_stdio(false); cin >> N; adj.assign(N, -1); for (auto &e : adj) { cin >> e; e--; } /* * For each node, we have to use a vector to store its children; * at nodes combining the cycle with other parts of the connected component, * there would be more than one outgoing arrow in the reversed adjacency list */ radj.assign(N, {}); for (int i = 0; i < N; i++) radj[adj[i]].push_back(i); ans.assign(N, -1); // we run Floyd's algorithm for each connected component for (int i = 0; i < N; i++) if (ans[i] == -1) floyd(i); for (auto &a : ans) cout << a + 1 << " "; }