Incorrect solutions

[Aimnos]

After testing a lot, I found out the inputs for all the Fare 'TestCase's:
TestCase#0 - input: 1 2 3 5; expected output: 14
TestCase#1 - input: 3 2 10 2; expected output: 4 (should be 2)
TestCase#2 - input: 1 2 3 4; expected output: 11

The problem is that the expected output is completely incoherent to the input, at least as I understand the problem.
Reflecting that, I implemented a solution that correctly prints 4 on TestCase#1, but is incorrect in a more general scenario.
To anyone that can explain to me why it is the way it is, please do so.

[Aimnos]

Following about the same testing principle, I found out all answers for Depleting Ammunition 'TestCase's:
TestCase#0 - expected ouput is 1
TestCase#1 - expected output is 2
TestCase#2 - expected output is 8
TestCase#3 - expected output is 32
TestCase#4 - answer is 17

My algorithm says that the solution for TestCase#3 is 27 bombs only.
In the same way, I modified the code to correctly answer 32 on TestCase#3.
Any insights on why this happens are welcome and apreciated.

[DeWill404]

Well you are missing the point....
Actually it is bound to happen, because given Problem Statement is not clear, I also had hard time to deal with it, untill got clue on stack overflow...

Problem want to say that,
for first A km prise is M, for rest distances prices is N...
and in input

A -> Max distance for M cost.
M -> Cost for first A km.
N -> Cost for remaining distance after A km.
D -> Total Distance in km.

Did you notice....?

D is total distance and A is distance with cost M,
They are totally independent values, where A is just threshold limit...

So, It might be possible that D < A,
Because question is saying that
for A distance take cost M
but if A>D, so how can you take Fare more then distance you travel..

so logic is that,
if A > D then
retrun DM;
else
return AM+(D-A)*N;

Here is my solution...
Hopes this help you,

with Regards, DeWill404

[Aimnos]

Hey DeWill404,

Thanks for replying and sharing your solution!

Although your solution does indeed work for all 3 test cases, I still belive that, logically speaking, your algorithm should not apply to this problem.
According to the problem's statement, "For the first A kilometer, the fare is M and for the subsequent distance, it is N per kilometer.", which implies 2 things:

• that M is a fixed base value for any travel that is at most A kilometers wrong;
• that N is a value that is applied upon the total fare per kilometer travelled beyond the initial A kilometers.
  Therefore, multiplying M with A or D should not be expected for the problem, unless it explicitly stated that it is a per kilometer type fare, as it did for N.

In conclusion, I do still believe that the logic expected should be (according to the problem statement):
if A > D then
return M;
else
return M + (D - A)*N;
but I still greatly appreciate your response and explanation of your logic.

[DeWill404]

Do not mention budd, it is the whole reason for open source to help each other 😄

Here is problem statement,
John is travelling by train, The fare of the train depends on the kilometer he traveled. For the first A kilometer, the fare is M and for the subsequent distance, it is N per kilometer. You are given total distance covered by train. Find out the total fare.

it is saying,
For A Km, fare is M and for Subsequent Distance(D-A) fare is N....

If you notice,
For the first A kilometer, the fare is M and for the subsequent distance, it is N per kilometer.
and
You are given total distance covered by train.
are two separate sentence...

So, Values A & D are totally independent, which can possibly means that A can be either larger or smaller then D,
as if we consider A as threshold value of M fare...

This is the possibility i assumed...
with Regards, DeWill404

[LaffinToo]

The algorithm i use for Depleting Ammunition fails test case #3 as well. the algorithm i use is conpletely different as well. Is there any way you can grab the inputs?

[LaffinToo]

Finally figured it out. the routine i used used a sort routine, and basicly went through the cities with range2, (figured since it was first city encountered,i would bomb city+range and start again at city+(range2). this worked for all except test case 4. Then I took a closer look at instructions, a bomb must hit a city.. did some adjustments to code, and it successfully passed all cases.

[Aimnos]

Hey @LaffinToo,

Thanks for replying.

Then I took a closer look at instructions, a bomb must hit a city..

This is actually the exact reason why my algorithm is wrong. I'l try to update it and post it soon. Thank you very much for sharing!

[LaffinToo]

#include <stdio.h>
#include <stdlib.h>

//Compiler version gcc  6.3.0

int main()
{
  unsigned int n,r,*c,b,d,i,j,l,m;
  scanf("%u %u",&n,&r);
  c=malloc(sizeof(int)*n);
  for(i=0;i<n;i++)
    scanf("%u",&c[i]);
    
  // Bubble Sort - Sort Cities by X axis
  for(i=0;i<(n-1);i++) {
    for(j=i+1;j<n;j++) {
      if(c[i]>c[j]) {
        c[j]^=c[i];
        c[i]^=c[j];
        c[j]^=c[i];
      }
    }
  }
  // Go through all cities
  for(i=d=l=m=0,b=1;i<n;i++) {
    // Do we have a Drop Zone?
    if(!d) l=d=m=c[i];
    // Can this city hit lowest Drop?
    else if((l+r)>=c[i]) d=c[i];
    // Can our Drop hit this new city?
    else if((d+r)>=c[i]) m=c[i];
    // Drop a bomb, set new city as Drop
    else {l=d=m=c[i];b++;}
  }
  printf("%u",b);
  return 0;
}

[Aimnos]

Hey @LaffinToo,

Thanks for sharing your implementation. I used it for reference for my own implementation, which is already available.

[LaffinToo]

Heh, I do the same with your implentations. I look it over, see how it was done, than work on my own routines. Good Work.

[riveroon]

Hey, love your work!

I found that one of your solutions is incorrect -
'The Largest Gap' states that the constraints are
.1<=Array elements<=10^4.,
implying that the Array elements are floating point numbers (hence the .1).

Thus the code should use float or f32 for the Array elements.

Here is my code:

//rust 1.30.0 

fn read() -> Vec<f32> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    return s.trim().split_whitespace()
        .map(|i| i.parse::<f32>().unwrap())
        .collect();
}

fn main() {
    let N = read()[0] as usize;
    let v = &read()[0..N];
    println!("{}",
        v.iter().max_by(
            |a, b| a.partial_cmp(b).unwrap()
        ).unwrap()
        - v.iter().min_by(
            |a, b| a.partial_cmp(b).unwrap()
        ).unwrap());
}

[Aimnos]

Hey @riveroon,

I would be inclined to agree with you, based on the constraints for the problem as stated on the website. However, there are other informations that lead me to believe that the array elements are actually all integers.

Firstly, the Input section clearly states that
The second line consists of N-space separated integer denoting the array elements.

Secondly, the first line in the Constraints section does not contain an ending period, while the second one does. This makes me think that the "decimal point" before the 1 on the second line is actually the missing period for the first line. In other words, I believe a typo was made.

In conclusion, I believe that my solution is not wrong, given that it passes all TestCases and there is sufficient reason to believe that the input is always an integer. However, using floating point variables to store integers is also valid and should work exactly the same, so your solution should be correct as well.

[riveroon]

Okay, racking my brain around this - You're right, they are indeed integers.

However, they aren't u16 (which does match the constraints, but fails the test case), which led me to see the '.1' and think that they must have been floats. I thought that the 'integer' was the typo, not the '.' =P

I also looked at and tried your solution, but because I looked at the one written in rust (which used u16, too - resulting in TestCase#1 and 2 failing), I failed to notice that using u32 would solve the problem.

So, I was really confused that 'it passes all TestCases', when it didn't for me - until I looked at your C code, which, to my surprise, noted that

// Even though the problem states that the maximum value for any element is 10000, using unsigned short fails for TestCase#1 and TestCase#2

So i tried out my code using u32, and voilà, it passed with flying colors!

Mistakes like this seem to be way too common for me - I have more trouble making my code meet the conditions, than actually writing the code (Especially the Depleting Ammunition one, that actually took 3 days for me to figure out my my mistake!)

Anyways, thank you for answering - I appreciate your work.
Have a good day!