UPD:Minor mistakes in grammar and expression fixed.
Disclaimer: This is not an official editorial.
If you have better or easy-to-understand solutions and thoughts, feel free to share your idea. Also welcome to point out mistakes so I can fix it.
160A - Twins
It's obvious that you should take the most valueable coins. so sort values in non-decreasing order, then take coins from the most valueable to the least, until you get strictly more than half of total value.
Time complexity depends on the sorting algorithm you use. O(n^2) is also acceptable, but if you use bogosort which runs in O(n!)...
160B - Unlucky Ticket
Deal with the situation that "first half is strictly less than second half" first. the other one can be solved accordingly.
You can use greedy here: sort digits in first and second half seperately. then if the i-th digit in first half is always less than i-th in second half for 1<=i<=n, answer is YES.
Time complexity is as same as problem A. Count sort may run faster in O(n+10), but it's not necessary .
160C - Find Pair
This is a tricky problem. When contest ends, I found there are 12 pages of accepted submissions while 60 pages of "WA on pretest 3" submissions.
First of all, sort a[].
A natural consideration is that the answer equals to (a[k/n] , a[k%n]). This algorithm will pass the sample and get "WA on pretest 3". In fact, it works only when all a[i] are distinct.
To get an AC, let's make elements distinct and weighted. For example, if there are ten 1s, we remain one of them and set its weight as 10. Now go over the whole array. for each element a[i], we can make weight[i]*n pairs using a[i] as first element. If k doesn't exceed that, go over the array again and find the second element, then print the answer. Otherwise, subtract it from K and go on.
Sort algorithm working in O(n log n) is acceptable. Java and Pascal users should beware of anti-quicksort tests.
160D - Edges in MST
Let's take a look at Kruskal Algorithm which solve MST in O(m log m) time. Sort the edges first in weight non-decreasing order, then process each edges. if the edge connects two different connected compoments, add this edge to MST then combine two compoments. We use disjoint-set union here to maintain connectivity.
The main point is that only those edges with same weight may replace each other in MST. First of all, sort edges as what Kruskal do. To get the answer, we construct MST in weight non-decreasing order, and process all edges with same weight together. Now on each step we are to face some edges with same weight x and a forest of connected compoments.
Note that for an edge, what points it connects does not matter, we only need to know what compoments it connects. Now build a new graph G', each point in G' is a connected compoment in the original forest,and edges are added to connect compoments that it connected before. Time complexity is O(|E|) here, with careful implementation.
Let's answer queries on these edges. First of all, if an edge in G' is a loop(connects the same compoment), this edge must not appear in any MSTs. If after deleting an edge V in G', G's connectivity is changed (A connected compoment in G' spilt into two. We call these edges bridge), V must be in any of MST. All edges left can appear in some MSTs, but not any.
What's left is to get all of V quickly. Maybe you hear about Tarjan before, he invented an algorithm based on DFS to get all bridges in an edge-undirected graph in O(|V|+|E|). Read this page on Wikipedia for detailed information: http://en.wikipedia.org/wiki/Bridge_(graph_theory)
Considering those compoments which don't have any edges connected don't need to be appear in G', we have |V|<=2|E|, so time complexity for Tarjan's DFS is O(|E|), where |E| is count of edges weighted x. Because each edge will be used exactly once in G', total time complexity except sorting is O(m).
160E - Buses and People
As what problem setter say, we sort the people and bus together with non-decreasing order of time first(if a bus and a person has same time, put the person first). Solving it by "For each person find which bus he should take" will become rather difficult, so let's take another idea: For each bus, find who it will take.
Abstract a person as a element in currently waiting list. Now, go over the sorted people and buses, we should apply two operations:
For a person, add it to the list.
For a bus, find all person in list satisfying sj ≤ li, ri ≤ fj ,remove them from the list and record the answer.(bi ≤ tj is hold, because we process these operation by time order.)
You will find it easy to solve this using any kind of balanced trees, like AVL or SBT. For each node i on balanced tree, we store r[i] as keyword and l[i] as value, then maintain the maxinum l[i] on every subtrees. Operating on a person is to add him to the tree. When dealing with a bus, we find the node i with maxinum l[i] in the range x<=f[j] (x is keyword), if l[i]>=s[j] is satisfied, delete the node i, set ans[i]=j, update the tree and search again until found l[i]<s[j].
If you are not familiar with balanced tree, discretize every r[i] and f[j], then use a segment tree to solve it.
Time complexity is O((n+m) log (n+m)) with balanced trees or segment tree.
Just a sofa
This solution is so good that I got a lot after appreciating it. What's more,I think it is not necessary to publish another solution called "official editorial"
Thank you for your encouragement >_<
Good job:) Your post is simple and clear.
thx ^ ^
Thanks,it's very clear~
Thanks for the solutions. Just one suggestion for the 160D - Edges in MST. Instead of using Tarjan Algorithm for computing the Connected Components/Bridges, we can maintain a Union Find Data structure which keeps track of the ancestor of a particular vertex. To check if 2 vertices connect different components just query for their ancestors and check whether they are equal or not. For merging part you can use the merge operation on the union find data structure. Find more information of Union find http://people.cs.umass.edu/~barring/cs611/lecture/7.pdf.
After reading the lecture you give I found the "Union Find Structure" is just an alternative saying of disjoint-set union which I've mentioned before when introducing Kruskal's MST Algorithm. What's more, I don't see your points here...How can we get all bridges using disjoint-set and only it? Maybe you can provide an AC code so I can get your idea.
Could you explain more about how we can use this data structure to count bridges? It's all right when we add a new edge which is a bridge at that time, but I don't think it works when we add a new edge which makes some edges no longer bridges.
I found some videos that explain Tarjan's algorithm to find bridges (for problem D). Wikipedia was not very useful.
Intro to Algorithms.
can anyone explain problem D in more simpler way?
I got a weird solution for problem D which doesn't include searching bridges :D If you're interested, feel free to PM me :)
TWINS PROBLEM
include<bits/stdc++.h>
using namespace std;
int main(){ int n; cin>>n;
return 0; }
could anyone check the code it is giving wrong answer to testcase 4 why it is so??
79911754 You can reverse sort and then iterate
For anyone looking for a segment tree solution for problem E:
Use coordinate compression (discretization) on time values and build a segment tree on these compressed values.
Sort both buses and people by L-values. For a person say x with l value as l_x, process all buses with l value l_b such that l_b <= l_x.
In segment tree, store the rValues of the buses in the leaf nodes of segment tree. ie: If a bus travels at time x(after coordinate compression) from stop l to r, store r in the segTree node corresponding to range (x-x).
The segment tree is built on the unique time values. Since for each time value, there can be at max 1 bus, we make use of time values in seg tree. Corresponding to each time value, we store what R value does the bus at that time travel upto. Since we have sorted by L values in main, the answer can be processed directly because all buses in segment tree at a particular iteration have L values less than the one corresponding to the person who is travelling in a particular iteration. Thus just check if for the time after the arrival of that person, there exists some bus which travels to a rValue greater than or equal to rValue of that person.
In the leaf nodes of segTree, we maintain the busNumber of the bus that arrives at the time corresponding to that leaf node, as well as the R value of that bus.
In ancestors of these nodes, we store the max R value in their children which helps us search the best option for a particular passenger during query.
Link to submission
Alternate segment tree solution in which we build the segment tree on left coordinate of people (after coordinate compression).
https://codeforces.net/contest/160/submission/198560211