CodeForce 230 Dragon Fighting, Sorting without using array

Question

Problem: https://codeforces.com/problemset/problem/230/A

Kirito is stuck on a level of the MMORPG he is playing now. To move on in the game, he's got to defeat all \$n\$ dragons that live on this level. Kirito and the dragons have strength, which is represented by an integer. In the duel between two opponents the duel's outcome is determined by their strength. Initially, Kirito's strength equals \$s\$.

If Kirito starts duelling with the i-th (1 ≤ i ≤ n) dragon and Kirito's strength is not greater than the dragon's strength \$x_i\$, then Kirito loses the duel and dies. But if Kirito's strength is greater than the dragon's strength, then he defeats the dragon and gets a bonus strength increase by \$y_i\$.

Kirito can fight the dragons in any order. Determine whether he can move on to the next level of the game, that is, defeat all dragons without a single loss.

Input
The first line contains two space-separated integers \$s\$ and \$n\$ (\$1 ≤ s ≤ 10^4, 1 ≤ n ≤ 10^3\$).
Then \$n\$ lines follow: the i-th line contains space-separated integers \$x_i\$ and \$y_i\$ (\$1 ≤ x_i ≤ 10^4, 0 ≤ y_i ≤ 10^4\$) — the i-th dragon's strength and the bonus for defeating it.
Output
On a single line print "YES" (without the quotes), if Kirito can move on to the next level and print "NO" (without the quotes), if he can't.
Examples Input
2 2
1 99
100 0

Output
YES

Input
10 1
100 100

Output
NO

Note:
In the first sample Kirito's strength initially equals 2. As the first dragon's strength is less than 2, Kirito can fight it and defeat it. After that he gets the bonus and his strength increases to 2 + 99 = 101. Now he can defeat the second dragon and move on to the next level.

In the second sample Kirito's strength is too small to defeat the only dragon and win.

I have used array to solve the problem.

What I have tried[accepted but I didn't like my solution]:

#include<stdio.h>
int main(void)
{
    int i=0, j=0, k=0, l=0, count=0;
    int myStrength, testCase;
    int dragonStrength[1000], killingBonus[1000];
    scanf("%d%d", &myStrength, &testCase);

for(k=0; k<testCase; k++){
    scanf("%d%d", &dragonStrength[k], &killingBonus[k]);
}
    while(l<testCase){ 
            i=0, j=0;

        while(i<testCase && j<testCase){
        if(myStrength>dragonStrength[j] && dragonStrength[j]!=-1){
         myStrength = myStrength + killingBonus[j];
         dragonStrength[j] = -1;
         count++;
        }
        i++;
        j++;
        }
        l++;
    }

    if(count==testCase){  
        printf("YES");
    }else{
    printf("NO");
    }
    return 0;
}

I want to solve it without using array.

Answer 1

There are many things besides properly formatting the code that would improve it.

Complexity

The function main() is too complex (does too much). This isn't clear in this program because it is simple, but as programs grow in size the use of main() should be limited to calling functions that parse the command line, calling functions that set up for processing, calling functions that execute the desired function of the program, and calling functions to clean up after the main portion of the program.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

There are at least 2 possible functions in main().

• Get the user input
• Sort the input

    #define MAX_DUELS 1000

    void get_input(int *testCase, int *myStrength, int dragonStrength[MAX_DUELS],
        int killingBonus[MAX_DUELS])
    {
        scanf("%d%d", &myStrength, &testCase);

        int k = 0;
        for(k=0; k<testCase; k++){
            scanf("%d%d", &dragonStrength[k], &killingBonus[k]);
        }
    }

    int sort_input_and_count_wins(int testCase, int myStrength, int dragonStrength[MAX_DUELS],
        int killingBonus[MAX_DUELS])
    {
        int wins = 0;
        int l = 0;

        while(l < testCase){ 
            int i = 0;
            int j = 0;

             while(i < testCase && j < testCase){
                 if(myStrength>dragonStrength[j] && dragonStrength[j] != -1){
                     myStrength = myStrength + killingBonus[j];
                     dragonStrength[j] = -1;
                     wins++;
                 }
                 i++;
                 j++;
            }
            l++;
        }
        return wins;
    }

    int main(void)
    {
        int myStrength;
        int testCase;
        int dragonStrength[MAX_DUELS];
        int killingBonus[MAX_DUELS];

        get_input(&testCase, &myStrength, dragonStrength, killingBonus);
        int wins = sort_input_and_count_wins(testCase, myStrength, dragonStrength, killingBonus)
        if(wins == testCase){  
            puts("YES");
        }else{
            puts("NO");
        }
    }

Declare the Variables as Needed

In the original version of C back in the 1970s and 1980s variables had to be declared at the top of the function. That is no longer the case, and a recommended programming practice to declare the variable as needed. In C the language doesn't provide a default initialization of the variable so variables should be initialized as part of the declaration. For readability and maintainability each variable should be declared and initialized on its own line. See the declarations in the above example.

Magic Numbers

There are Magic Numbers in the main() function (1000), it might be better to create symbolic constants for them to make the code more readable and easier to maintain. These numbers may be used in many places and being able to change them by editing only one line makes maintenance easier.

Numeric constants in code are sometimes referred to as Magic Numbers, because there is no obvious meaning for them. There is a discussion of this on stackoverflow.

Horizontal Spacing

To make code more readable a common practice is to leave spaces between operands and operators in expressions.

Answer 2

Your code is too difficult to read. Please do some good indentation and formatting.

You can't solve this without storing whole information somewhere, because you can fight dragon in any order, so in each step you have to choose remaining dragon that has weakest hurdle but gives largest strength bonus.

Answer 3

You can separate input and processing.
And worst case, looking at the input values before the last one is read doesn't help you any:
The last dragon may be the only one Kirito initially dominates.

Then again, one tactic is to reap the low-hanging fruit:
If the dragon is inferior, just accumulate strength. If the dragon is too strong now, queue it up.
Queueing may be as simple as appending to a sequence.

Borrowing shamelessly from pacmaninbw's answer, checking input:

/** Establish strength and non-trivial dragons.
 *  Return number thereof. */
static int
get_dragons(int *strength, 
    int dragonStrength[MAX_DUELS], int killingBonus[MAX_DUELS])
{
    int myStrength, nDragons = 0, significant = 0;
    if (NULL == strength || NULL == dragonStrength || NULL == killingBonus
        || scanf("%d%d", &myStrength, &nDragons) < 2
        || myStrength < 0 || nDragons <= 0 || MAX_DUELS < nDragons) {
        if (NULL != strength)
            *strength = -1;
        return 0;
    }
    myStrength += *strength;
    while (0 <= --nDragons) {
        int bonus;
        if (scanf("%d%d", dragonStrength + significant, &bonus) < 2
            || bonus < 0) {
            return 0;
        }
        if (myStrength <= dragonStrength[significant]) {
            killingBonus[significant++] = bonus;
        } else
            myStrength += bonus;
    }
    *strength = myStrength;
    return significant;
}

(Single Responsibility holds weight, cunning wording significant/non-trivial dragons notwithstanding: there's a tradeoff with computer resource requirements.)
Note the similarity between putting the next item somewhere if it is no less than strength and putting the next item somewhere if it is less than strength, somewhere else otherwise:
Handling dragons that way is similar to "quicksort"s partition using Kirito's ever increasing strength as the single pivot.
Queueing may advance to a respectable implementation of a priority queue.

Choice of mechanism depends on many things, starting with What's available?
Not that much, given implementation in C:
I might skip implementing queue (a circular buffer of capacity \$n\$ should do) in favour of collecting non-dominated dragons, optionally "min-heapifying" them, and starting over.

#include <stdbool.h>

/** Starting at strength, eliminate weaker dragons accumulating their bonus. 
 * Return "all defeated". */
static bool
defeat_dragons(int strength, int dragons, int tenacity[], int bonus[])
{
    while (0 < dragons) {
        // insert optionally moving weak dragons to the front here
        int obstinate = 0;
        for (int i = 0 ; i < dragons ; i++) {
            if (tenacity[i] < strength) {
                strength += bonus[i];
            } else // if (obstinate < i) (mind obstinate++)
            {
                tenacity[obstinate] = tenacity[i];
                bonus[obstinate++] = bonus[i];
            }
        }
        if (obstinate == dragons) {  // none defeated
            return false;
        }
        dragons = obstinate;
    }
    return true;
}

(Your i and j stay in lockstep: Get rid of (at least) one.)