10779 - Collectors Problem

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

10779 - Collectors Problem

Post by emotional blind » Mon Sep 18, 2006 6:39 pm

I tried this one with maximum flow.
At first I create a capacity graph cap[][] and then call maxFlow function?

Here is my method to create capacity graph.

Code: Select all

#define SIZE 100
int cap[SIZE][SIZE];

int maxFlow( int numberOfVert, int source, int destination ){
........

return flow;
}

int main()
{
    
	int T, nPerson, nSticker, nst;
	int i, j, k, a, u;
        int frq[110], frq1[110];
	//freopen("10779.in","r",stdin);
	cin>>T;
	for(u=1;u<=T;u++){
		cin>>nPerson>>nSticker;
		memset( cap, 0, sizeof( cap ) );
		for(i=1;i<=nPerson;i++){
			cin>>nst;
			if(i==1){
				for(j=1;j<=nSticker;j++)frq1[j]=0;

				for(j=1;j<=nst;j++){
					cin>>a;
					cap[0][a]++;
					frq1[a]++;
				}
			}
			else{
				for(j=1;j<=nSticker;j++)frq[j]=0;

				for(j=1;j<=nst;j++){
					cin>>a;
					frq[a]++;
				}

				for(j=1;j<=nSticker;j++)if(frq[j]>1)for(k=1;k<=nSticker;k++)if(!frq[k])cap[k][j]++;
			}
		}
		for(j=1;j<=nSticker;j++)cap[j][nSticker+1]=1;
		cout<<"Case #"<<u<<": "<<maxFlow(nSticker+2, 0, nSticker+1 )<<endl; 
	}
    return 0;
}
Is there any problem in my of capacity graph creation ?
I am getting Wrong Answer

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Sep 18, 2006 10:43 pm

I think that your program won't work in the following test case:

Code: Select all

1
4 6
12  4 4 4 4 5 5 5 5 6 6 6 6
2   1 1
20  2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6
20  2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6
Correct output should be:

Code: Select all

Case #1: 4
In this scenario, only person #2 is willing to buy Bob's tickets, and he can sell only one ticket of type 1.
But your program, as I understand it, will try to buy several tickets from him.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Wed Sep 20, 2006 7:46 am

Thanks mf,
I got the point I think!
I changed my code but again Wrong Answer

Code: Select all


#define SIZE 200 
int cap[SIZE][SIZE]; 

int maxFlow( int numberOfVert, int source, int destination ){ 
........ 

return flow; 
} 


int main()
{
    
	int T, nPerson, nSticker, nst;
	int i, j, k, a, u, total;
    int frq[110], frq1[110];
	//freopen("10779.in","r",stdin);
	cin>>T;
	for(u=1;u<=T;u++){
		cin>>nPerson>>nSticker;
		memset( cap, 0, sizeof( cap ) );
		total=nSticker+1;
		for(i=1;i<=nPerson;i++){
			cin>>nst;
			if(i==1){
				for(j=1;j<=nSticker;j++)frq1[j]=0;

				for(j=1;j<=nst;j++){
					cin>>a;
					cap[0][a]++;
					frq1[a]++;
				}
			}
			else{
				for(j=1;j<=nSticker;j++)frq[j]=0;

				for(j=1;j<=nst;j++){
					cin>>a;
					frq[a]++;
				}

				for(j=1;j<=nSticker;j++){
					if(frq[j]>1){
						for(k=1;k<=nSticker;k++){
							if(!frq[k])cap[k][nSticker+j]++;
						}
						cap[nSticker+j][j]+=(frq[j]-1);
						//total++;
					}
				}
			}
		}
		for(j=1;j<=nSticker;j++)cap[j][2*nSticker+1]=1;
		cout<<"Case #"<<u<<": "<<maxFlow(2*nSticker+2, 0, 2*nSticker+1 )<<endl;
	}
    return 0;
}
I need hint, plz help.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Sep 20, 2006 11:51 am

I believe it won't work on this test case. Can't say for sure, unless you post your complete code, so that I could compile it.

Code: Select all

1
5 7
12  4 4 4 4 5 5 5 5 6 6 6 6
2   1 1
20  2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6
20  2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6
24  1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6
Correct output:

Code: Select all

Case #1: 4

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Wed Sep 20, 2006 6:13 pm

mf: I have sent you my code

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Sep 21, 2006 11:02 am

Here are a few test cases:

Code: Select all

12

2 4
3 1 1 1
4 3 3 4 4

7 5
4 5 4 5 5
46 4 1 1 4 1 4 5 4 5 1 2 2 5 5 5 2 3 5 5 2 5 5 5 5 1 5 1 1 2 3 3 4 5 1 1 4 2 3 5 2 2 5 5 4 4 3
41 2 5 3 5 3 5 1 3 1 5 4 5 5 3 5 1 2 3 2 1 1 3 4 5 1 1 4 3 2 2 2 2 3 5 2 3 1 3 3 1 4
12 1 3 4 3 2 3 1 1 2 4 2 2
31 5 5 3 2 2 1 3 4 5 4 1 3 5 4 3 2 3 5 5 1 4 3 3 2 4 1 3 5 3 3 4
19 5 1 1 3 4 1 2 2 1 5 1 4 1 4 1 3 1 3 3
44 3 2 2 3 5 1 1 5 3 2 2 4 3 2 3 1 5 5 2 2 4 2 1 4 1 5 5 5 1 4 5 5 4 3 1 3 4 5 1 2 4 4 5 4

7 20
19 6 8 13 5 10 6 5 10 11 10 20 19 19 9 15 5 4 18 2
18 1 20 6 18 10 12 8 14 16 11 3 4 3 7 10 3 11 15
12 7 18 20 4 17 8 7 20 11 2 6 5
16 16 9 12 20 16 3 19 17 9 7 18 7 13 4 10 17
22 11 20 7 1 9 6 20 2 11 19 7 9 19 18 20 6 10 14 14 17 6 10
13 9 10 5 2 1 12 8 8 1 5 5 14 6
32 20 12 11 4 18 20 10 9 4 5 3 16 3 3 18 8 3 7 14 17 10 19 9 17 11 2 17 12 4 1 1 20

7 24
14 5 23 13 16 14 5 5 3 14 16 22 22 3 15
11 9 8 2 10 8 22 5 10 24 15 18
4 17 21 6 14
50 5 17 10 24 18 13 4 13 2 2 6 4 17 7 6 1 15 23 3 13 3 7 4 23 19 20 4 2 19 22 14 13 9 3 5 11 3 11 22 5 22 17 19 14 13 14 8 2 10 5
50 1 16 6 17 6 23 24 21 21 1 21 19 19 8 2 13 15 23 20 4 23 18 11 7 24 2 7 6 22 13 17 7 17 2 17 10 11 7 4 1 22 24 2 22 18 21 23 1 13 6
50 13 17 15 24 2 5 18 17 23 20 19 6 23 20 18 21 7 23 24 9 22 22 23 10 17 13 24 7 20 18 4 14 2 18 12 9 18 24 5 20 5 5 13 16 20 13 3 16 23 22
33 13 8 7 12 6 9 11 13 24 21 16 20 15 17 15 4 22 15 1 16 1 17 16 22 21 24 10 4 19 5 17 10 22

9 14
20 13 10 2 12 4 9 8 4 9 14 9 12 5 9 2 14 5 14 13 5
49 12 13 10 9 2 10 14 2 13 6 4 1 6 12 1 7 4 7 7 5 12 12 9 7 8 1 14 5 11 2 3 13 12 7 4 4 7 5 11 4 12 1 11 1 10 3 8 9 4
30 9 1 5 8 10 7 3 14 6 10 7 4 5 4 12 11 5 3 11 1 3 1 12 2 4 10 7 11 3 11
46 14 13 14 1 10 13 14 11 14 7 8 13 14 4 6 4 8 2 3 3 9 8 12 2 4 11 14 6 5 2 8 10 11 14 5 9 4 3 3 9 11 11 3 12 5 13
10 3 1 13 7 9 2 11 13 5 2
43 7 12 8 3 9 13 9 9 2 8 8 4 5 4 3 2 10 2 5 14 11 11 7 4 5 4 5 10 5 14 12 3 14 10 9 10 11 10 9 12 13 5 2
21 4 10 13 2 13 13 14 3 12 7 7 8 1 4 7 3 2 13 13 4 5
37 12 8 5 10 2 14 1 7 4 8 14 14 12 6 6 4 6 12 7 11 8 3 12 14 7 6 4 4 1 4 6 4 11 3 13 1 13
39 9 3 9 3 12 13 7 11 14 10 14 7 4 2 7 6 6 1 12 6 9 11 7 9 10 5 2 10 4 12 13 9 14 4 8 9 10 4 11

7 18
21 2 2 13 18 11 1 8 8 1 2 17 8 17 13 3 14 17 11 10 13 18
3 6 1 1
44 14 1 17 10 1 6 2 16 5 15 11 2 18 9 10 16 8 11 11 18 11 12 2 12 16 17 5 11 11 15 2 14 17 18 6 16 9 8 4 4 5 3 5 3
4 13 16 13 6
22 7 4 11 9 2 6 5 6 17 15 4 12 9 11 5 5 7 10 14 16 13 17
15 4 2 12 1 11 18 11 7 14 3 15 9 7 18 5
27 11 13 8 1 5 18 13 1 14 2 7 6 14 14 18 7 16 7 17 1 5 2 15 11 9 1 12

8 25
21 25 6 7 9 15 15 2 21 22 19 6 6 1 13 10 21 12 12 18 25 5
0
35 3 13 8 6 19 19 17 17 12 21 4 19 25 23 21 11 4 23 17 19 24 24 24 3 18 13 23 17 24 5 22 5 5 24 7
32 6 1 23 10 20 10 20 25 11 16 1 7 7 15 18 19 19 11 14 18 4 10 11 15 2 19 16 22 24 6 13 13
1 20
16 8 3 3 5 9 4 23 7 9 7 18 20 8 22 25 3
1 12
10 15 25 2 4 16 7 6 22 10 9

10 24
24 7 5 1 17 14 6 23 19 6 13 14 3 1 8 20 16 11 24 1 2 15 20 13 7
36 21 7 10 2 23 7 21 1 21 1 18 20 20 9 23 20 4 14 6 12 4 21 4 18 23 17 5 3 21 12 1 20 4 20 6 20
46 18 14 15 23 11 1 9 13 9 2 11 19 17 16 17 24 24 8 9 21 10 2 14 10 20 3 22 17 3 1 18 3 18 13 3 14 10 22 17 7 15 22 5 1 21 15
11 22 2 22 19 7 5 12 5 6 24 17
11 3 23 18 5 12 6 9 12 21 22 11
3 5 21 19
35 1 13 24 9 20 24 23 15 7 9 4 19 2 22 18 9 24 9 9 12 4 15 18 5 3 2 10 5 4 17 23 17 16 4 7
32 11 11 7 8 3 6 7 5 3 3 22 20 15 1 24 11 10 13 22 20 19 12 17 12 24 17 22 17 3 10 22 22
16 14 14 18 19 12 7 21 1 19 15 12 6 18 23 11 23
19 19 16 15 7 11 18 10 1 15 20 24 24 8 15 7 18 10 19 16

10 20
18 16 4 12 8 12 8 8 2 8 4 4 14 7 11 5 9 4 7
31 3 11 1 10 5 8 15 4 17 17 5 7 9 4 15 11 15 11 6 12 10 16 12 17 2 17 16 18 7 18 6
29 17 17 11 18 11 13 9 4 4 16 7 1 18 13 4 14 11 11 6 7 9 17 6 3 8 2 6 12 8
24 3 15 9 9 15 10 20 1 10 5 20 13 14 16 10 7 20 6 15 9 9 8 3 3
0
31 14 19 19 14 16 6 20 14 2 18 18 17 12 10 20 11 15 10 16 9 3 14 7 2 1 10 9 17 17 16 9
7 9 13 4 18 9 1 8
11 12 11 1 4 10 2 3 16 6 15 2
16 8 15 19 20 2 4 19 12 5 3 18 12 3 2 6 13
34 6 11 14 6 9 14 7 18 13 12 13 9 18 16 16 7 18 16 4 11 2 9 2 11 15 1 20 8 19 1 6 5 6 14

10 18
21 4 11 18 4 5 8 5 4 4 14 8 14 6 16 4 8 7 14 2 11 7
42 7 6 14 18 7 11 7 1 2 12 13 4 11 16 16 6 17 3 9 15 3 16 5 10 2 8 12 12 10 14 8 13 10 18 13 4 6 14 6 14 11 11
28 13 2 3 3 1 4 14 12 3 9 13 6 6 13 9 18 6 12 18 7 3 9 15 15 4 14 4 17
33 10 14 7 4 2 8 13 11 3 7 9 18 13 5 1 14 17 3 18 7 15 16 5 18 11 13 13 1 14 18 2 17 8
31 11 16 18 13 10 4 16 3 8 6 3 11 15 16 18 16 8 16 5 12 9 8 4 12 7 10 10 18 4 4 9
35 13 16 17 9 6 14 12 2 8 5 6 2 4 2 3 3 2 9 6 4 4 4 3 14 4 7 3 15 15 14 9 7 8 1 2
46 18 5 18 17 7 14 15 7 1 8 8 8 13 4 15 15 10 5 8 8 3 5 12 16 9 15 5 17 12 13 3 7 14 14 9 10 8 4 9 9 16 4 12 11 11 6
44 1 15 17 17 16 11 18 16 9 16 4 1 6 12 2 4 1 3 17 12 8 5 15 17 5 8 13 4 6 1 5 13 1 10 3 11 17 3 17 14 13 13 15 3
4 16 10 13 9
17 13 11 16 12 2 4 11 6 5 14 14 13 1 7 11 8 9

8 20
17 5 14 19 10 13 20 11 13 7 15 7 13 6 15 17 13 14
44 7 6 1 16 15 6 17 9 3 20 4 5 1 3 10 15 3 12 15 2 16 20 3 7 18 6 20 18 1 17 1 18 6 5 3 17 18 16 1 16 9 1 10 8
25 1 19 7 10 4 13 12 18 8 18 2 18 12 14 7 7 13 1 10 5 8 17 16 1 14
40 17 7 13 5 7 19 1 1 9 17 19 9 10 7 7 16 14 11 9 18 6 14 9 1 19 3 2 9 13 20 14 17 10 16 18 10 5 18 13 1
33 20 17 4 4 14 5 6 1 16 6 15 14 8 17 19 15 13 1 6 10 4 6 8 20 9 16 12 20 19 8 14 2 11
45 7 6 6 10 4 10 3 5 6 15 10 4 2 13 7 1 9 1 16 13 2 20 2 11 8 6 14 18 13 8 18 10 16 6 13 10 2 10 11 19 7 17 11 7 1
1 7
29 19 4 12 17 15 5 3 12 3 16 13 6 13 18 19 12 14 8 3 19 8 5 7 11 15 1 19 19 6

5 25
29 12 21 20 2 21 6 16 23 2 19 9 17 5 6 20 22 16 6 23 8 10 6 20 15 18 5 3 17 19
35 13 18 18 16 13 19 22 14 11 5 1 21 25 11 4 10 4 17 15 19 8 10 20 7 4 17 10 5 16 10 22 19 23 7 9
23 8 21 21 12 2 9 6 15 21 7 15 18 1 22 11 21 12 20 1 6 21 20 6
33 7 9 7 16 4 19 9 15 4 24 15 6 2 15 7 14 17 21 6 17 20 9 9 5 7 18 21 19 11 24 9 14 20
28 12 11 24 6 17 16 16 23 20 4 19 6 3 3 20 22 1 10 10 4 5 8 21 9 8 12 22 14
Output of my accepted program:

Code: Select all

Case #1: 2
Case #2: 3
Case #3: 18
Case #4: 12
Case #5: 12
Case #6: 15
Case #7: 19
Case #8: 23
Case #9: 16
Case #10: 15
Case #11: 15
Case #12: 23

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Sep 21, 2006 7:31 pm

Thanks a Lot mf.
I got ACCEPTED at last.
Your input/output helped me a lot.

kevinufo
New poster
Posts: 2
Joined: Mon Oct 08, 2007 6:16 pm

Post by kevinufo » Sat Jul 18, 2009 3:43 pm

Could anyone provide some hints about this problem?
As far as I know, this problem can be solved by max-flow algorithm,
but I can't figure out how to map the problem to the corresponding graph.
I think any explanation or example will help.

Thanks in advance.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10779 - Collector's Problem

Post by mf » Wed Jul 22, 2009 10:44 pm

If I recall correctly, here's how to solve this problem.

The trick is to build a graph, such that every path in it will correspond to a series of exchanges of duplicate stickers, starting with Bob giving away one of his duplicates, and ending with him receiving a new sticker.

The graph has n subgraphs, one for each person (including Bob).

i-th subgraph has the following vertices:
  • m input vertices In(i, j) and m output vertices Out(i, j), where j=1..m (j denotes sticker's type)
  • a source s(i) and a sink t(i)
And the edges are:
  • from In(i, j) to t(i) of capacity 1 for all j's such that i-th person doesn't yet have j-th sticker
    (a flow on this edge means that i-th person decides to buy j-th sticker)
  • from t(i) to s(i) of infinite capacity, if i > 1.
    (if i=1, s(1) and t(1) will be source and sink; if i>1, we actually need only one vertex here, but let's keep two just for consistency)
  • from s(i) to Out(i, j) of capacity equal to the number of duplicate stickers of type j that i-th person has;
    (each unit of flow here corresponds to a sale of j-th sticker by i-th person)
  • an edge from Out(i, k) to In(j, k) for all i,j,k of capacity 1
The value of maximum flow from s(1) to t(1) should give you the maximum number of additional stickers that Bob can gain by trading his duplicate stickers.

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 10779 - Collector's Problem

Post by crip121 » Wed Sep 23, 2009 5:28 pm

never mind, i made a stupid mistake. ACed... :)

pratikjain1993
New poster
Posts: 2
Joined: Sun Mar 23, 2014 10:31 pm

Re: 10779 - Collector's Problem

Post by pratikjain1993 » Mon Mar 24, 2014 10:39 pm

I made the graph using this function :

Code: Select all

void build_graph()
{
    int i,j;
    nodes=0;
    vector <pii> in,out;
    FOR(i,1,n)
    {
        int src = ++nodes;
        int sink = ++nodes;
        if(i>1)
        {
            cap[sink][src]=1000000;
            adj[sink].push_back(src);
        }
        FOR(j,1,m)
        {
            nodes++;
            if(mp[i].count(j))
            {
                if(mp[i][j]==1)
                    continue;
                out.pb(make_pair(nodes,j));
                adj[src].push_back(nodes);
                cap[src][nodes] = mp[i][j]-1;
            }
            else
            {
                in.pb(make_pair(nodes,j));
                adj[nodes].push_back(sink);
                cap[nodes][sink]=1;
            }
        }
    }
    FORL(i,0,out.size())
    {
        FORL(j,0,in.size())
        {
            if(out[i].second==in[j].second)
            {
                adj[out[i].first].push_back(in[j].first);
                cap[out[i].first][in[j].first] = 1;
            }
        }
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
    #endif // ONLINE_JUDGE
    int t,tc;
    scanf("%d",&t);
    FOR(tc,1,t)
    {
        int k,i,j;
        SETZERO(cap);
        si(n);si(m);
        FOR(i,1,n)
        {
            mp[i].clear();
            si(k);
            FOR(j,1,k)
            {
                int x;
                si(x);
                mp[i][x]++;
            }
        }
        build_graph();
        assert(nodes<600);
        printf("Case #%d: %d\n",tc,max_flow()+mp[1].size());
        FOR(i,0,nodes)
        {
            adj[i].clear();
        }
    }
}
I have created only those output nodes which have non zero flow capacity( that is there is 1 or more duplicates available) from s(i) ... Similarly only those input nodes which are to have flow capacity=1... I am getting WA.. I have tried a lot but am unable to find the mistake... Please somebody help...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10779 - Collector's Problem

Post by brianfry713 » Tue Mar 25, 2014 12:38 am

Post your full code.
Check input and AC output for thousands of problems on uDebug!

pratikjain1993
New poster
Posts: 2
Joined: Sun Mar 23, 2014 10:31 pm

Re: 10779 - Collector's Problem

Post by pratikjain1993 » Thu Mar 27, 2014 4:00 pm


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10779 - Collector's Problem

Post by brianfry713 » Thu Mar 27, 2014 9:33 pm

Input:

Code: Select all

20
6 20
15 20 2 1 16 15 9 20 16 7 14 1 15 6 7 20
42 16 20 7 6 4 10 5 11 6 3 4 19 19 17 18 19 10 10 6 16 19 5 11 17 19 4 11 16 10 10 14 6 1 20 3 5 1 7 15 6 2 10
11 20 6 13 18 16 3 4 11 13 20 14
1 10
23 11 18 6 1 11 3 13 3 17 9 3 4 15 1 17 4 16 16 10 9 6 17 11
26 19 15 20 12 3 10 8 5 19 6 5 9 20 18 3 17 18 18 20 13 18 16 16 13 3 17
10 22
15 3 14 12 15 8 13 19 21 9 18 21 12 22 5 13
27 14 11 9 15 4 7 20 9 16 6 6 15 11 15 15 11 5 4 2 12 15 20 10 1 13 8 10
30 10 20 7 21 9 13 13 10 17 10 17 11 16 20 1 2 12 13 12 14 15 13 3 7 9 10 5 19 15 12
18 1 9 12 21 15 2 10 3 19 17 17 5 10 14 5 9 3 15
21 15 7 9 17 13 15 3 15 12 15 4 16 15 13 5 12 5 7 21 5 1
38 21 3 1 12 5 7 13 19 3 5 4 12 19 14 2 21 7 13 12 10 7 4 20 11 15 1 15 11 5 13 2 4 15 22 13 19 6 3
24 9 7 17 18 2 8 19 20 14 10 9 22 14 13 19 22 3 19 13 14 2 3 13 3
36 12 15 12 17 16 3 3 20 19 18 21 5 15 19 16 2 5 15 13 15 10 12 18 4 2 7 3 3 19 5 18 6 18 7 22 11
26 1 8 4 18 7 8 10 1 22 9 5 12 19 18 21 9 13 3 8 17 5 8 11 8 3 16
42 8 13 11 15 13 16 18 7 20 2 14 20 1 1 1 12 19 18 9 3 6 11 9 22 13 16 10 20 19 1 20 2 13 6 16 2 22 11 8 19 10 21
6 10
3 1 6 2
21 8 6 7 8 8 4 2 10 9 8 4 1 1 7 5 1 2 4 10 2 3
41 6 10 2 7 4 4 2 5 3 9 1 1 8 10 4 10 1 4 9 4 4 9 10 1 9 3 4 10 5 7 2 2 8 3 8 1 9 10 8 1 10
39 4 8 9 7 9 10 1 7 5 6 5 7 6 4 1 10 5 5 8 6 6 7 1 4 7 9 5 6 9 4 5 2 3 6 1 1 7 1 7
46 6 4 9 4 7 2 3 1 6 2 9 4 8 9 9 6 7 5 2 7 10 6 1 3 3 1 5 9 3 4 2 10 7 2 3 5 3 7 7 1 10 5 6 7 3 4
38 1 10 6 10 9 3 10 1 6 2 8 4 6 1 7 5 7 9 10 1 3 8 7 3 8 4 8 4 8 3 8 9 2 5 10 3 8 1
8 18
41 18 12 7 6 5 1 10 1 14 16 11 18 9 2 13 6 5 10 7 14 8 17 11 4 4 9 13 6 16 5 15 13 15 3 1 1 4 10 17 15 6
32 12 12 8 6 15 11 14 3 4 3 2 14 4 5 3 17 11 16 1 5 10 15 8 10 13 9 18 11 3 3 2 15
37 7 18 10 17 13 12 2 13 11 14 15 16 16 11 6 11 11 10 2 6 15 10 18 5 7 9 8 9 8 2 4 14 1 11 11 12 2
27 4 13 5 16 10 18 8 13 8 17 4 10 4 17 17 1 3 5 9 8 11 16 9 14 10 8 4
19 17 5 11 2 17 14 16 6 11 5 18 1 1 2 10 2 18 6 3
14 10 9 8 2 5 16 13 14 3 14 15 1 18 5
6 15 18 16 2 11 18
14 9 17 17 16 18 14 3 18 13 10 7 2 9 11
8 19
14 13 7 17 17 11 2 2 2 7 6 5 2 18 15
35 10 10 19 5 5 4 5 3 8 4 19 3 9 4 10 1 16 13 17 13 4 19 11 3 3 16 4 4 12 18 7 2 8 6 3
3 6 8 11
36 8 7 12 17 10 2 17 4 14 15 16 14 11 5 13 13 17 16 13 9 11 19 11 15 2 10 4 7 14 12 16 3 18 8 16 6
18 13 9 16 5 2 10 12 6 1 2 4 13 11 12 5 10 19 16
18 7 1 11 1 9 4 3 4 11 15 9 16 9 14 12 10 13 19
2 18 19
48 18 12 12 8 13 18 4 10 4 10 7 14 8 15 18 7 15 6 3 5 19 8 15 8 17 8 7 13 4 3 14 2 12 3 9 2 17 10 8 1 19 14 12 4 6 7 11 2
6 25
8 20 12 8 24 22 7 9 20
49 2 9 14 3 15 14 16 19 18 22 6 11 24 2 14 19 15 13 14 10 15 18 5 3 2 5 24 10 13 20 1 14 3 15 18 19 5 11 15 24 9 22 9 7 23 24 2 12 11
12 23 25 9 4 2 11 8 3 20 23 24 23
21 4 14 6 24 18 16 13 16 24 9 1 7 8 25 11 21 12 25 19 12 11
6 15 23 7 19 17 4
2 16 16
7 14
49 14 11 3 1 6 6 3 11 14 3 4 14 2 7 13 7 1 3 5 10 7 11 7 3 10 9 1 6 4 4 10 2 12 12 2 4 2 2 12 1 4 1 12 4 5 10 10 6 11
47 13 3 8 5 3 1 12 4 7 13 5 2 14 14 11 13 3 12 1 12 10 2 10 7 5 1 1 1 4 11 10 2 11 2 4 14 2 13 1 8 12 5 7 11 2 2 10
12 13 10 14 7 9 10 11 14 10 11 12 11
34 7 12 2 8 13 1 8 12 1 13 7 3 6 3 4 7 10 6 3 3 6 9 12 13 4 11 6 14 6 2 5 12 11 4
28 9 4 11 4 2 9 10 4 12 11 5 2 6 11 5 9 14 11 4 12 14 12 3 12 3 2 14 14
34 3 1 6 4 11 8 5 4 3 8 13 11 10 1 3 6 5 9 3 13 10 14 11 7 14 8 9 1 5 6 10 7 7 14
32 1 7 14 4 7 5 3 4 14 3 4 4 5 12 6 1 7 4 11 11 3 4 5 2 8 10 11 12 14 10 7 1
4 15
50 4 5 15 8 14 7 14 12 2 13 8 13 15 9 4 8 10 7 10 3 14 15 6 4 9 4 13 12 6 9 3 1 5 10 8 3 8 13 14 10 2 7 14 1 7 2 8 1 15 9
45 6 9 8 9 9 11 6 12 8 6 14 9 11 8 8 5 1 13 11 10 14 2 15 15 15 8 14 1 8 8 2 5 8 9 13 1 4 10 12 4 8 10 4 3 3
28 14 10 15 9 4 14 2 10 5 2 2 3 2 1 2 3 12 9 4 1 9 7 11 12 2 3 14 5
41 8 8 2 2 7 11 12 5 12 6 1 13 14 4 6 7 5 1 3 6 4 4 6 2 6 3 4 15 1 8 3 15 15 4 1 14 14 12 3 11 2
9 12
5 5 8 4 4 6
48 1 6 10 1 4 3 1 10 5 2 1 2 10 1 11 7 2 4 9 3 8 2 7 7 2 3 6 6 10 11 3 3 4 4 3 8 10 7 9 6 8 1 7 9 6 5 3 7
49 3 1 7 4 11 2 5 5 7 2 3 6 4 5 1 11 11 12 8 5 9 1 4 1 7 12 6 4 6 5 3 8 5 10 3 8 3 7 12 1 1 2 6 8 10 11 7 12 10
49 8 10 7 3 11 1 2 8 8 11 12 11 6 9 8 8 4 10 7 3 10 7 9 8 2 10 10 12 2 7 2 9 5 8 12 7 12 5 6 8 4 6 10 1 6 5 1 9 6
39 3 7 5 11 6 10 1 3 10 2 2 3 10 10 2 1 4 5 10 9 4 5 6 1 5 11 9 9 11 6 7 2 1 11 4 10 1 4 5
46 5 6 4 7 7 5 11 10 9 8 10 1 12 8 1 9 10 2 9 9 7 4 2 11 6 5 9 6 9 5 11 1 10 2 7 4 10 6 5 7 5 6 11 9 5 3
29 3 4 5 3 11 8 4 9 6 8 9 11 4 1 10 9 2 3 7 9 1 4 5 11 9 11 1 9 3
0
16 9 11 9 11 1 9 2 1 2 10 2 4 5 2 5 1
6 22
25 10 12 15 15 18 13 11 2 7 5 12 19 14 6 16 2 12 6 8 3 3 1 12 16 19
48 7 22 16 2 15 4 13 7 16 6 18 4 7 2 6 16 19 19 22 10 21 9 13 4 11 15 4 20 6 20 15 12 19 8 13 11 9 1 16 2 6 11 3 10 10 9 4 4
44 3 13 21 11 3 2 20 15 3 17 21 1 9 8 17 15 21 4 1 19 17 1 3 3 1 12 12 9 13 16 12 15 4 8 2 5 8 21 17 10 15 13 8 22
16 3 14 17 4 12 13 20 10 15 22 11 3 9 19 15 22
12 6 2 12 5 6 19 3 20 4 15 11 12
1 9
8 21
12 20 4 8 4 21 12 13 19 2 15 13 7
19 11 13 16 13 1 9 4 12 19 8 15 10 9 16 10 18 10 5 14
15 11 15 10 1 6 6 21 20 18 6 7 7 17 20 20
17 5 21 6 1 7 20 10 13 12 18 9 21 20 20 12 9 13
10 7 16 4 6 13 21 10 19 4 5
6 2 19 20 21 1 18
36 18 7 17 9 1 2 8 20 1 18 6 11 14 10 6 17 14 18 14 2 13 15 6 7 15 1 4 14 21 21 17 15 4 10 21 2
41 8 20 12 2 4 20 13 13 4 6 5 19 19 4 11 12 7 15 5 6 16 16 5 14 12 19 15 19 17 17 9 1 15 18 2 16 17 14 7 20 19
5 22
4 21 2 22 3
31 8 2 17 15 5 1 4 18 19 10 15 6 18 2 16 22 16 18 19 9 19 13 22 22 22 13 18 1 11 20 1
21 21 15 6 1 15 10 19 9 17 9 15 12 9 8 9 2 4 3 11 20 16
32 19 15 19 12 14 7 10 14 22 8 6 5 9 18 12 3 4 4 11 16 14 19 2 22 19 3 3 5 20 16 12 16
30 8 3 21 12 12 10 11 18 13 14 2 6 1 4 8 5 12 1 16 7 22 15 1 2 15 5 21 8 16 12
5 6
47 6 1 4 6 2 5 2 5 2 6 5 5 5 3 1 5 6 1 1 3 3 4 5 3 3 5 4 2 2 3 4 5 4 6 4 5 4 4 1 6 1 5 2 5 2 2 1
42 2 1 1 2 3 6 4 5 2 6 4 3 2 2 1 3 5 5 1 2 6 1 5 6 6 1 4 5 2 2 5 2 3 4 1 3 3 5 5 2 2 2
0
36 1 4 4 5 6 4 5 5 3 3 4 6 3 5 4 3 1 2 4 1 5 4 3 5 6 5 6 5 6 3 6 5 5 1 3 2
1 1
2 5
12 2 5 2 2 4 3 1 3 1 2 3 3
2 2 2
8 11
39 2 9 9 9 5 1 2 10 9 4 4 10 5 8 2 8 5 10 9 2 2 1 10 8 8 9 3 11 9 9 11 10 6 8 6 8 8 7 6
0
0
48 2 11 4 3 7 6 10 4 7 11 2 5 6 7 11 8 7 8 3 4 4 6 1 7 2 6 2 6 9 10 2 10 7 3 11 2 8 9 3 1 7 3 3 1 9 2 6 2
39 7 6 8 1 4 4 3 7 3 8 5 10 7 1 5 9 11 4 3 7 7 3 2 9 5 11 4 4 5 6 10 11 11 4 1 1 7 1 7
18 6 11 6 1 10 11 7 9 3 9 4 7 9 3 2 2 2 6
40 5 11 1 4 8 4 2 8 9 11 3 5 5 1 10 3 10 9 9 5 10 6 7 5 3 9 7 2 11 10 4 4 9 4 5 5 6 5 10 3
13 10 5 7 10 3 9 6 10 7 11 6 10 6
3 11
19 3 10 11 1 3 3 9 4 8 11 9 1 7 9 2 6 2 8 2
9 6 8 10 10 5 4 6 8 2
49 8 3 2 8 3 2 10 10 5 4 7 1 2 3 9 4 6 9 9 7 9 1 1 7 8 3 8 3 10 9 3 5 9 4 1 1 3 8 8 8 1 3 8 2 3 3 3 8 9
2 5
41 3 4 3 4 1 4 3 2 3 5 5 3 3 4 4 5 4 2 5 2 3 1 2 2 2 3 3 4 4 5 2 3 3 4 1 5 5 5 2 4 5
47 3 2 2 4 1 2 5 3 5 4 5 1 1 1 3 3 5 3 4 1 3 3 1 5 3 2 5 1 5 4 3 5 2 1 3 4 2 4 1 3 3 1 4 3 1 3 2
4 20
7 4 13 4 10 19 6 6
20 6 18 8 19 17 14 19 9 8 18 17 18 20 16 10 10 13 8 3 4
2 5 10
38 9 14 4 7 11 1 20 17 18 7 7 6 13 17 6 20 14 15 9 6 10 19 7 3 18 9 18 16 5 20 10 13 5 5 20 15 6 11
9 14
3 11 13 3
3 6 6 5
42 7 2 12 11 5 14 2 1 5 9 14 6 11 10 4 3 13 13 14 11 3 1 14 14 11 2 9 2 8 13 14 12 13 9 8 3 8 9 1 10 3 14
42 11 8 5 14 4 1 11 1 2 11 14 13 5 13 7 7 4 5 4 1 3 12 8 3 3 14 4 12 1 1 13 11 8 2 8 12 14 5 12 1 13 9
10 4 7 3 10 11 8 11 9 8 8
36 11 10 14 12 5 14 12 4 9 4 3 2 13 14 4 8 1 3 2 11 6 6 14 13 14 5 9 9 10 14 9 4 7 6 1 11
10 11 12 10 14 14 11 10 12 1 3
46 1 4 6 4 9 3 2 9 7 8 1 3 5 7 4 11 12 5 7 13 13 5 8 10 2 3 5 13 1 7 8 13 8 12 2 14 14 1 6 5 8 6 7 12 12 8
19 8 12 12 4 10 14 10 5 14 12 7 10 10 11 4 8 4 1 9
6 16
44 1 16 10 13 14 9 10 10 16 5 5 3 5 9 5 4 5 2 15 6 5 12 6 8 5 6 2 5 1 12 9 1 11 2 13 9 10 7 2 9 11 6 11 15
34 15 2 3 16 16 8 5 11 13 12 15 2 14 3 2 9 11 3 3 12 15 11 5 5 12 13 16 2 8 14 15 6 16 1
41 15 8 10 10 5 5 8 6 2 11 8 10 5 10 13 1 8 7 5 13 3 2 12 4 9 9 2 14 8 3 3 7 10 12 16 14 1 7 4 2 1
27 12 6 4 8 6 11 14 10 7 16 11 2 3 3 11 5 1 2 7 3 8 16 15 7 14 15 14
35 16 14 11 11 3 14 2 8 8 16 2 15 15 12 16 2 15 10 6 15 12 12 1 3 11 15 10 8 13 7 8 13 4 2 7
50 15 9 14 7 8 15 5 6 11 4 7 9 14 12 7 9 7 7 11 2 6 4 9 2 10 1 14 14 2 5 4 1 13 1 7 4 16 11 9 10 14 16 2 11 11 8 3 2 14 14
AC output:

Code: Select all

Case #1: 13
Case #2: 15
Case #3: 3
Case #4: 18
Case #5: 12
Case #6: 8
Case #7: 14
Case #8: 15
Case #9: 4
Case #10: 18
Case #11: 12
Case #12: 4
Case #13: 6
Case #14: 5
Case #15: 11
Case #16: 11
Case #17: 5
Case #18: 5
Case #19: 3
Case #20: 16
Check input and AC output for thousands of problems on uDebug!

OmarEltobgy
New poster
Posts: 1
Joined: Sat Aug 24, 2013 2:08 pm

Re: 10779 - Collector's Problem

Post by OmarEltobgy » Sun Jul 13, 2014 2:34 pm

Try this input:

Code: Select all

1
3 6
6 1 1 2 3 4 4
4 2 2 3 3
6 1 4 5 5 6 6
The answer should be:

Code: Select all

Case #1: 6

Post Reply

Return to “Volume 107 (10700-10799)”