11167 - Monkeys in the Emei Mountain

[krijger]

Almost same challenge case:

5 2
1 0 1
2 2 4
2 2 4
1 0 2
2 0 4
0

[Per]

Ah yes, thanks! I should have seen that.

[rio]

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 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]

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?

[rio]

Ofcourse
I'll send my code with PM. Also you can send me your code.

[Noldorin]

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!

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

[rio]

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");
      }
   }
}

[Noldorin]

Thank you very much, I've corrected some output errors so my code passes your test for the long input posted before, but still WA. I think I will give it up.

[sclo]

My max-flow is also slow, because I use stl vector to represent the graph.

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!

Did your code handle cases when a monkey doesn't need to drink (v=0)?

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

I won't say anything else about my code or I'll be spoiling it.

[Noldorin]

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.

[Angeh]

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

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

[cosmin79]

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

[7maAqB]

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.

[mike21]

How exactly can the intervals be contracted to 200 ?

[flashion]

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 :/