Horse Racing Duals puzzle discussion


#315

I did it in Python. For some reason I pass "Horses in any order" and "Many horses", but not "Simple case". It seems like first input is entering 3 instead of 4, so it prints when I inserted

print('n = ' + str(n), file=sys.stderr)

after

n = int(input())


#316

The problem statement doesn't say that all the speeds you'll be given are unique, which implies that there is a chance that horses with the same speed will be in the data set. What will be the result if those horses race each other, and what will the difference in speeds be?

From another perspective, the output D is shown to be an integer value greater than or equal to zero. Can your algorithm produce that?


#317

Hello, I made this code :
include iostream>
include string>
include vector>
include algorithm>
include set>

using namespace std;

int main(){
set<unsigned long> myset;

unsigned int N;
cin >> N; cin.ignore();
for (unsigned int i = 0; i < N; i++) {
    unsigned long Pi;
    cin >> Pi; cin.ignore();

    myset.insert(Pi);
}

set<unsigned long>::iterator it=myset.end();
it--;

unsigned long ecartTmp=*it-*--it;

if (ecartTmp==1 || myset.size()==2){
    cout << ecartTmp <<endl;
    return 0;
}

unsigned long ecart=ecartTmp;

do{
    ecartTmp=*it-*--it;

    if (ecartTmp==1){
        cout << "1" <<endl;
        return 0;
    }

    if (ecartTmp<ecart){
        ecart=ecartTmp;
    }
}while(it!=myset.begin());

cout << ecart << endl;

// Write an action using cout. DON'T FORGET THE "<< endl"
// To debug: cerr << "Debug messages..." << endl;
}

It pass "horses in desorder" in IDE but not when I submitted it, why?

Thanks for help :blush:


#318

My code gets 90% on validation test. It does not print the values for the shorter distance among the initial two horses according to the results. I don know why.

**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
let arr = []
let arr2 = []

var N = parseInt(readline());
for (var i = 0; i < N; i++) {
    var pi = parseInt(readline());
    arr.push(pi)
}
arr = arr.sort()
for(let i = 1;i<arr.length;i++){
    arr2.push((arr[i]-(arr[i-1]))*1)
    }

for(let i =0;i<arr2.length;i++){
    if(arr2[i]<0){
        arr2[i] = arr2[i]*-1}}
arr3 = arr2.reduce(function(p,n){if(p>n){return n}
else{return p}})
print(arr3)

Here is my code. It would be great if you could help me.


#319

When I test against Many Horses, it says it expects 47 as the answer. But when I print off the list, the numbers are 0, 1, 2, 3, 4, 5, 6, etc… so the minimum difference should be 1. Am I missing something?


#321

Don’t use a std::set. You’re losing information if two horses have same power.
You’re lucky to pass the validator 5 with your method because all powers are equal, so your set is of size 1 and
unsigned long ecartTmp=it-–it gives you 0 then.

Hi, I don’t get your code.
If you do arr = arr.sort() then arr is sorted in increasing order I guess, so arr[i]-(arr[i-1]) is always a positive number.
You don’t have to copy the adjacent differences in arr2, you’re wasting time and space.
Just traverse arr and compute arr[i] - arr[i-1] on the fly.

I don’t know what you’re printing (the loop count ?) because the numbers begin like this :
9999999
9999888
9999741
9999653
9999595


#322

Oh, wow. Yeah, I was missing a really obvious piece. Thanks for the help.


#323

Hey, I am a little confused about this puzzle. In the second test case wouldn’t the output be 27, since the 2 greatest powers are 55 and 28?
Am I getting this right? How in this particular case the output be 1? Is it a bug?

image


#324

quote from the puzzle’s statement

Write a program which, using a given number of strengths, identifies the two closest strengths and shows their difference with an integer (≥ 0).

Here, the two closest strengths are 10 and 11. So the difference is 1.


#325

I see. I got it mixed up. Thank you for the clarification.


#326

I’m amazed at the length of this thread.

As other people said, bash is not meant to do algorithms, it’s just meant to call standard UNIX tools which will do the actual job. Trying to do any kind of tight loop in bash is like using visual basic to do 3D imaging. The worst possible tool for the job.

UNIX pipelining system is extremely powerful. The data are read only once at the entrance of the chain and then remain in memory, so disk access overhead is limited to a minimum. Each process in the pipe chain will run in parallel, so except for the sort that cannot produce results until it has processed the whole input, other filters will spit out results as soon as they have an input line available. If an element of the chain is waiting for disk I/O, the other elements use the available CPU to do their part of the job. No bottleneck at all, except logical data dependency (you need to wait for the sort to finish before you can process its output data).
And most important of all, each UNIX tool is an optimized binary that will do its job extremely well, while bash is a general purpose interpreter that cannot compete with compiled code in terms of efficiency and will run your own code, which is very likely to be less optimized than tools that have been fine tuned for decades.

I solved it in 7 lines of bash, with a pipeline of :

  • sort to get the values sorted
  • awk to produce a list of differences (with a 26 character long awk script that just substract each line from the next)
  • another sort to sort the differences
  • tail to display the needed result

The processing time of the awk script is basically zero. The CPU goes into the two successive sorts.

If you try to do the differences within the bash shell, your code will run inside a single process (the bash interpreter) so you will add a huge bottleneck just to substract two consecutive values.
If (God forbid!) you write your own quicksort or whatever sorting algorithm in bash script, you will replace a lightning fast optimized binary code with a ponderous interpreter that needs to think hard each time it tries to access a variable or index an array.
It can be an interesting challenge to make that work fast enough, but you can spare yourself the hassle really easily.


#327

I don’t know why my code is not working.If someone can help me.This is my mrogram(
class Solution
{
static void Main(string[] args)
{

    int N = int.Parse(Console.ReadLine());
    int[] hstr = new int[N];
    for (int i = 0; i < N; i++)
    {
        hstr[i] = int.Parse(Console.ReadLine());
    }
    int horse1 = hstr[0];
    int horse1idx = 0;
    for(int s = 1; s < N; s++){
        if(horse1 < hstr[s]){
            horse1 = hstr[s];
            horse1idx = s;
        }
    }
    hstr[horse1idx] = 0;
    
    int horse2 = hstr[0];
    int horse2idx = 0;
    for(int a = 1; a < N; a++){
        if(horse2 < hstr[a]){
            horse2 = hstr[a];
            horse2idx = a;
        }
    }
    
    int ans = horse1 - horse2;
    
    // Write an action using Console.WriteLine()
    // To debug: Console.Error.WriteLine("Debug messages...");

    Console.WriteLine(ans);
}

})


#328

posting your code isn’t really useful. Try instead to define this: “my code is not working”. Also, don’t hesitate to skim through this thread, which most probably holds the key to the issue in your code.


#329

The logic of your code shows that you didn’t understant what you were asked to output.

Can you rephrase here what you understand of the problem statement ?

And given these powers what shoudl you output ? 2 5 8 14 26 35


#330

Yes.Thank you.I have to output the difference between the two closest strengths not the difference between the two biggest strengths.


#331

Hi, I’ve already used sort() in PHP but it does not seems to take it into account…


#332

Got mine to work 100% with Python 3. Pull all input into a list, sorted it, created another list with all the differences then found the minimum.