online advertising

Sunday, November 30, 2014

UVa Problem 910 - TV game

Problem:

Please find the problem here.

Solution:

Typical path counting problem, just keep the path count on the node and iterates, just like in project Euler problem 15 (my solution).

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=851

#include "UVa910.h"

#include <iostream>
#include <vector>

using namespace std;

int UVa910()
{
    while (true)
    {
        // Step 1: Read Input
        int number_of_nodes;
        cin >> number_of_nodes;
        if (cin.eof())
        {
            break;
        }
        vector<vector<int> > adjacency_list;
        vector<bool> mode;
        adjacency_list.resize(number_of_nodes);
        mode.resize(number_of_nodes);
        for (int i = 0; i < number_of_nodes; i++)
        {            
            char from;
            char to1;
            char to2;
            char mode_char;
            cin >> from;
            cin >> to1;
            cin >> to2;
            cin >> mode_char;
            adjacency_list[from - 'A'].resize(2);
            adjacency_list[from - 'A'][0] = to1 - 'A';
            adjacency_list[from - 'A'][1] = to2 - 'A';
            mode[from - 'A'] = (mode_char == 'x');
        }
        int steps;
        cin >> steps;

        // Step 2: Dynamic programming
        vector<int> old_ways;
        vector<int> new_ways;
        old_ways.resize(number_of_nodes);
        new_ways.resize(number_of_nodes);

        for (int i = 0; i < number_of_nodes; i++)
        {
            old_ways[i] = 0;
        }
        old_ways[0] = 1;
        
        for (int s = 0; s < steps; s++)
        {
            for (int n = 0; n < number_of_nodes; n++)
            {
                new_ways[n] = 0;
            }
            for (int n = 0; n < number_of_nodes; n++)
            {
                new_ways[adjacency_list[n][0]] = new_ways[adjacency_list[n][0]] + old_ways[n];
                new_ways[adjacency_list[n][1]] = new_ways[adjacency_list[n][1]] + old_ways[n];
            }
            for (int n = 0; n < number_of_nodes; n++)
            {
                old_ways[n] = new_ways[n];
            }            
        }

        int win_ways = 0;
        for (int n = 0; n < number_of_nodes; n++)
        {
            if (mode[n])
            {
                win_ways += old_ways[n];
            }
        }
        cout << win_ways << endl;
    }

    return 0;
}

UVa Problem 10891 - Game of Sum

Problem:

Please find the problem here.

Solution:

Dynamic programming is applied here. The key is that part of an optimal strategy is also an optimal strategy, so we can build up the optimal strategies with increasing length.

The optimal strategy with just 1 element is deceptively simple. Just pick the value.

The optimal strategy for a subarray with k elements can have 2k - 1 choices. If we left anything for out opponent, he will choose the best strategy, so in that case we have already know what that strategy is, and therefore we know what is the end difference. Just choose the one with the best end difference, that is the optimal strategy.

With that, the code is easy. Note how to loop through the set of sub-sequences.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1832

#include "UVa10891.h"

// #define LOG

#include <iostream>
#include <vector>

using namespace std;

struct UVa10891_strategy
{
    int start_index;
    int end_index;
    int strategy_value;
};

int UVa10891()
{
    while (true)
    {
        // Step 1: Input
        int number_of_elements;
        cin >> number_of_elements;
        if (number_of_elements == 0)
        {
            break;
        }

        vector<int> elements;
        elements.resize(number_of_elements);
        for (int i = 0; i < number_of_elements; i++)
        {
            int element;
            cin >> element;
            elements[i] = element;
        }

        // Step 2: Pre compute running sum
        vector<int> element_sums;
        element_sums.resize(number_of_elements + 1);
        int element_sum = 0;
        for (int i = 0; i < number_of_elements; i++)
        {
            element_sums[i] = element_sum;
            element_sum += elements[i];
        }
        element_sums[number_of_elements] = element_sum;

        // element_sums[b + 1] - element_sums[a] = sum(i = a to b) elements[i]

        // Step 3: Dynamic programming
        vector<vector<UVa10891_strategy> > optimal_strategies;
        optimal_strategies.resize(number_of_elements);
        for (int start = 0; start < number_of_elements; start++)
        {
            optimal_strategies[start].resize(number_of_elements);
        }

        for (int length = 1; length <= number_of_elements; length++)
        {
            for (int start = 0; (start + length - 1) < number_of_elements; start++)
            {
                int end = start + length - 1;
                if (length == 1)
                {
                    // There is only one element - we have no choice but to pick this number
                    optimal_strategies[start][end].start_index = start;
                    optimal_strategies[start][end].end_index = start;
                    optimal_strategies[start][end].strategy_value = elements[start];
#ifdef LOG
                    cout << "optimal_strategies[" << start << "][" << end << "] = (" << optimal_strategies[start][end].start_index << ", " << optimal_strategies[start][end].end_index << ") = " << optimal_strategies[start][end].strategy_value << endl;
#endif
                }
                else
                {
                    optimal_strategies[start][end].start_index = start;
                    optimal_strategies[start][end].end_index = end;
                    optimal_strategies[start][end].strategy_value = element_sums[end + 1] - element_sums[start];
                    for (int p = start; p < end; p++)
                    {
                        // Consider I am choosing [start, p]
                        int strategy_value = element_sums[p + 1] - element_sums[start];                        
                        UVa10891_strategy opponent_strategy = optimal_strategies[p + 1][end];
                        strategy_value -= opponent_strategy.strategy_value;
                        if (strategy_value > optimal_strategies[start][end].strategy_value)
                        {
                            optimal_strategies[start][end].strategy_value = strategy_value;
                            optimal_strategies[start][end].start_index = start;
                            optimal_strategies[start][end].end_index = p;
                        }
                    }
                    for (int q = end; q > start; q--)
                    {
                        // Consider I am choosing [q, end]
                        int strategy_value = element_sums[end + 1] - element_sums[q];
                        UVa10891_strategy opponent_strategy = optimal_strategies[start][q - 1];
                        strategy_value -= opponent_strategy.strategy_value;
                        if (strategy_value > optimal_strategies[start][end].strategy_value)
                        {
                            optimal_strategies[start][end].strategy_value = strategy_value;
                            optimal_strategies[start][end].start_index = q;
                            optimal_strategies[start][end].end_index = end;
                        }
                    }
#ifdef LOG
                    cout << "optimal_strategies[" << start << "][" << end << "] = (" << optimal_strategies[start][end].start_index << ", " << optimal_strategies[start][end].end_index << ") = " << optimal_strategies[start][end].strategy_value << endl;
#endif
                }
            }
#ifdef LOG
            cout << endl;
#endif
        }

        UVa10891_strategy optimal_strategy = optimal_strategies[0][number_of_elements - 1];
        cout << optimal_strategy.strategy_value << endl;
    }
    return 0;
}

UVa Problem 10243 - Fire! Fire!! Fire!!!

Problem:

Please find the problem here.

Solution:

This is a minimum vertex cover on tree problem. .

For each node v, we wanted to compute two counts. The minimum vertex cover size for the subtree rooted at v, and the minimum vertex cover size for the subtree root at v if v has to be in the cover.

Pick an arbitrary node as root, we have two cases, for leaf and for internal nodes. For leaf, this is easy, if the leaf has a parent, and the parent is in the cover, then the leaf is not in the cover, otherwise the leaf has to be in the cover.

For internal node, there are two possibilities, either it is in the cover or not. If it is in the cover, then all the children node can be free to include itself in the cover or not. Otherwise, all children must be in the cover.

That's the crux of the algorithm, the code is short, dfs is used to determine if the node is a leaf or not, recurrence relation applied on stack unwind.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1184

#include "UVa10243.h"

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

pair<int, int> UVa10243_dfs(int parent, int current, vector<vector<int> >& adjacency_list)
{
    vector<pair<int, int> > results;
    for (vector<int>::iterator ai = adjacency_list[current].begin(); ai != adjacency_list[current].end(); ai++)
    {
        if (*ai != parent)
        {
            results.push_back(UVa10243_dfs(current, *ai, adjacency_list));
        }
    }

    if (results.size() == 0)
    {
        // Leaf case
        if (parent != -1)
        {
            return pair<int, int>(0, 1);
        }
        else
        {
            return pair<int, int>(1, 1);
        }
    }
    else
    {
        int free_sum = 0;
        int force_sum = 0;
        for (vector<pair<int, int> >::iterator ri = results.begin(); ri != results.end(); ri++)
        {
            free_sum += ri->first;
            force_sum += ri->second;
        }

        int selected_result = 1 + free_sum;     
        int not_selected_result = force_sum; 

        return pair<int, int>(min(selected_result, not_selected_result), selected_result);
    }
}

int UVa10243()
{
    while (true)
    {
        // Step 1: Read input
        int number_of_galleries;
        cin >> number_of_galleries;
        if (number_of_galleries == 0)
        {
            break;
        }
        vector<vector<int> > adjacency_list;
        adjacency_list.resize(number_of_galleries);
        for (int i = 0; i < number_of_galleries; i++)
        {
            int number_of_adjacent_galleries;
            cin >> number_of_adjacent_galleries;
            adjacency_list[i].resize(number_of_adjacent_galleries);
            for (int a = 0; a < number_of_adjacent_galleries; a++)
            {
                int adjacent_gallery;
                cin >> adjacent_gallery;
                adjacency_list[i][a] = adjacent_gallery - 1;
            }
        }

        // Step 2: dfs for the answer
        pair<int, int> result = UVa10243_dfs(-1, 0, adjacency_list);
        cout << result.first << endl;
    }

    return 0;
}

UVa Problem 590 - Always on the run

Problem:

Please find the problem here.

Solution:

This is a variation of the Bellman Ford algorithm for graph shortest path. Just keep track of the minimum cost of reaching a certain city on certain day, that's it.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=531

// #define LOG

#include "UVa590.h"

#include <iostream>
#include <vector>

using namespace std;

int UVa590()
{
    int test_case_number = 0;
    while (true)
    {
        test_case_number++;
        int number_of_cities, number_of_flights;
        cin >> number_of_cities;
        cin >> number_of_flights;
        if ((number_of_cities == 0) && (number_of_flights == 0))
        {
            break;
        }

        // Step 1: Allocation
        vector<vector<vector<int> > > flight_schedules;
        flight_schedules.resize(number_of_cities);
        for (int src = 0; src < number_of_cities; src++)
        {
            flight_schedules[src].resize(number_of_cities);
        }

        // Step 2: Read inputs
        for (int src = 0; src < number_of_cities; src++)
        {
            for (int dst = 0; dst < number_of_cities; dst++)
            {
                if (src != dst)
                {
                    int period;
                    cin >> period;
                    flight_schedules[src][dst].resize(period);
                    for (int p = 0; p < period; p++)
                    {
                        cin >> flight_schedules[src][dst][p];
                    }
                }
            }
        }

        // Step 3: Bellman-ford
        vector<int> old_cost;
        vector<bool> old_reachable;
        vector<int> new_cost;
        vector<bool> new_reachable;
        old_cost.resize(number_of_cities);
        new_cost.resize(number_of_cities);
        old_reachable.resize(number_of_cities);
        new_reachable.resize(number_of_cities);

        // Step 3.1: Initialize old_cost to be 0, only cities 0 is reachable
        for (int c = 0; c < number_of_cities; c++)
        {
            old_cost[c] = 0;
            old_reachable[c] = (c == 0);
        }
        
        // Step 3.2: Relaxation
        for (int k = 0; k < number_of_flights; k++)
        {
            for (int c = 0; c < number_of_cities; c++)
            {
                new_reachable[c] = false;
            }

            for (int dst = 0; dst < number_of_cities; dst++)
            {
                bool first = true;
                for (int src = 0; src < number_of_cities; src++)
                {
                    if (old_reachable[src] && src != dst)
                    {
                        int period = flight_schedules[src][dst].size();
                        int day_in_period = k % period;
                        int cost = flight_schedules[src][dst][day_in_period];
                        if (cost > 0)
                        {
                            new_reachable[dst] = true;
                            if (first)
                            {
                                new_cost[dst] = old_cost[src] + cost;
                                first = false;
                            }
                            else
                            {
                                new_cost[dst] = min(new_cost[dst], old_cost[src] + cost);
                            }
                        }
                    }
                }
            }

            // Copy new to old
            for (int c = 0; c < number_of_cities; c++)
            {
                old_cost[c] = new_cost[c];
                old_reachable[c] = new_reachable[c];
            }
#ifdef LOG
            cout << "On day " << k << " we have: ";
            for (int c = 0; c < number_of_cities; c++)
            {
                if (old_reachable[c])
                {
                    cout << old_cost[c] << " ";
                }
                else
                {
                    cout << "X" << " ";
                }
            }
            cout << endl;
#endif
        }

        // Step 4: Output
        cout << "Scenario #" << test_case_number << endl;
        if (old_reachable[number_of_cities - 1])
        {
            cout << "The best flight costs " << old_cost[number_of_cities - 1] << "." << endl;
        }
        else
        {
            cout << "No flight possible." << endl;
        }

        cout << endl;
    }
    return 0;
}

UVa Problem 10651 - Pebble Solitaire

Problem:

Please find the problem here.

Solution:

By modeling the game states as a graph, we can easily BFS the graph to find out all reachable states, and keep track with the state with minimum pebble count.

This one is NOT dynamic programming either. But I did use bitmask to make game state representation easy.

Code:


#include "stdafx.h"

// http://uva.onlinejudge.org/external/106/10651.html

#include "UVa10651.h"

#include <iostream>
#include <queue>

using namespace std;

int read_input()
{
    int game = 0;
    int bit = 1 << 11;
    for (int p = 0; p < 12; p++)
    {
        char c = cin.get();
        if (c == 'o')
        {
            game = game | bit;
        }
        bit = bit >> 1;
    }

    return game;
}

int UVa10651()
{
    int number_of_test_case;
    cin >> number_of_test_case;
    for (int c = 0; c < number_of_test_case; c++)
    {
        cin.get(); // eliminate the endline
        int game = read_input();
        bool enqueued[4096];
        queue<int> bfs_queue;
        for (int i = 0; i < 4096; i++)
        {
            enqueued[i] = false;
        }

        bfs_queue.push(game);
        enqueued[game] = true;

        int min_piece = 13; // there are at most 12 pieces, so this is basically infinitely

        while (!bfs_queue.empty())
        {
            int current = bfs_queue.front();
            bfs_queue.pop();
            int num_piece = 0;
            for (int p = 0; p < 12; p++)
            {
                if ((current & (1 << p)) != 0)
                {
                    num_piece++;
                }
            }
            min_piece = min(min_piece, num_piece);

            for (int p = 11; p >= 2; p--)
            {
                int m1 = 1 << p;
                int m2 = 1 << (p - 1);
                int m3 = 1 << (p - 2);

                // 1 1 0 case
                if (((current & m1) != 0) && ((current & m2) != 0) && ((current & m3) == 0))
                {
                    // 0 0 1
                    int new_game = current - m1 - m2 + m3;
                    if (!enqueued[new_game])
                    {
                        bfs_queue.push(new_game);
                        enqueued[new_game] = true;
                    }
                }

                // 0 1 1 case
                if (((current & m1) == 0) && ((current & m2) != 0) && ((current & m3) != 0))
                {
                    // 1 0 0
                    int new_game = current + m1 - m2 - m3;
                    if (!enqueued[new_game])
                    {
                        bfs_queue.push(new_game);
                        enqueued[new_game] = true;
                    }
                }
            }
        }

        cout << min_piece << endl;
    }

    return 0;
}