PERCAPTA - Editorial

editorial
, , , , ,
65

Hello everybody! After reading the editorial, I wrote a code that uses DFS but it is showing time out for me. So, I decided to copy and Paste “Tester’s Code” (which also uses DFS), but it is showing runtime error in that too. What is going on?
https://www.codechef.com/viewsolution/34627355
Please look into this matter…

66

I ran it with C++ 17 it shows error but with C++14 it is working fine. Any ideas as to what can explain this?

67

Initially I was getting WA with DFS. Solution Link.

Then I modified that same code just by not selecting any edge to the non - desired provinces in the graph itself (i.e. I’m not even creating that edge in the Adjacency List) and it got AC. Solution Link.

Now I’m all the more curious about what is going wrong in the first solution.

Anyone please look in the codes and suggest strong cases where it’s going wrong.

@taran_1407 please help sir !!

69

@anon55283797 fast input output use kar le ,ye inki alag level ki bakchodi h ,mai buri tarah se frustrate ho gya iski wajah se

70

TL was somewhat tight.
Most of the AC solution has taken 0.5s+ time (in cpp).

71

just use fast unput bro ,they are not testing your logic ,they are just testing how do we efficiently use fast i/0

72

How to flagged this post?

73

Hello there, I changed your return type of dfs func from vector to void and it got accepted
https://www.codechef.com/viewsolution/34628746

1 Like
74

I was initially using testers’s approach of selecting vertices depending on ratio, this approach gave TLE in both DFS and BFS , I don’t know why.
Then I removed this extra loop and and checked ratio just by multiplying and got
AC in both DFS and BFS approach.

My DFS soltuion (AC):
https://www.codechef.com/viewsolution/34629111
MY BFS soltuion (AC):
https://www.codechef.com/viewsolution/34629095

75

My humble request to don’t include your micros in solutions. It’s very hard to understand for beginners.

2 Likes
76

here is my submission using DSU.
https://www.codechef.com/viewsolution/34631551

1 Like
78

Why am I getting TLE.
I am using DFS. I am storing all the provinces in a map and running dfs on each node.
[My submission]
(CodeChef: Practical coding for everyone)

79

Can someone please help why I am getting WA(used the DFS approach)
My Code::EEDtu4 - Online C++0x Compiler & Debugging Tool - Ideone.com
THANKS IN ADVANCED!!!

80

Hey @taran_1407 @raja1999 if you look at tester’s solution, there is function name fd which is iterating over all the choosen nodes and then applying dfs over it. Don’t you think, this should be a O(n*(v+e) algorithm, which is of quadratic type

81

Here’s my submission using BFS.
Learning or realization
if A/B <= C/D
then A/B <= A+C/ B+D <= B/D

82

There is one more condition that if(vis_i ==0) before doing dfs. This makes sure each vertex is visited at most once. Hence it is O(N).

83

Is it 5 seconds even in the contest? If so, that is good to know. Next time I will submit in python then.

84

Oh god, can’t believe this was the only mistake T_T. Thank you so much man, your input is invaluable!

1 Like
85

xD. I did floating point arithmetic in a codeforces round and I couldn’t wrap my head around the fact that this was the only bug. Since then I always find a way to avoid floating point arithmetic :P.

Every Contest Teaches You Something!

1 Like
86

use scanf, printf because they have set time limit 1 second.
This is something which I hate about Codechef. That’s why Codeforces set execution time limit 2 seconds.

2 Likes