## Search found 119 matches

Wed Sep 23, 2009 7:38 am
Forum: Algorithms
Topic: Longest path in a DAG
Replies: 0
Views: 2475

### Longest path in a DAG

Longest path in a DAG. I've some problems for longest path in DAG with this function. Can you point out if it is correct. Found it , visit is the culprit. int dfs(int x){ visit[x]=true; if(dp[x]) return dp[x]; int i,ans=1; for(i=0;i<g[x].size();i++){ if(!visit[g[x][i]]) ans=max(ans,1+dfs(g[x][i])); ...
Wed Sep 23, 2009 7:11 am
Forum: Volume 100 (10000-10099)
Topic: 10029 - Edit Step Ladders
Replies: 70
Views: 21717

### Re: 10029 - Edit Step Ladders

never mind found it.
Sat Sep 19, 2009 9:47 am
Forum: Volume 116 (11600-11699)
Topic: 11668 - How Many Teams
Replies: 7
Views: 1434

### Re: 11668

if we do as above, don't we need to track which department has allocated student to which partition.

f(a,b,c) = f(a-x,b,c)*Bin(a,x) *Bin(b,y)*Bin(c,z) *( k!). (x+y+z=k)
Fri Sep 18, 2009 4:39 pm
Forum: Volume 116 (11600-11699)
Topic: 11673 - Enemy at the Gateway
Replies: 2
Views: 812

### Re: 11673 - Enemy at the Gateway

thanks chimed, for all those who want to solve the problem. don't swap ,< p0 , q0> , assume they are in correct order. If the number of places where pattern can be found is 0, then print 0, not "Peter has Forgotten Everything". the output is like printf("Case %d: %d\n", testcase,ans); for everything...
Thu Sep 17, 2009 11:06 pm
Forum: Volume 116 (11600-11699)
Topic: 11673 - Enemy at the Gateway
Replies: 2
Views: 812

### 11673 - Enemy at the Gateway

i don't understand this problem. What is s7,s8,s9. First Output For each test case, output the number of places, the preamble may start. Isn't this an integer ? How can we have more values. Then after constraints it says Output For each line of input produce two or more line of output. The first lin...
Thu Sep 17, 2009 4:18 pm
Forum: Volume 116 (11600-11699)
Topic: 11669 - Non Decreasing Prime Sequence
Replies: 2
Views: 903

### Re: 11669 - Non Decreasing Prime Sequence

thanks, yes it was an off by 1 , i forgot the powers of 19, only calculated until 18.
Thu Sep 17, 2009 2:37 am
Forum: Volume 116 (11600-11699)
Topic: 11668 - How Many Teams
Replies: 7
Views: 1434

### Re: 11668 - How Many Teams

Can you give some hints, I thought of maximum matching but it is too complicated
Thu Sep 17, 2009 2:12 am
Forum: Volume 116 (11600-11699)
Topic: 11669 - Non Decreasing Prime Sequence
Replies: 2
Views: 903

### 11669 - Non Decreasing Prime Sequence

Can someone post input outputs for the following and additional cases ? I get WA 38 2 10 1 2 10 2 2 10 3 2 10 4 2 10 5 2 10 6 2 10 7 2 10 8 2 10 9 2 20 10 2 500 35 2 1000 500 2 10000 5000 2 100000 50000 2 1000000 500000 2 1000000 99999 2 1000000 999993 2 1000000 999994 2 1000000 999995 2 1000000 999...
Mon Sep 14, 2009 3:31 pm
Forum: Volume 116 (11600-11699)
Topic: 11667 - Income Tax Hazard II
Replies: 5
Views: 3122

### 11667 - Income Tax Hazard (II)

Code: Select all

``````10000 50000 50002
70000 50000 80000
120000 50000 200000
11111 122222 233333
131111 122222 233333
60000   50000 70000
10000 50000 150000
90000 50000 200000
0 0 0

Case 1: 0.00
Case 2: 1333.36
Case 3: 3266.69
Case 4: 0.00
Case 5: 71.12
Case 6: 500.02
Case 7: 0.00
Case 8: 1066.69``````
Sun Sep 13, 2009 8:17 pm
Forum: Volume 116 (11600-11699)
Topic: 11675 - Happy Friends
Replies: 6
Views: 3216

### 11675 - Happy Friends

10 4 4 0 5 0 1 1 2 2 3 3 1 4 4 0 6 0 1 1 2 2 3 3 1 4 4 0 35 0 1 1 2 2 3 3 1 4 4 0 36 0 1 1 2 2 3 3 1 4 4 0 37 0 1 1 2 2 3 3 1 4 4 0 47 0 1 1 2 2 3 3 1 10 9 0 10000 0 1 1 2 2 3 3 4 5 6 6 7 7 9 6 8 9 1 10 9 3 10000 0 1 1 2 2 3 3 4 5 6 6 7 7 9 6 8 9 1 30 29 15 1000000000 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 ...
Tue Sep 08, 2009 2:27 pm
Forum: Volume 116 (11600-11699)
Topic: 11664 - Langton's Ant
Replies: 10
Views: 3803

### Re: 11664 - Langton's Ant

can you guys show me code to convert from big integer to mod2 string ? string mapper[]={"0","1","2","3","4","5","6","7","8","9"}; inline string myconvert(const string& s){ if(s=="0") return "0"; if(s=="1") return "1"; string ns; int num=0,carry=0,i; for(i=0;i<s.size();i++){ num=carry*10 + s[i]-'0'; ...
Mon Sep 07, 2009 11:32 pm
Forum: Volume 116 (11600-11699)
Topic: 11660 - Look-and-Say sequences
Replies: 1
Views: 1767

### 11660 - Look-and-Say sequences

AC input output

Code: Select all

``````1 3 1
1 3 2
1 7 2
123 3 1
22 30 2
123 43 3
100 343 7
999 999 999
1000 1000 500
324 343 233
0 0 0``````

Code: Select all

``````2
1
3
3
2
2
2
1
1
1
``````
Mon Sep 07, 2009 4:15 pm
Forum: Volume 116 (11600-11699)
Topic: 11659 - Informants
Replies: 31
Views: 9001

### Re: 11659

As an example, let's assume there are four informants A, B, C and D, with the following surveyed answers: ``A says B is reliable but D is not'', ``B says C is not reliable'', and ``C says A and D are reliable''. In this case, it happens that at most two informants are reliable. Can you tell me how ...
Mon Sep 07, 2009 4:01 pm
Forum: Volume 116 (11600-11699)
Topic: 11659 - Informants
Replies: 31
Views: 9001

### Re: 11659

yes it is 20 because the mask 2^20 -1 is satisfied by all things. I don't understand how to formulate this problem and i find this problem VERY HARD. I really don't now how to solve this one. Can you give me more examples ,smaller ones so that i can relate it understand and use it to test my program...
Mon Sep 07, 2009 3:46 pm
Forum: Volume 116 (11600-11699)
Topic: 11664 - Langton's Ant
Replies: 10
Views: 3803

### Re: 11664 - Langton's Ant

removed stringstream to get AC. stringstream is very slow. Got TLE