Thank your for participation!
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 craborac.
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
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
problem elections can be solved using ternary search, how ??
i already solved it in O(n2) how to solve it in nlog(n) ??
no way
this is one of the solution for same problem but in another contest http://codeforces.me/contest/458/submission/7416845
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)
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
oh i misread, sorry
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 ?
i don't know any solution on high costs(
could you tell me how i can solve it in O(nlgn) with fenwick tree?i am weak in data structure :(
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 cost
look and trace my submission http://codeforces.me/contest/458/submission/41572445
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.
yes, sure, this solution works for the exact same problem with different constraints..
For Div2 C, one can also see this editorial also(round 2(c)). nlog(n) solution is described there. link to editorial
i don't understand the editorial, if you understand it, can you please make it clear here ?
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.me/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...)
thanks so much, this was so helpful for me
Can you explain me the reasoning? Thanks in advance..
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 betweeni
,tot
andpos
. Bothpos
andtot
depend uponi
, 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?What a beautiful task div.2 E was.
Amazing!!!!
I don't understand the logic begind "A. Elections". Could someone explain it to me please ?
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.
hey can you please comment out your code that would be very helpful
mangat my code is commented, under the code spoiler. For space safe reasons.
You only have to click in the Code part. Thanks
no i mean can you add comments in your code
Done, if you have any doubt ask me via Talks, I response to you
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:-
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)
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.
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.
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.
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).
I'm uncomfortable when can't solve a problem, then it turns out to be a theorem.
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.
In IOI there are many hard problems which can be solved by a short code, for example, IOI2017 D1T3 (Toy Train), IOI2014 D2T2 (Friends).
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.
(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
andc*b
, or you could use long longs to compute the continued fraction expansions ofa/b
andc/d
, and then compare the expansions.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.
Oh, wait... Nevermind, at least rand() generates numbers up to 231.
Hmmm, maybe just there isn't a penalty for WA on sample other that the first one?
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!
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.
I was like wtf! since when does codeforces support int128 it wasn't available the last time I checked.
So I wrote an "int96" to deal with multiplication. I want to know if there is a more convienient way to deal with it.
I have a trick, can one verify that:
It seems correct.
In large triangle can someone explain what they mean by radius vector of third point?
Could anyone write the optimized solution O(n) of problem B div 2 ?
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.
Can u write the code of B?
Yes
What's the full form SIS in SIS Olympiad?
Summer Informatics School
can anyone help with explanation of div 2 c for easily understanding, got stuck in this problem for 3 days
Hey!
You can have a look on the comment I wrote below!
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:
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:
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.me/contest/1020/submission/41604370 (it is a mess, but I will try to upload a better, cleaner one soon :) )
Doing random old contests, I happened to find another very different solution for Div1 C.
First, if the graph was a DAG, then we could solve the problem using a topological sort. Actually, we can guarantee that each vertex is either in the chosen set or can be reached in one edge (this is important). Just sort the vertices topologically, and for each v we test if any vertex u that has an edge (u, v) has been included. If so, we don't do anything; otherwise, we add v to the set.
However, the original graph is not a DAG. But it can be made one if we remove edges that form cycles. We run a DFS and for each back-edge, we remove that edge from the graph G and put it in another graph G2.
Now, we solve the problem for our new DAG G using toposort. The problem is that we might have chosen vertices that are adjacent in G2, since we ignored those edges. The key observation here is that G2 is also a DAG. To see why, consider the DFS tree which we used to construct G2. The edges we picked only go up in the tree, so they cannot form a cycle. Thus, we can also solve the problem separately for G2, only caring for the vertices that conflict in G (both have been chosen but they have a direct edge in G2). For both separate solutions, we have a set in each graph that allows us to go to every vertex in at most one edge. If we get only the vertices that have been chosen in G and, among the conflicts, only the vertices that have been chosen in G2 as well, by transitivity we get a solution for that reaches every vertex in at most 2 steps.
Code
O(N) solution for problem B div 2 (1020B - Badge) for those interested:
thank you so much for sharing, I had different thinking and approach to it. can you please review my submission?
here is my comment: https://codeforces.me/blog/entry/61161?#comment-1064893
Can someone please define where my mistake is in problem B in O(N) Solution
Here's my submission: 221630255