Hello guys ,
Today i was solving CodeChef: Practical coding for everyone ( 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 : #include <bits/stdc++.h>using namespace std;typedef long long int ll;#defi - Pastebin.com
Will be helpful if someone tells me where i am wrong
Thanks a lot !!
1 Like
ssjgz
December 20, 2019, 6:04pm
3
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
For this problem, my solution gives WA for only a few testcases. Can someone please provide a testcase where it doesn’t pass?
Thanks!
@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
ssjgz
December 20, 2019, 6:43pm
5
Dunno then
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
Will try to solve it
Thanks a lot !! @ssjgz
1 Like
ssjgz
January 9, 2020, 9:34am
8
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: #include<bits/stdc++.h>using namespace std;typedef long long int ll;#defin - Pastebin.com
It’d be really helpful if you gave a testcase where this fails. @ssjgz
2 Likes
ssjgz
January 9, 2020, 6:23pm
11
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
ssjgz
January 11, 2020, 9:27am
12
@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 : CodeChef: Practical coding for everyone
can someone figure it out why the code is wrong ?
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
ssjgz
April 24, 2020, 12:44pm
16
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