editorial_28350_780x0_proportion

TopCoder SRM 500 Div 2 Easy

I have solved another TopCoder problem. I am starting to get better at these as this one took a lot less time to understand. I ended up getting my first attempt wrong on some test cases and couldn’t figure out why at the time. I think it was because I did the first attempt in cpp and spent most of the time trying to remember how to use it. Think I will stick with Java for the rest of them as this will allow me to focus on coding the solution and keep me from tripping up on the language. Here’s the problem statement:

Dmitry likes TopCoder Single Round Matches. Once, he registered for an SRM and was waiting for the coding phase to begin. To entertain himself while waiting, he decided to play the following game.

He makes a pile of cards, and on each card, he writes the number of an SRM in which he has competed. No two cards contain the same number. He then takes turns until the pile is empty. Each turn consists of the following sequence of actions:
Dmitry chooses an arbitrary card from the pile. Let A be the number written on this card.
The card with number A is removed from the pile.
If the pile contains a card with number A-1, that card is removed from the pile.
If the pile contains a card with number A+1, that card is removed from the pile.
The game is finished when the pile becomes empty. It’s fun to play the game, so Dmitry wants to spend as much time as possible playing it.

You are given a int[] cards containing the numbers written on the cards in the pile before the start of the game. Return the largest possible number of turns in which Dmitry can finish the game.

Constraints
– cards will contain between 1 and 50 elements, inclusive.
– Each element of cards will be between 1 and 499, inclusive.
– All elements of cards will be distinct.

So basically we needed to play the game of removing a card and any other cards with a value within 1 of the value of the current card as long as possible. The best way to play the game longer is to limit the amount of cards that you remove each turn.  The most you can remove is 3 and the least is 1, but if there are 3 cards that are within 1 of each other, say with values {1,2,3}, the least you can remove is 2 cards ( either 1 and 2, or 2 and 3 ).  So it is best to always shoot for this case of removing either 1 or 2 cards.  To do this, we can sort the array and always test the beginning as this will always be the least valued card in the deck.  We would either just remove the first card, or the first and the second at most.

First attempt: 1h

#include <vector>
#include <algorithm>

using namespace std;

class SRMCards {
public:
    int maxTurns(vector<int> cards) {
        int turns = 0;

        // sort the array
        sort(cards.begin(), cards.end());
        auto it = cards.begin();

        // run through to see how long we can play
        while (!cards.empty()) {
            if ((it + 1) != cards.end() && *(it + 1) - *it == 1) {
                cards.erase(it + 1);
            }

            ++it;
            ++turns;
            cards.erase(cards.begin());
        }

        return turns;
    }
};

This was my initial approach. I spent the majority of the time fumbling over the c++ language. I forgot how long it’s been since I have actually done any coding in this language. This failed some of the test case and I couldn’t figure out why. I thought it was because I had misunderstood the problem statement so I looked at the editorial. Low and behold my understanding of the statement was correct, but I had overcomplicated the implementation. I think this is partially because I hadn’t really used vectors ever in c++ and I just kind of felt it out. Here’s my second attempt:

Second attempt: 20m

import java.util.Arrays;

public class SRMCards {
    public static int maxTurns(int[] cards) {
        int turns = 0;
        Arrays.sort(cards);

        for (int i = 0; i < cards.length; i++) {
            if (i < cards.length - 1 && cards[i+1] - 1 == cards[i]) {
                ++turns;
                ++i;
            }

            else
                ++turns;
        }

        return turns;
    }
}

I went back to java and knocked out a second attempt. This time instead of removing items from the array, I just incremented the counter to move an extra position. This made for much a more concise implementation.

Third attempt: 1m

import java.util.Arrays;

public class SRMCards {
    public static int maxTurns(int[] cards) {
        int turns = 0;
        Arrays.sort(cards);
        for (int i = 0; i < cards.length; ++i) {
            if (i < cards.length - 1 && cards[i+1] - cards[i] == 1) {
                ++turns;
                ++i;
            }
            else
                ++turns;
        }

        return turns;
    }
}

Having fully understood the problem and implementation, the third attempt only took me 1 minute to code! Not a bad improvement, I am looking forward to the next practice problem. Actually today I am hoping to get my chance to participate in my first live SRM!

Published by

Duke Deus

Deus Duke is a mobile software developer in the Bay Area. Also interested in game development, the occasional bar, and all around good times.

Leave a Reply