object022's blog

Codeforces Round #111 (Div. 2) Solution
By object022, 13 years ago, In English

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:

  1. For a person, add it to the list.

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

  • Vote: I like it
  • +51
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
13 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Just a sofa

→ Reply
»
13 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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"

→ Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Good job:) Your post is simple and clear.

→ Reply
»
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks,it's very clear~

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I found some videos that explain Tarjan's algorithm to find bridges (for problem D). Wikipedia was not very useful.

Intro to Algorithms.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain problem D in more simpler way?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got a weird solution for problem D which doesn't include searching bridges :D If you're interested, feel free to PM me :)

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

TWINS PROBLEM

include<bits/stdc++.h>

using namespace std;

int main(){ int n; cin>>n;

vector<int> arr(n);

for(int i=0;i<n;i++){
    cin>>arr[i];
}

sort(arr.begin(),arr.end());

int sum=0,mysum=0;

for(int i=0;i<n;i++){
    sum+=arr[i];
}

for(int i=0;i<n;i++){
    mysum+=arr[i];
    sum -= arr[i];
    if(mysum > sum){
        cout<<i+1<<endl;
        break;
    }
}

return 0; }

could anyone check the code it is giving wrong answer to testcase 4 why it is so??

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

For anyone looking for a segment tree solution for problem E:

Hint1
Hint2
Hint3
Solution

Link to submission

→ Reply