OJ Board

Hi guys! i dont know how optime my search in this problem, some hint ? I used Dynamic programming to solve this problem.Think a dp table of size [31][4][4][4][4][4][4] is within memory constraint of this problem.Just make best strategy at each recursion for each player and meomrize this for future ...

Well,Here's how 170 comes 1)Fill tank with 9 unit from city 0 and go to city 1 which costs 9 unit of fuel(9*10=90) 2)From station 1 take 8 unit of fuel and go to station 2 which costs 1 unit of fuel(8*10=70) 3)Go from station 2 to destination 3 which needs 7 unit of of fuel .so here u don't need any...

Just check whether graph is strongly connected and then check whether graph have any cross or forward edge.If first one is 'yes' and second one is 'no' then the graph is cactus otherwise not.no need to check something else.Here's some case. 2 5 7 0 1 1 2 2 0 2 3 3 2 2 4 4 2 5 8 0 1 1 2 2 0 2 3 3 2 2...

LCA for this problem?! I just used normal bfs to solve that and nothing else is needed. Just use one flea's location as source and another flea's location as destination. Then find the path between them. If path length+1 odd then they will jump between two node forever otherwise they will meet.Now,J...

I would like to tell respective authority of this problem to add some more data set in input file.It missed some input like: 5 1 2 3 5 4 output should be 5 but previous accepted code gave 4.after fixing that I got accepted which means absence of data set like that.For those who getting WA Try This I...

I don't understand why the cities are not case sensitive as problem description didn't cleared it.
How to get that point 'case insensitive' from this problem?

@plamplam
ur exact about my fault.I overlooked a blank space character .after fixing it I got accepted.BTW,thanks for ur reply.In fact I forgot about this problem and ur post made me give a look back at it....

I tried this with BFS+Bit-masking.But getting TLE.Same result for Dijkstra+bit-masking too.
whats the correct approach to solve it?

To:bourne
If You didn't get it accepted yet ..then it's for u...

long long dp[11][31]; //dp[city][day]

day could be as large as 1000 ..so you should increase size of 2nd dimension of your array..I was also getting WA for this reason..

Data set for this problem is weak,I think.As,The Graph is undirected. Output for following should be: 7 7 1 4 2 4 5 5 5 2 2 1 7 3 7 5 3 4 6 3 6 2 3 0 0 My latest accepted approach Outputs: 1 4 1 7 But my another accepted(Not supposed to get accepted :D) outputs: 1 4 5 4 5 2 which is definitely wrong.

I don't know whether you got accepted it..However you could reduce number of iterations in following portion. You don't need to look over all the node's possible to find adjacent of current node rather you should look up only four node up, down,left ,right of current node..this should avoid TLE...:)...

I Tried many Test-cases compared with UVA toolkit's output and it passed all.
I counted path as sclo said and as aninnda implemented...could not figure out reason behind WA...please help anyone....here is my code

Even My O(n^3) solution was giving TLE and was really irritated with this...at last I found memset() is too slow for this problem..manual assigning gives me accepted... :) Try these Input: 13 170 8 100 26 351 16 200 5 2 23 323 14 156 12 12 0 0 Output: Case 1: 201413 Case 2: 61890 Case 3: 1 Case 4: 1...

I was Trying it with nlogn+n+n^2logn algorithm..but was getting TLE ..What I was doing is: 1)First,I sorted data 2)Then used Grouping Idea.By O(n) loop I made separate list of unique elements with their frequency 3)Then two nested loop: for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) result+=Binary_search(a[i...

I was really tired of this problem..was getting WA repeatedly...Let me show what was giving me WA: I was taking Input Like Below: scanf("%d",&kase); getchar(); while(kase--) { getchar(); for(i=0;i<4;i++) gets(grid[i]); scanf("%d",&n); getchar(); while(n--) { gets(word); /...