WA in INOI1401

Hello guys ,

Today i was solving https://www.codechef.com/INOIPRAC/problems/INOI1401 ( Highway Bypass ) this problem and i am getting wa and i checked on many testcases myself but i am unable to find a fault in my code

My code : https://pastebin.com/PKmwe5V0

Will be helpful if someone tells me where i am wrong

Thanks a lot !!

1 Like

I changed my code
And here is my new code : https://www.codechef.com/viewsolution/28424188

Someone please help me :sob::sob:

@ssjgz @druh @sarthakmanna @vijju123 @kshitij_789

I’ve quickly knocked up a brute-force implementation and testcase generator, and apparently the answer to the testcase:

6 5 4
1 1 1 0 1
0 1 0 0 1
1 1 1 0 1
1 1 1 0 1
0 0 1 1 1
0 1 1 1 1

is 6.

2 Likes

@ssjgz ,

His code is correctly printing the answer for your test case and his code is failing for the same testcases mine is failing

@crap_the_coder

Dunno then :slight_smile:

Edit:

@crap_the_coder 's solution gives 3 for this testcase:

8 4 4
1 1 1 1
1 1 1 0
0 1 1 0
0 1 1 0
1 0 1 0
1 0 1 0
1 0 1 1
1 0 0 1

but mine (and another AC solution) give 4.

3 Likes

Got to know where I am wrong
In my code ( as well as @crap_the_coder’s code ) we are over subtracting

What we are doing :

dp(7,3) = dp(6,3) - dp(2,3)

What we should do :

dp(7,3) = dp(6,3) - dp(2,3) + dp(1,3)

This became inclusion and exclusion problem :sob: :sob:

Will try to solve it
Thanks a lot !! @ssjgz

1 Like

Why is my code giving WA ??

My code : https://pastebin.com/XpnZ4H11
Pls let me know a testcase where this fails
@ssjgz

:slight_smile:
Thanks !

1 Like

According to my Brute-Force solution, the answer to the testcase:

20 16 4
1 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1
1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1
1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0
1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1
0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1
1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1
1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1
1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 0 1 1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1
0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1
0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1
1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 0
1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1

should be 15418.

3 Likes

Thank you. After changing the code a bit , it works for the above testcase and a few more but is still failing for a few (including those for which d=2).
Here’s my new code: https://pastebin.com/Rhgq6ADM
It’d be really helpful if you gave a testcase where this fails. @ssjgz

2 Likes

Consider the testcase:

11 18 7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 Likes

@anon40864956

The answer to the testcase:

13 10 5
1 1 1 1 0 1 1 1 1 0
1 1 0 1 1 1 1 0 1 1
1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1
1 0 1 1 1 0 1 0 1 1
1 1 0 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 0 1

is apparently 4378.

1 Like

for me too this problem is happenning , my code also failed in same test cases
my solution : https://www.codechef.com/viewsolution/32186570

can someone figure it out why the code is wrong ?

how is it 4 ?

1 1 1 1
1 2 3 0
0 2 5 0
0 2 7 0
0 0 7 0
0 0 6 0
0 0 3 3
0 0 0 3

This represents the number of ways of reaching a square .
The blocked ones are always 0 .
How is the answer 4 , I cannot understand , can You please explain

These are the outputs I got from my brute-force solution:

>echo "8 4 4
> 1 1 1 1
> 1 1 1 0
> 0 1 1 0
> 0 1 1 0
> 1 0 1 0
> 1 0 1 0
> 1 0 1 1
> 1 0 0 1" | ./a.out
Reached dest: 
ULUUUULUUL
Reached dest: 
ULUUUULULU
Reached dest: 
ULUUULUUUL
Reached dest: 
ULUUULUULU
solutionBruteForce: 4
1 Like

i found my mistake ,
thank you

1 Like