problem elections can be solved using ternary search, how ??

i already solved it in O(n²) how to solve it in nlog(n) ??

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.

#include<bits/stdc++.h>

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<int> 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;
}

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.

Regarding E: This might be a bit pedantic, but I'm surprised no one seems to have mentioned it. When you add 10⁵ points with coordinates (10⁵, 10⁹), the sum looks like (10¹⁰, 10¹⁴). If you then multiply the two coordinates, you get 10²⁴, 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.

#include <bits/stdc++.h>
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 ≈ 10⁴, 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.

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 ?

What's the full form SIS in SIS Olympiad?

can anyone help with explanation of div 2 c for easily understanding, got stuck in this problem for 3 days

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://mirror.codeforces.com/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 G₂.

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 G₂, since we ignored those edges. The key observation here is that G₂ is also a DAG. To see why, consider the DFS tree which we used to construct G₂. 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 G₂, only caring for the vertices that conflict in G (both have been chosen but they have a direct edge in G₂). 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 G₂ 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:

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> adj, ans;
vector<vector<int>> 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 << " ";
}

Can someone please define where my mistake is in problem B in O(N) Solution

Here's my submission: 221630255