Problem AHHOUSE of Innerve's Summer Code Challenge [C++]

general
, , ,
1

The link to the problem is HERE.
[The competition is closed now]
I solved this problem in C++ and tested for all possible combinations I could and uploaded the code for submission. But it showed “Wrong Answer”. If can anyone tell me any testcase for which my code produces wrong output (I could not find any) andI just want to know what mistake I had committed. Any help is Much appreciated…!
My solution is HERE

Codechef should upload the test cases they used to verify the solution (after the contest ended). Atleast one gets to know which cases are not catered in the code…

2

There are lots of problems with your code.

  • If T > 1 it doesn’t work for obvious reasons.
  • The code is very inefficient. I’m surprised you didn’t get TLE. You should apply DP.
  • But most importantly, in your code you only move down or right (assuming you start at the left upper corner). But what is with the following map?

PF-matrix:

111
991
111
199
111

You’re algorithm gives the answer 15, but it is possible with a fear factor of only 11.

4 Likes
3

Can you please explain the DP solution? I have solved it using dijkstra.

4

@ista2000 I was just telling OP, that his solution was inefficient. Even if you apply DP to his approach, his solution would be wrong. Dijkstra is probably the best approach for this problem.

1 Like
5

What is the DP solution? I am new to codechef so don’t know most of the obvious algorithms…

6

Most probably it should be solved using Dijkstra, cause they added test cases to give dp approach (which only considered down and right) a WA.

7

It can also be solved using Floyd-Warshall algorithm.

1 Like
8

Hi @c_utkarsh, Can u please explain your solution?

9

@dishant_18, I’ve already given a quick explanation about it in the following link. I can elaborate more if you want. https://discuss.codechef.com/questions/106772/ahhouse-test-case-were-added-after-i-correctly-submitted-my-code

1 Like