5 2
1 0 1
2 2 4
2 2 4
1 0 2
2 0 4
0
11167 - Monkeys in the Emei Mountain
Moderator: Board moderators
Re: 11167 Monkeys in the Emei Mountain
I took the same approach as you and used Ford-Fulkerson algorithm for max-flow, but got runtime 0.391. Did you apply max-flow only for the intervals where > m monkeys ?krijger wrote:I got this problem accepted using a max-flow approach. But that algorithm barely runs in time (6,5 seconds) and for that I had to use a pretty efficient max-flow algorithm.
So I wonder if someone used another approach. Maybe some kind of dp or greedy, or backtracking with pruning, etc. I tried to think of these kind of techniques, but I don't see how they can be used.
I also use Ford-Fulkerson (with dijkstra / priority_queue to find the maximal augmenting path), but I did apply max-flow for all intervals (so not only for the intervals containing more than m monkeys).
But even after implementing this optimalization, it still runs for 6.322 secs. Can you send me your implementation / can I send you my implementation?
But even after implementing this optimalization, it still runs for 6.322 secs. Can you send me your implementation / can I send you my implementation?
Hey, could you help me out with this problems, keeps giving me WA, not that i'm not used to, but i'm unable to find the flaw in the code.
I know that is really bad looking, i hope the error it's more obvious to you than has been for me.
Thanks!
I know that is really bad looking, i hope the error it's more obvious to you than has been for me.
Thanks!
Code: Select all
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <utility>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<_b;++i)
#define sz(v) ((int)(v).size())
#define pb push_back
#define FORSZ(i,a,v) FOR(i,a,sz(v))
#define REPSZ(i,v) FORSZ(i,0,v)
inline int maxflow(VVI &matrix, int src, int dest){
int cap[sz(matrix)];
int in[sz(matrix)];
int previous[sz(matrix)];
int total = 0;
while(true){
int last = dest;
memset(cap, 0, sizeof(cap));
memset(in, 0, sizeof(in));
queue<int> Q;
Q.push(src);
cap[src] = 999999;
int done = 0, node;
while(sz(Q) > 0){
node = Q.front();
Q.pop();
if(node == dest){ done = 1; break;}
else{
FOR(i, 0, sz(matrix[node])){
int obj = matrix[node][i];
if(cap[i] < min(cap[node], obj)){
cap[i] = min(cap[node], obj);
previous[i] = node;
if(in[i] == 0){
Q.push(i);
in[i] = 1;
if(node == 1) break;
//Only one at a time, if monkey A can't drink, we ahven't to test whit monkey A+1
}
}
}
}
}
if(done){
total += cap[0];
while(last != src){
matrix[last][previous[last]] += cap[0];
matrix[previous[last]][last] -= cap[0];
last = previous[last];
}
}else break;
}
return total;
}
int main(){
int monkeys, fonts, cases = 1;
while(cin >> monkeys){
if(monkeys == 0) return 0;
cin >> fonts;
int need[monkeys];
int start[monkeys];
int end[monkeys];
int total = 0, minim = 9999999, maxim = 0;
FOR(i, 0 , monkeys){
cin >> need[i] >> start[i] >> end[i];
total += need[i];
if(start[i] < minim) minim = start[i];
if(maxim < end[i]) maxim = end[i];
}
//Only making sure it's water for them all
if(total > (maxim - minim) * fonts){
cout << "Case " << cases << ": No" <<endl;
cases++;
continue;
}
//Signaling where to break the interval
vector<int> placesToBreak(2*monkeys);
FOR(i,0,monkeys){
placesToBreak[i] = start[i];
placesToBreak[monkeys+i] = end[i];
}
sort(placesToBreak.begin(), placesToBreak.end());
int intervalFirst[monkeys + 2 + sz(placesToBreak)];
int intervalLast[monkeys + 2 + sz(placesToBreak)];
int firstEmpty = monkeys + 2;
intervalFirst[firstEmpty] = placesToBreak[0];
FOR(i, 1, 2*monkeys){
if( placesToBreak[i] != placesToBreak[i-1]){
intervalLast[firstEmpty] = placesToBreak[i];
firstEmpty++;
intervalFirst[firstEmpty] = placesToBreak[i];
}
}
//Breaks saved
//Creating the matrix and placing capacities
//From monkey to interval
//From interval to water
//From source to monkeys (their thirstyness?)
VVI matrix(firstEmpty, VI(firstEmpty,0));
FOR(i, 0, monkeys)
FOR(j, monkeys+1, firstEmpty)
if(start[i] <= intervalFirst[j] && end[i] > intervalFirst[j])
matrix[i+2][j] = intervalLast[j] - intervalFirst[j];
FOR(i,monkeys+2,firstEmpty) matrix[i][0] = (intervalLast[i]-intervalFirst[i])*fonts;
FOR(i,0,monkeys) matrix[1][i+2] = need[i];
//Calling the maxflow
int bo = maxflow(matrix, 1, 0);
if(bo != total) cout << "Case " << cases << ": No" <<endl;
else{
cout << "Case " << cases << ": Yes" << endl;
VI toPrint;
int firstToUse[sz(matrix)];
FOR(j, monkeys+2, sz(matrix)){
firstToUse[j] = intervalFirst[j];
}
FOR(i, 0, monkeys){
toPrint.clear();
FOR(j, monkeys+2, sz(matrix)){
int aux = intervalLast[j] - intervalFirst[j];
if(start[i] <= intervalFirst[j] && end[i] > intervalFirst[j] && matrix[i+2][j] < aux){
int sobren = firstToUse[j] - intervalFirst[j] - matrix[i+2][j];
if( sobren <= 0 ){
//See if one interval follows the last
if(toPrint.size() == 0 || toPrint[sz(toPrint)-1] != firstToUse[j]){
toPrint.pb(firstToUse[j]);
toPrint.pb(firstToUse[j] + (intervalLast[j]-intervalFirst[j]) - matrix[i+2][j]);
firstToUse[j] = toPrint[sz(toPrint)-1];
if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
}else{
//Puting this interval with the last
toPrint[sz(toPrint)-1] = firstToUse[j] + (intervalLast[j]-intervalFirst[j]) - matrix[i+2][j];
firstToUse[j] = toPrint[sz(toPrint)-1];
if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
}
}
else{
if(sz(toPrint)==0 || toPrint[sz(toPrint)-1]!=intervalFirst[j]){
toPrint.pb(intervalFirst[j]);
toPrint.pb(intervalFirst[j] + sobren);
toPrint.pb(firstToUse[j]);
toPrint.pb(intervalLast[j]);
firstToUse[j] = toPrint[sz(toPrint)-3];
if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
}else{
//Puting this interval with the last
toPrint[sz(toPrint)-1] = intervalFirst[j] + sobren;
toPrint.pb(firstToUse[j]);
toPrint.pb(intervalLast[j]);
firstToUse[j] = toPrint[sz(toPrint)-3];
if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
}
}
}
}
cout << sz(toPrint)/2;
FOR(a,0,sz(toPrint)){
cout << " ("<<toPrint[a]<<","<<toPrint[a+1]<<")";
a++;
}cout<<endl;
}
}
cases++;
}
}
Code: Select all
Fear is the mind killer.
Heres a simple corrector program I used to verify my program.Ofcourse, it only verfies the "Yes" answers. If there is a invalid output, it simply asserts.
Code: Select all
/* Lazy Correct Program */
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
typedef struct {
int v, a, b;
} Monkey;
#define MAX_MONKEY 128
static Monkey mon[MAX_MONKEY];
int main()
{
FILE *in, *out;
in = fopen("in", "r");
out = fopen("out", "r");
int N, M, i, j, caseno = 1;
char buf[64];
while (fscanf(in, "%d", &N) && N) {
fscanf(in, "%d", &M);
for (i = 0; i < N; ++i)
fscanf(in, "%d %d %d", &mon[i].v, &mon[i].a, &mon[i].b);
printf("Case %d:\n", caseno++);
fflush(stdout);
fgets(buf, sizeof(buf), out);
if (buf[strlen(buf)-2] == 'o') {
printf("You answered \"No\". I can't verify.\n");
} else {
int *count = (int*)calloc(sizeof(int), 1024);
for (i = 0; i < N; ++i) {
int k, v;
fscanf(out, "%d", &k);
v = 0;
int tmp = mon[i].a - 1;
while ( k-- ) {
int a, b;
fscanf(out, " (%d,%d)", &a, &b);
assert(a < b);
assert(mon[i].a <= a && b <= mon[i].b);
assert(tmp < a);
tmp = b;
v += b-a;
for (; a < b; ++a)
assert(++count[a] <= M);
}
assert(v == mon[i].v);
}
free( count );
fgets(buf, sizeof(buf), out);
printf("\"Yes\" is yes!!\n");
}
}
}
My max-flow is also slow, because I use stl vector to represent the graph.
Check your max-flow. There is also a bug with the index somewhere when you construct the graph. Also, I think how you compute what interval to print is wrong.
Below is what I do to print:
I won't say anything else about my code or I'll be spoiling it.
Did your code handle cases when a monkey doesn't need to drink (v=0)?Noldorin wrote:Hey, could you help me out with this problems, keeps giving me WA, not that i'm not used to, but i'm unable to find the flaw in the code.
I know that is really bad looking, i hope the error it's more obvious to you than has been for me.
Thanks!
Check your max-flow. There is also a bug with the index somewhere when you construct the graph. Also, I think how you compute what interval to print is wrong.
Below is what I do to print:
Code: Select all
REP(j,I-1) B[j]=ix[j];
REP(i,n) {
vector<pair<int,int> > sol;
REP(j,I-1) {
int x = F[i][n+j];
if(!x) continue;
int start=B[j],end=start+x,len=ix[j+1]-ix[j];
B[j]=end;
if(end<=ix[j+1])
sol.push_back(make_pair(start,end));
else {
sol.push_back(make_pair(start,ix[j+1]));
sol.push_back(make_pair(ix[j],end-len)), B[j]-=len;
}
if(B[j]==ix[j+1]) B[j]=ix[j];
}
sort(sol.begin(),sol.end());
vector<pair<int,int> > r;
REP(j,size(sol)) {
if(size(r) && r.back().second==sol[j].first)
r.back().second = sol[j].second;
else r.push_back(sol[j]);
}
cout << r.size();
REP(j,size(r))
cout << " ("<<r[j].first<<','<<r[j].second<<')';
cout << endl;
}
Thank you very much, finally accepted.
I had already corrected the output, the code up here has severeal glitches about intervals like (a,b)(b,c) and saving the instant of time in the interval when a monkey can enter in, but the error left was this small error on building the graph, and the most annoying part is that this error doesn't breaks the code on the public tests or the large input/output posted before.
I had already corrected the output, the code up here has severeal glitches about intervals like (a,b)(b,c) and saving the instant of time in the interval when a monkey can enter in, but the error left was this small error on building the graph, and the most annoying part is that this error doesn't breaks the code on the public tests or the large input/output posted before.
Fear is the mind killer.
Re: 11167 - Monkeys in the Emei Mountain
Hi,Experts ...
i used FordFolkerson-Edmond Krap maxFlow Algorithm ...
i'm getting continuously WA ... Why!!!!!
check every thing 100 of thimes ....
( i'm going crazy ...(
can somebody help me ...
or if solved by this Method PM his/her code ...
I, have got AC on Problem 11358 (The same Without Printing ... ) so i should have problem in Printing ... but What ~!!!(
thnaks in advance ...
i used FordFolkerson-Edmond Krap maxFlow Algorithm ...
i'm getting continuously WA ... Why!!!!!
check every thing 100 of thimes ....
( i'm going crazy ...(can somebody help me ...
or if solved by this Method PM his/her code ...
I, have got AC on Problem 11358 (The same Without Printing ... ) so i should have problem in Printing ... but What ~!!!
(thnaks in advance ...
Code: Select all
/*start 5.30
*/
#include<iostream>
#include<algorithm>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;++i)
struct Monkey{
int v,s,e;
Monkey(){};
}in[110];
const int MAX=400;
int cap[MAX][MAX],fnet[MAX][MAX],mark[MAX],parent[MAX],adj[MAX],deg[MAX],MA=1,out[MAX],outC=0;
int used[50010];
int inter[210],monkeyC;
#define Mon(n) (n+2)
#define Int(n) (2+monkeyC+n)
#define NN MAX // the maximum number of vertices[0,n),[i][j] = i->j edge
int q[NN], qf, qb, prev[NN];// BFS – Q
int FordFulkerson(int s, int t , int n){
memset( fnet, 0, sizeof( fnet ) );// init the flow network
int flow = 0;
while( true ){
memset( prev, -1, sizeof( prev ) );// find an augmenting path
qf = qb = 0;
prev[q[qb++] = s] = -2; //Enqueue
while( qb > qf && prev[t] == -1 )//BFS //Dequeue
for( int u = q[qf++], v = 0; v < n; v++ )
if( prev[v] == -1 && fnet[u][v] < cap[u][v] )
prev[q[qb++] = v] = u;
if( prev[t] == -1 ) break;// see if we're done
int bot = 0x7FFFFFFF;
for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] ) // get the bottleneck capacity
bot = min(bot,cap[u][v]-fnet[u][v]);
for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] )// update the flow network
fnet[u][v] += bot,fnet[v][u] -= bot;
flow += bot;
}
return flow;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,m,ca=1;
while(scanf("%d",&n)>0 && n ){
scanf("%d",&m);
monkeyC=n;
FOR(i,n)scanf("%d%d%d",&in[i].v,&in[i].s,&in[i].e );
FOR(i,n) inter[2*i]=in[i].s ,inter[2*i+1]=in[i].e;
sort(inter,inter+2*n);
memset(cap,0,sizeof(cap) );
int src=0;
int sink=1;
//make Graph;
int Sum=0;
FOR(i,n) Sum+=in[i].v;
FOR(i,n) cap[src][Mon(i)]=in[i].v;
FOR(i,n){//monkey
FOR(j,2*n-1){//interval [ .. )
if( in[i].s<=inter[j] && inter[j]<in[i].e ){
cap[ Mon(i) ][ Int(j) ]= inter[j+1]-inter[j];
// printf("[%d][%d] = %d %d %d\n",Mon(i) , Int(j) ,inter[j],inter[j+1], inter[j+1]-inter[j] );
}
}
}
memset(used,0,sizeof(used) );
FOR(i,2*n-1) cap[Int(i) ][sink]=(inter[i+1]-inter[i])*m;
int res=FordFulkerson(src,sink,Int(2*n) );
//printf("%d\n",res);
if(res==Sum){
printf("Case %d: Yes\n",ca++);
FOR(i,n){
//printf("moneyk %d : ",i);
outC=0;
FOR(j,2*n-1){
if( fnet[ Mon(i)][ Int(j) ]>0 ){
int s=inter[j];
while( used[s]>=m)s++;
FOR(t,fnet[ Mon(i)][Int(j)] ){
//printf(">>%d\n",s);
used[s]++;
out[outC++]=s++;
if(outC>1 && out[outC-1]==out[outC-2])outC-=2;
out[outC++]=s;
}
}
}
//FOR(i,outC)printf("%d ",out[i] );
printf("%d",outC/2);
FOR(i,outC)printf(" (%d,%d)",out[i],out[i+1] ),++i;
putchar('\n');
}
}
else
printf("Case %d: No\n",ca++);
}
return 0;
}
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)
Re: 11167 - Monkeys in the Emei Mountain
Can anyone help me figure out why do I get WA?? It works on every test I try. Can anyone take a look at my output formatting? Maybe there's a mistake there I can't see... Thank you in advance!
Code: Select all
#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#define NMAX 105
#define HMAX 405
#define LMAX 505
#define INF 1000000000
#define pb push_back
#define mp make_pair
#define vi vector <int>
#define pii pair <int, int>
#define x first
#define y second
using namespace std;
int n, m, no, val[HMAX], F[LMAX][LMAX], C[LMAX][LMAX];
int source, dest, dad[LMAX], flow, expected, Q[LMAX];
vi G[LMAX], I;
vector <pii> sol;
pair <int, pii> info[NMAX];
bitset <LMAX> vis;
void add_edge(int from, int to, int cap)
{
G[from].pb(to); C[from][to] = cap;
G[to].pb(from);
}
void read()
{
int i, j, x, y;
for (i = 1; i <= n; i++)
{
scanf("%d%d%d", &info[i].x, &info[i].y.x, &info[i].y.y);
expected += info[i].x; info[i].y.y--;
I.pb(info[i].y.x); I.pb(info[i].y.y);
}
sort(I.begin(), I.end());
I.erase(unique(I.begin(), I.end()), I.end());
source = 0; no = I.size();
for (i = 0; i < no - 1; i++)
{
val[2 * i + 1] = 1;
val[2 * i + 2] = I[i + 1] - I[i] - 1;
}
val[2 * no - 1] = 1;
for (i = 1; i <= 2 * no; i++)
add_edge(source, i, val[i] * m);
dest = 2 * no + n + 1;
for (i = 1; i <= n; i++)
{
x = lower_bound(I.begin(), I.end(), info[i].y.x) - I.begin();
y = lower_bound(I.begin(), I.end(), info[i].y.y) - I.begin();
info[i].y = mp(2 * x + 1, 2 * y + 1);
for (j = x; j < y; j++)
{
add_edge(2 * j + 1, 2 * no + i, val[2 * j + 1]);
add_edge(2 * j + 2, 2 * no + i, val[2 * j + 2]);
}
add_edge(2 * y + 1, 2 * no + i, val[2 * y + 1]);
add_edge(2 * no + i, dest, info[i].x);
}
}
int BF()
{
vis.reset();
Q[Q[0] = 1] = source; vis[source] = 1;
int i, j, node, x;
for (i = 1; i <= Q[0]; i++)
{
node = Q[i];
for (j = 0; j < (int)G[node].size(); j++)
{
x = G[node][j];
if (F[node][x] < C[node][x] && !vis[x])
{
Q[++Q[0]] = x; dad[x] = node; vis[x] = 1;
if (x == dest)
return 1;
}
}
}
return vis[dest];
}
void max_flow()
{
int node, fmin;
while (BF())
{
fmin = INF;
for (node = dest; node != source; node = dad[node])
fmin = min(fmin, C[dad[node]][node] - F[dad[node]][node]);
for (node = dest; node != source; node = dad[node])
{
F[dad[node]][node] += fmin;
F[node][dad[node]] -= fmin;
}
flow += fmin;
}
}
void recons()
{
int i, j, x, y;
for (i = 1; i <= n; i++)
{
for (j = info[i].y.x; j <= info[i].y.y; j++)
if (F[j][i + 2 * no])
{
x = I[(j - 1) / 2]; y = x + F[j][i + 2 * no];
if (!(j & 1))
x++, y++;
if (sol.size() && sol[sol.size() - 1].y == x)
sol[sol.size() - 1].y = y;
else
sol.pb(mp(x, y));
}
printf("%d", sol.size());
for (j = 0; j < (int)sol.size(); j++)
printf(" (%d,%d)", sol[j].x, sol[j].y);
printf("\n");
sol.clear();
}
}
void clear_data()
{
I.clear();
int i;
for (i = source; i <= dest; i++)
G[i].clear();
memset(F, 0, sizeof(F));
memset(C, 0, sizeof(C));
expected = flow = 0;
memset(val, 0, sizeof(val));
}
int main()
{
//freopen("input", "r", stdin);
int test_no = 0;
while (scanf("%d%d", &n, &m), n)
{
test_no++;
read();
max_flow();
printf("Case %d: ", test_no);
if (flow == expected)
{
printf("Yes\n");
recons();
}
else
printf("No\n");
clear_data();
}
return 0;
}
Last edited by cosmin79 on Wed Sep 25, 2013 3:25 am, edited 1 time in total.
Re: 11167 - Monkeys in the Emei Mountain
It's .rar file that include test generator, test checker by rio and one test
4shared link -> http://goo.gl/5mHu1H
gogoshare link -> http://goo.gl/xY9m0D
thank rio.
4shared link -> http://goo.gl/5mHu1H
gogoshare link -> http://goo.gl/xY9m0D
thank rio.
Re: 11167 - Monkeys in the Emei Mountain
How exactly can the intervals be contracted to 200 ?
Re: 11167 - Monkeys in the Emei Mountain
Hello guys,
My approach to this problem is:
- created bipartite graph (monkeys, time from 0 to 50000)
- link monkeys to time vertexes, when they can drink (capacity 1)
- link source to monkeys (capacity: thirstyness of monkey)
- link time vertexes to sink (capacity: m)
- run maxflow with Dinic
and I got TLE which I expected, but I have no idea how to make it in another way.
Any help would be appreciated.
// EDIT: I "compressed" time intervals to O(n), but I'm getting WA :/
My approach to this problem is:
- created bipartite graph (monkeys, time from 0 to 50000)
- link monkeys to time vertexes, when they can drink (capacity 1)
- link source to monkeys (capacity: thirstyness of monkey)
- link time vertexes to sink (capacity: m)
- run maxflow with Dinic
and I got TLE which I expected, but I have no idea how to make it in another way.
Any help would be appreciated.
// EDIT: I "compressed" time intervals to O(n), but I'm getting WA :/