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* ≤ 10^{5}.

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 senek_k.

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

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(n^{2}) how to solve it innlog(n) ??no way

this is one of the solution for same problem but in another contest http://codeforces.com/contest/458/submission/7416845

This problem isn't the same. that problem is like problem from round 503 with

m= 2, but withmup 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 costoh 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 ≥

Kand add them to your party and make the followingfen1[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.com/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 whosec_{i}'s rank in partyp_{i}is not less thankshould be selected, and then select some minimumc_{i}until voters are selected. Increasingkand 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(n^{2}) 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..

eds467, 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 Ithinkrepresents 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.

Codehey 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

Looking at it again and again, i finally understand.

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)

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)?

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.

Mind if I ask more specifically why 2-sats cannot work? Thank you so much :D

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).

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? eds467

Nevermind, it's not a DAG. I misread the question. It's graph without self-loops, not without cycles:)

Regarding E: This might be a bit pedantic, but I'm surprised no one seems to have mentioned it. When you add 10

^{5}points with coordinates (10^{5}, 10^{9}), the sum looks like (10^{10}, 10^{14}). If you then multiply the two coordinates, you get 10^{24}, 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(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≈ 10^{4}, 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`

,oryou could use long longs to compute the continued fraction expansions of`a/b`

and`c/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 toA·B·n^{2}. Good that codeforces is modern programing site and have int128.Oh, wait... Nevermind, at least

rand() generates numbers up to 2^{31}.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.I got it,thank you

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!

thanks.

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.

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.com/contest/1020/submission/41604370 (it is a mess, but I will try to upload a better, cleaner one soon :) )

thank you!

Please add source codes

Here is my code for question 'B': 59775091 Let me know if I can do it better...

Wait, does 1019E utilize convex hull trick, or just convex hull?

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

vwe test if any vertexuthat has an edge (u,v) has been included. If so, we don't do anything; otherwise, we addvto 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

Gand put it in another graphG_{2}.Now, we solve the problem for our new DAG

Gusing toposort. The problem is that we might have chosen vertices that are adjacent inG_{2}, since we ignored those edges. The key observation here is thatG_{2}is also a DAG. To see why, consider the DFS tree which we used to constructG_{2}. The edges we picked only go up in the tree, so they cannot form a cycle. Thus, we can also solve the problem separately forG_{2}, only caring for the vertices that conflict inG(both have been chosen but they have a direct edge inG_{2}). 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 inGand, among the conflicts, only the vertices that have been chosen inG_{2}as well, by transitivity we get a solution for that reaches every vertex in at most 2 steps.Code