This problem's statement and Russian solution is by winger. Construct bipartite graph G1 with available sets on the left side and the numbers on the right side. We put an edge from a set to all the numbers contained in it. By Hall's theorem it follows from "the union of any k sets contains no less than k distinct numbers (for every positive integer k)" that there exists perfect matching of all the elements in the bipartite graph (in fact the theorem states that there exists matching including all set vertices, but as the numbers are also restricted by n, this means that there exists perfect matching). After this observation we find whichever perfect matching in G1, let's denote it by M = {(ui, vi)}. Now we construct second oriented graph G2 with vertices corresponding to the available sets and edges (ui → uj) for each edge (ui, vj) from G1 that do not occur in M (Note that the matching sets the indices of v's and thus we consider them, not the values of the corresponding numbers). Now for every suitable collection of size k there should be no outgoing edge to other set in G2 (otherwise the numbers included in the sets of the collection will be k plus the additional few numbers from the corresponding outgoing edges and the collection will not be suitable - more numbers than sets). Thus our problem has been transformed to the following equivalent: in an oriented graph with weight of vertices find subset S of the vertices with minimum sum of weights and without outgoing edge with other end not in S. This problem is known to be equivalent to finding minimum cut (I wasn't able to prove the equivalence, didn't know it by heart either, but I found it even easier to prove if I consider the task as just max flow) . Assign to the edges of G2 infinite weights, add additional vertices s and t,. Now for every set ui with weight w add edge ui → t with weight w iff w > 0 and edge s → ui with weight - w iff w < 0. The part of the minimum cut of s and t in the constructed graph that contains s is the sought optimal collection (in fact what I did was sum the outgoing weights from s after computing max flow in the graph; I was able to prove this is the required number). |
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
I would be very grateful if there was a way to turn off tags for particular competition, or even for a user as a whole. I know it is too arrogant to ask even more once we have such a beautiful site for problem solving, but I certainly hope this is not such big deal of implementation and I believe that this will improve the after-contest solving experience, which, of course, is the most important part of programing competitions.
Topcoder Open 2011 started recently. This weekend was the first qualification round of the algorithm competition. I had an interesting experience during it, which I want to share.
The second problem was not that hard, though my solution seems to be too stupid for it. You can check out the statement here. I solve it with quite naive approach as follows:
double dp[80002][50];
class FoxListeningToMusic {
public:
vector <double> getProbabilities(vector <int> length, int T) {
memset(dp, 0, sizeof(dp));
int n = length.size();
for(int i = 0; i < n; i++)
dp[0][i] = 1.0 / (double)n;
double mul = 1.0 / (double)n;
int idx ;
for(int i = 1; i <= T; i++) {
for(int j = 0; j < n; j++) {
idx = i - length[j];
if(idx >= 0) {
for(int k = 0; k < n; k++)
dp[i][k] += mul * dp[idx][k];
}
else
dp[i][j] += mul;
}
}
}
vector<double> v(n);
for(int i = 0; i < n; i++)
v[i] = dp[T][i];
return v;
}
};
It is not important weather the code is solving the problem with correct answers, at least for what I am going to discuss. The fact is that I got time limit with this code. It was somehow expected as the complexity here is O(T * length.size() ^ 2), which becomes 2 * 108 if we take into account the problem constraints. However, the interesting thing is that I tested into the arena before submitting. The case I used seems to be "worst case" for my solution: 50 1s given in length and T = 80000. The code ran for 0.365 seconds. This is quite below the time limit of 2 seconds. I submitted and then was pretty surprised to see I almost did not manage to qualify to Round 1, with 250 ptr only.
I say the case I used is the worst case, because the number of instructions what will be executed depends only on the branching condition idx >= 0 in the inner for. If this is true one more cycle is to be executed (the cycle is of complexity O(n)). In the other case only a single operation O(1) will be executed. And as you can see the less the elements in length the more times this becomes true.
Even though this reasoning, my problem fails the following case:
length = {1, 1, 1, 1, 3, 3, 3, 3, 1, 3, 3, 2, 3, 2, 3, 3, 1, 2, 3, 1, 2, 3, 2, 1, 3, 1, 1, 1, 2, 3, 2, 3, 2, 2, 1, 3, 1, 1, 3, 1, 3, 1, 3, 2, 3, 1, 1, 3, 2, 76393} T= 77297.
For this case my program runs for 5.204000 seconds on my computer (my computer is significantly slower than Topcoder's, but I am going to show you runtimes on my machine, as here the ratio is what matters), whereas
length = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} T = 80000 runs for 0.750000 on my machine.
My first assumption was that the reason for this unexpected ratio of runtime measurements (as long as we should expect that in the first case quite fewer processor instructions are to be executed) was that the processor caches somehow the similar calculations: in my example the calculations are symmetric with regard to all the elements of length and really clever processor can use this to spare repeating the same sequence of instructions. So I tried composing another example: this time with different values in length array:
length = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 77943} T=80000 runs for 0.813000 seconds on my machine.
After this example I am no longer able to say how come these time measures - my second example seems to require more processor instructions than the test that failed me and does not allow the caching I thought was happening in the first example. Actually I have not been able to define the cause of this behavior, but I am quite sure it should have something to do either with processor caches or conveyors. I am very curios how those experiments will behave on different chipsets, so feel free to comment here.
Also, if there is anyone more knowledgeable in hardware than me and he/she can explain this behavior it will be appreciated.
Until then there is a note I should make for myself - when estimating the algorithm complexity do not underestimate the processor optimizations. Sometimes, they seem to decrease/increase significantly the amortized speed of specific examples.
PS: I wonder have Topcoder guys specifically thought of such "processor breaking" examples?
However, I am pacifist, and especially in this troubled times I feel even worse about the title. I somehow feel I have guilt just because of the fact of being in an army (though imaginary).
How do you feel about changing the titles assigned in the system? I have thought about it and so far the best thing I could come up with is choosing titles from the computer game favorite of us all: "Heroes of might and magic 3" :P. We have plenty of mythological characters in the game and I am totally sure the creatures themselves are not copyrighted in any way. For example I would love to be Champion :P
Also if we go to this manner of giving titles, we will have at our disposal over a hundred titles! How cool is that?
I wonder when tourist will become Titan...
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<sstream>
#include<deque>
#include<math.h>
#include<cstring>
#include <bitset>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#define all(v) v.begin(),v.end()
#define mpair make_pair
using namespace std;
typedef long double ld;
const ld epsilon = 1e-9;
typedef long long ll;
vector<pair<int, int> > roads;
bool intersect(int i, int j)
{
int a = (roads[i].first - roads[j].first) * (roads[i].second - roads[j].first);
int b = (roads[i].first - roads[j].second) * (roads[i].second - roads[j].second);
int c = (roads[j].first - roads[i].first) * (roads[j].second - roads[i].first);
int d = (roads[j].first - roads[i].second) * (roads[j].second - roads[i].second);
if(a == 0 || b == 0 || c == 0 || d == 0)
return false;
if((a < 0) ^ (b < 0))
return true;
if((c < 0) ^ (d < 0))
return true;
}
int main()
{
//freopen("bobi.in", "r", stdin);
int n, m;
cin >> n >> m;
vector<int> vis(m, -1);
roads.resize(m);
for(int i = 0; i < m; i++)
cin >> roads[i].first >> roads[i].second;
queue<int> toProcess;
int cur;
for(int i = 0; i < m; i++)
{
if(vis[i] == -1)
{
toProcess.push(i);
vis[i] = 0;
while(!toProcess.empty())
{
cur= toProcess.front();
toProcess.pop();
for(int j = 0; j < m; j++)
{
if(j == cur)
continue;
if(intersect(cur, j))
{
if(vis[j] != -1)
{
if(vis[j] == vis[cur])
{
cout << "Impossible" << endl;
return 0;
}
}
else
{
vis[j] = !vis[cur];
toProcess.push(j);
}
}
}
}
}
}
for(int i = 0; i < m; i++)
if(vis[i] == 0)
cout << "i";
else
cout << "o";
cout << endl;
return 0;
}
