Velocity Reviews > Qsort-ing structures

# Qsort-ing structures

Albert
Guest
Posts: n/a

 02-19-2009
Hi:

I did a 4-hour programming contest this morning-early afternoon and I
had the following problem which I'll put in a nutshell, hopefully
that's enough to get even the vaguest idea as to what my code (when I
post it) was to intentionally do

--
You love playing Space Invaders. It's where ONE row of enemy bots are
on the top of the screen. You're on the bottom and may move only
horizontally. When you fire, you fire straight up till the bullet
destroys an enemy. You love the game so much that you stay all night
playing it. Therefore, you eventually get to the last and hardest
level. In this level, some of the screen is covered with polygons. If
the polygon happens to cover a particular column, firing at that
column won't do anything. So if the input tells you how wide and how
tall the screen is (I believe it was from 3 -> 10^7 for both
dimensions) and you assume that the whole top row is covered with
enemies, and in the input you're given the number of polygons and the
points of the corners of them, work out how many enemies you can
--

What I ended up doing was creating a struct representing a polygon. It
stored the number of points needed to describe the polygon (which was
part of the input data), it had an array of all the x coordinate
values inputted for this particular polygon and stored also the
smallest and largest x value in the array. The reason I didn't store
the y coordinate is because it's not needed in my algorithm (which I
believe is correct, would have been fast enough had I managed to code
it properly...).

Once you've stored all the input into an array of ships (I declared my
type as struct ship {...} ships [10^5 + 2] you sort the ships[] from
ship with the lowest x coordinate to the highest (ie by the ship's sx
[smallest x] increasing).

Then, essentially you sweep from the leftmost ship to the rightmost
ship. You find the difference of each ship's smallest and largest x
coordinate and subtract it from the variable, nfire (the number of
enemies you can destroy which starts off as the width inputted) and at
the end of the algorithm you output nfire.

The catch is when one ship is in front of another. Or, one ship's x
coordinate is in between another ship's smallest and largest x
coordinate. In this case, subtracting differences of smallest and
largest values from nfire wouldn't work because there will surely be
test cases where the ships 'overlap'. So - that's why I wantED to sort
my ships array. Continually searching through each ship for similar x
coordinates would timeout. A maximum of 10^5 ships can be described
and such an algorithm would take O(nships^2) which is unusable,
considering the assumption that a computer can process approximately
10^8 (but really it should be 3 * 10^8 but we like powers of ten)
instructions per second (and the time limit in most problems in this
olympiad are 1 second). So I thought the inbuilt qsort() would work
but I couldn't get it to work.

Let's simplify the problem before I get the full problem statement
again (can't access it outside the competition times anymore until
sometime) and my code which I left saved on the school network.

struct ship {
int sx;
} ships[10^5];

fscanf()....//into ships.sx

qsort(ships, 10^5, //comparison function//);

How do I get qsort to sort the array of structures accordign to sx?

Thanks
Albert

CBFalconer
Guest
Posts: n/a

 02-21-2009
Gordon Burditt wrote:
>
>> Once you've stored all the input into an array of ships (I
>> declared my type as struct ship {...} ships [10^5 + 2] you
>> sort the ships[] from ship with the lowest x coordinate to the
>> highest (ie by the ship's sx [smallest x] increasing).

>
> You do realize, don't you, that 10^5 as a C expression is not
> 10000 but a much smaller number? ^ is not an exponentiation
> operator in C. If you declared your array as somestruct[10^5],
> you're going to have a massive array overflow if you read in
> 10000 data points.

Who, may I ask, is 'you'?

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>

Albert
Guest
Posts: n/a

 02-28-2009
I wrote:
> Let's simplify the problem before I get the full problem statement
> again...[M]y code [was] saved on the school network*
> [snip]

The 'full problem statement' and the code which I have since typed up

Note that the code currently deals with the input only. I've been
trying to divide this program into several functions and I'm trying to
get the design right for now.
I've been fiddling around with header files and #include's; I can't
get the files to all compile because I don't really understand how all
these declartions work across multiple files. Could you please suggest
as to how to split the current source code into files and how to
#include them in each of the files?

@Richard: Thanks for the code; I got three out of 20 test cases
correct without a sort (and that O(n) algorithm has been putting me
off lately) since I had the correct algorithm, but strictly given non-
overlapping polygons. I was expecting to have a problem in coming up
with slow algorithms but instead I couldn't get a sort to work for a
correct AND a O(nlog(n)) algorithm!

@Burditt: Actually I didn't realise that during the contest. I think
that's why my results said (for around the first 10 cases) my program
generated either the incorrect answer or that it crashed...

@CBFalconer: Is that a rhetorical question?

*I saved my source files along with a temp copy of Dev-cpp portable in
the C:\ during the contest; logging off automatically wiped (and
wipes) any changes made on a school computer. I forgot to keep a copy
of my original source file on my USB

Thanks a lot,
Albert

Albert
Guest
Posts: n/a

 03-01-2009
When I try to compile each of the .c files at
- why?

Nate Eldredge
Guest
Posts: n/a

 03-01-2009
Albert <(E-Mail Removed)> writes:

> When I try to compile each of the .c files at
> - why?

main.c should #include "setup.h". The other files compile fine for me.

What errors do you get, what compiler are you using, and how are you
running it? There might be something wrong in that process.

Ike Naar
Guest
Posts: n/a

 03-01-2009
In article <(E-Mail Removed)>,
Albert <(E-Mail Removed)> wrote:
>When I try to compile each of the .c files at
>- why?

For me, it compiles fine (using gcc).
How do you compile it, and what errors do you get?

Albert
Guest
Posts: n/a

 03-01-2009
Nate Eldredge <(E-Mail Removed)> wrote:
> main.c should #include "setup.h". *The other files compile fine for me.

#include "setup.h"
to main.c

> What errors do you get what compiler are you using, and how are you

running it? There might be something wrong in that process.
gcc errchk.c
/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
reference to `WinMain@16'
collect2: ld returned 1 exit status

gcc main.c
C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x3a): undefined reference to
`open_file'
C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x4: undefined reference to
`setup'
collect2: ld returned 1 exit status

gcc setup.c
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0x5b): undefined reference
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xa2): undefined reference
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xb4): undefined reference
/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
reference to `WinMain@16'
collect2: ld returned 1 exit status

Nate Eldredge
Guest
Posts: n/a

 03-01-2009
Albert <(E-Mail Removed)> writes:

> Nate Eldredge <(E-Mail Removed)> wrote:
>> main.c should #include "setup.h". *The other files compile fine for me.

>
> #include "setup.h"
> to main.c
>
>> What errors do you get what compiler are you using, and how are you

> running it? There might be something wrong in that process.
> gcc errchk.c
> /mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
> reference to `WinMain@16'
> collect2: ld returned 1 exit status

Running `gcc' on a file without other arguments tries to compile that
file into its own program. None of those files constitutes a complete
program by itself, which is why this doesn't work.

Try

gcc -o myprog.exe errchk.c main.c setup.c

Ike Naar
Guest
Posts: n/a

 03-01-2009
In article <(E-Mail Removed)>,
Albert <(E-Mail Removed)> wrote:
>gcc errchk.c
>/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
>reference to `WinMain@16'
>collect2: ld returned 1 exit status
>
>gcc main.c
>C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x3a): undefined reference to
>`open_file'
>C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x4: undefined reference to
>`setup'
>collect2: ld returned 1 exit status
>
>gcc setup.c
>C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0x5b): undefined reference
>C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xa2): undefined reference
>C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xb4): undefined reference
>/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
>reference to `WinMain@16'
>collect2: ld returned 1 exit status

Try this:
gcc main.c errchk.c setup.c

Albert
Guest
Posts: n/a

 03-01-2009
Nate Eldredge wrote:
> Try
>
> gcc -o myprog.exe errchk.c main.c setup.c

I just did. Your suggestion worked. Thank you.