Search found 147 matches

by Shafaet_du
Thu Jun 23, 2011 4:58 pm
Forum: Volume 112 (11200-11299)
Topic: 11247 - Income Tax
Replies: 50
Views: 20950

Re: 11247 - Income Tax Hazard

Ac after lots of wa. try to avoid double whenever possible. try this random cases: 2345235 34 1243214 34 213123 45 21313 5 12432 65 456456 54 3452342 23 36213 21 324234 4 35645555 4 344 3 23325 100 234 0 12312 56 234234 4 0 0 out: 3553384 1883656 387494 22433 35517 992293 4483559 45837 337742 371307...
by Shafaet_du
Thu Jun 23, 2011 3:51 pm
Forum: Volume 115 (11500-11599)
Topic: 11561 - Getting Gold
Replies: 31
Views: 9769

Re: 11561 - Getting Gold

use flood fill,just dont dont call flood() from risky places.
by Shafaet_du
Thu Jun 23, 2011 3:13 pm
Forum: Volume 110 (11000-11099)
Topic: 11094 - Continents
Replies: 43
Views: 19988

Re: 11094 - Continents

no need to use gets.
by Shafaet_du
Tue Jun 21, 2011 5:33 pm
Forum: Volume 8 (800-899)
Topic: 846 - Steps
Replies: 30
Views: 16058

Re: 846 - Steps

In 'n' steps you can advance to maximum (i/2)*( (i/2) +1) numbers if n is odd and (i/2)*( (i/2) +1) + ceil(i/2) numbers if n is even,where i=n/2. Save this and do a binary search(linear search may also do)
by Shafaet_du
Tue Jun 14, 2011 12:22 am
Forum: Volume 118 (11800-11899)
Topic: 11892 - ENimEN
Replies: 9
Views: 3243

Re: 11892-EnimEn

You don't need XOR approach or any kind of knowledge on nim. Just do some thinking. Try this cases if you get wa:

Code: Select all

7
3 2 1 1
4 2 2 1 1
5 2 2 2 2 2
6 82 62 24 12 2 32
6 1 1 1 1 1 1
5 1 1 1 1 1
6 2 3 4 1 1 1

Code: Select all

poopi
poopi
poopi
poopi
piloop
poopi
poopi
You should get ac if you can pass this.
by Shafaet_du
Mon Jun 13, 2011 5:30 pm
Forum: Volume 113 (11300-11399)
Topic: 11386 - Triples
Replies: 23
Views: 8621

Re: 11386 - Triples

Try this:

Code: Select all

20
234
67
45
56
34
67
45
34
56
45
34
56
67
45
5
34
5
54
67
my output from accepted code: 56
uva toolkit output: 63

Current time limit is 8 sec,so n^2 will pass.
by Shafaet_du
Fri Jun 10, 2011 9:30 pm
Forum: Volume 108 (10800-10899)
Topic: 10887 - Concatenation of Languages
Replies: 49
Views: 18756

Re: 10887 - Concatenation of Languages

getting tle after tle :(. I tried trie. I dont know how to write hash function yet.
by Shafaet_du
Fri Jun 10, 2011 12:32 am
Forum: Volume 102 (10200-10299)
Topic: 10243 - Fire! Fire!! Fire!!!
Replies: 12
Views: 6445

Re: 10243 - Fire! Fire!! Fire!!!

uva toolkit gives wrong output to this case: 5 1 2 1 1 1 3 1 5 1 4 0 my ac code outputs 2 while toolkit outputs 3. ""for each corridor at least one of the two galleries it connects must have a fire exit"" fulfilling this condition is enough to solve the problem. Use dynamic programming. Check each n...
by Shafaet_du
Thu Jun 09, 2011 11:42 pm
Forum: Volume 101 (10100-10199)
Topic: 10150 - Doublets
Replies: 46
Views: 16964

Re: 10150 - Doublets

@Live_lie:
Bfs can pass the time limit if you can build the graph efficiently. I used trie instead of map and passed the limit.
by Shafaet_du
Thu Jun 09, 2011 10:53 pm
Forum: Volume 113 (11300-11399)
Topic: 11307 - Alternative Arborescence
Replies: 22
Views: 10995

Re: 11307 - Alternative Arborescence

7 colors gave me ac,5 color wa. But i think a tree should have no loops and chromatic number should be 2. but this problem statement says there can be loops.

Don't assume 0 as root. The node which have no in-degree is the root.
by Shafaet_du
Wed Jun 08, 2011 9:44 am
Forum: Volume 107 (10700-10799)
Topic: 10702 - Travelling Salesman
Replies: 20
Views: 9428

Re: 10702 - Travelling Salesman

1-3,3-2
5+2=7
by Shafaet_du
Tue Jun 07, 2011 10:19 pm
Forum: Volume 106 (10600-10699)
Topic: 10681 - Teobaldo's Trip
Replies: 44
Views: 12120

Re: 10681 - Teobaldo's Trip

I solved using dp but i am interested to know the matrix exponent solution. I am failing to raise the power to 200 as the elements are becoming too large. Do we need to use some kind of modular arithmetic?
by Shafaet_du
Mon Jun 06, 2011 9:52 pm
Forum: Volume 9 (900-999)
Topic: 988 - Many Paths, One Destination
Replies: 9
Views: 7332

Re: 988 - Many paths, one destination

Explanation to sample input: 6 3 1 2 5 3 2 3 4 2 3 4 0 1 5 0 This means from event 0 you can go to event 1,2,5. from event 1 you can go to event 2,3,4. You need to determine the number of ways you can go to event of death(event that have no choices). You can see it becomes an DAG if you draw the cho...
by Shafaet_du
Thu Jun 02, 2011 7:04 pm
Forum: Volume 115 (11500-11599)
Topic: 11572 - Unique Snowflakes
Replies: 36
Views: 12535

Re: 11572 - Unique Snowflakes

my solution is O(n) + complexity of accessing stl map in each iteration. it took .416 second.

btw its the 600th problem that i solved :P.
by Shafaet_du
Thu Jun 02, 2011 6:40 am
Forum: Volume 115 (11500-11599)
Topic: 11597 - Spanning Subtree
Replies: 4
Views: 3982

Re: 11597 - Spanning Subtree

Easy problem. in an complete graph you have n*(n-1)/2 edges and you need n-1 edges to form each spanning tree.

Go to advanced search