Gaming Array, by HackerRank
Problem statement: https://www.hackerrank.com/challenges/an-interesting-game-1. Given the constraints of 10^5, we're likely either looking for a linear solution or worst case an NLogN. I decided to go with the latter. For that there are multiple ways of doing it (sorting strategies), the one I picked is the following:
- Build a Heap
- Add the elements of the array to the heap, descending order
- In addition to the element, have the index of the element in the heap
- When the game starts:
- Pick the latest from the heap (LogN)
- If less than the current min, that's a valid move, replace current min and change the current winner
- Do this until you get an index of zero (first element), hence all the elements are covered (N)
- Total execution time: NLogN
- Total space: N (heap)
Works well for the problem, code is below, have a great night folks!!! Marcelo
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
static void Main(String[] args)
{
int g = Convert.ToInt32(Console.ReadLine());
string[] result = new string[g];
for (int a0 = 0; a0 < g; a0++)
{
int n = Convert.ToInt32(Console.ReadLine());
string[] parts = Console.ReadLine().Split(' ');
PriorityQueue pq = new PriorityQueue(2 * n, true);
for (int i = 0; i < n; i++)
{
QueueItem qi = new QueueItem(Int64.Parse(parts[i]), i);
pq.Enqueue(qi, qi.value);
}
result[a0] = "ANDY";
int minIndex = Int32.MaxValue;
while (minIndex > 0)
{
QueueItem nqi = (QueueItem)pq.Dequeue();
if (nqi.index < minIndex)
{
minIndex = nqi.index;
result[a0] = (result[a0] == "ANDY") ? "BOB" : "ANDY";
}
}
}
for (int i = 0; i < g; i++)
{
Console.WriteLine(result[i]);
}
}
}
public class QueueItem
{
public long value = 0;
public int index = 0;
private QueueItem() { }
public QueueItem(long value,
int index)
{
this.value = value;
this.index = index;
}
}
/*By-the-book PriorityQueue*/
public class PriorityQueue
{
public struct HeapEntry
{
private object item;
private long priority;
public HeapEntry(object item, long priority)
{
this.item = item;
this.priority = priority;
}
public object Item
{
get
{
return item;
}
}
public long Priority
{
get
{
return priority;
}
}
}
private long count;
private long capacity;
private bool descending; //Means that the max element at the top
private HeapEntry[] heap;
public long Count
{
get
{
return this.count;
}
}
public PriorityQueue(long capacity, bool descending)
{
this.capacity = capacity;
this.descending = descending;
heap = new HeapEntry[this.capacity];
}
public object Dequeue()
{
object result = heap[0].Item;
count--;
trickleDown(0, heap[count]);
return result;
}
public void Enqueue(object item, long priority)
{
count++;
bubbleUp(count - 1, new HeapEntry(item, priority));
}
private void bubbleUp(long index, HeapEntry he)
{
long parent = (index - 1) / 2;
// note: (index > 0) means there is a parent
while (
(index > 0) &&
((this.descending && heap[parent].Priority < he.Priority) || (!this.descending && heap[parent].Priority > he.Priority))
)
{
heap[index] = heap[parent];
index = parent;
parent = (index - 1) / 2;
}
heap[index] = he;
}
private void trickleDown(long index, HeapEntry he)
{
long child = (index * 2) + 1;
while (child < count)
{
if (
((child + 1) < count) &&
((this.descending && heap[child].Priority < heap[child + 1].Priority) || (!this.descending && heap[child].Priority > heap[child + 1].Priority))
)
{
child++;
}
heap[index] = heap[child];
index = child;
child = (index * 2) + 1;
}
bubbleUp(index, he);
}
}
Thanks for another nice problem, Marcelo! I used a following observation - the winner is determined by the number of "peaks" starting from index 0 where every next "peak" is greater than a previous one, since at every turn one of them is removed. So if the number of "peaks" is odd - Bob wins, otherwise - Andy wins.
ReplyDeleteNow, we just need to count these "peaks" and we can do this by going from left to right and making a note of every new maximum value.
#include
using namespace std;
int main() {
int g; cin >> g;
while (g--) {
int n; cin >> n;
int count = 0;
int max_so_far = 0;
for (int i = 0; i < n; ++i) {
int num; cin >> num;
if (num > max_so_far) {
max_so_far = num;
count += 1;
}
}
cout << (count % 2 == 1 ? "BOB" : "ANDY") << endl;
}
return 0;
}
http://ideone.com/pVjB67
This implementation has O(n) time and O(1) space complexity.
:) brilliant!!!!!
ReplyDelete