## 11167 - Monkeys in the Emei Mountain

Moderator: Board moderators

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am
Almost same challenge case:
5 2
1 0 1
2 2 4
2 2 4
1 0 2
2 0 4
0
Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Ah yes, thanks! I should have seen that.
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### Re: 11167 Monkeys in the Emei Mountain

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 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
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am
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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Ofcourse I'll send my code with PM. Also you can send me your code.
Noldorin
New poster
Posts: 4
Joined: Tue Feb 20, 2007 11:25 pm
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;
while(last != src){
matrix[last][previous[last]] += cap;
matrix[previous[last]][last] -= cap;
last = previous[last];
}
}else break;
}
}

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;
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] = (intervalLast[i]-intervalFirst[i])*fonts;
FOR(i,0,monkeys) matrix[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++;
}
}
``````
Fear is the mind killer.
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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;
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
New poster
Posts: 4
Joined: Tue Feb 20, 2007 11:25 pm
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.
Fear is the mind killer.
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
My max-flow is also slow, because I use stl vector to represent the graph.
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!
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
New poster
Posts: 4
Joined: Tue Feb 20, 2007 11:25 pm
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.
Fear is the mind killer.
Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### 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 ~!!! (

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;
const int MAX=400;
int used;
int inter,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;)
cosmin79
New poster
Posts: 11
Joined: Fri Aug 09, 2013 7:25 pm

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

{
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++)

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 = 1] = source; vis[source] = 1;
int i, j, node, x;
for (i = 1; i <= Q; 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] = 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])

for (node = dest; node != source; node = dad[node])
{
}

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

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.
7maAqB
New poster
Posts: 1
Joined: Thu Oct 17, 2013 7:03 am

### Re: 11167 - Monkeys in the Emei Mountain

It's .rar file that include test generator, test checker by rio and one test

thank rio.
mike21
New poster
Posts: 5
Joined: Sat Jun 15, 2013 3:25 am

### Re: 11167 - Monkeys in the Emei Mountain

How exactly can the intervals be contracted to 200 ?
flashion
New poster
Posts: 17
Joined: Thu Jul 24, 2014 10:29 pm

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