shoumikhin
BAN USER#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
struct Cell
{
int x, y;
char marker;
};
bool is_digit(char c)
{
return '0' <= c && c <= '9';
}
void clasterize(vector<vector<char>> &map)
{
char marker = 'A';
auto compare = [](pair<int, Cell> const &lhs, pair<int, Cell> const &rhs){ return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second.x < rhs.second.x) || (lhs.first == rhs.first && lhs.second.x == rhs.second.x && lhs.second.y < rhs.second.y); };
set<pair<int, Cell>, decltype(compare)> queue(compare);
for (auto i = 0; i < map.size(); ++i)
for (auto j = 0; j < map[i].size(); ++j)
{
bool top, bottom, right, left;
top = bottom = right = left = false;
if (0 == i || (i > 0 && map[i-1][j] > map[i][j]))
top = true;
if (map.size()-1 == i || (i < map.size()-1 && map[i+1][j] > map[i][j]))
bottom = true;
if (0 == j || (j > 0 && map[i][j-1] > map[i][j]))
left = true;
if (map[i].size()-1 == j || (j < map[i].size()-1 && map[i][j+1] > map[i][j]))
right = true;
if (top && bottom && left && right)
queue.insert(make_pair(map[i][j], Cell({.x = i, .y = j, .marker = marker++})));
}
while (!queue.empty())
{
auto cell = (*queue.begin()).second;
queue.erase(queue.begin());
if (is_digit(map[cell.x][cell.y]))
{
map[cell.x][cell.y] = cell.marker;
if (cell.x > 0 && is_digit(map[cell.x-1][cell.y]))
queue.insert(make_pair(map[cell.x-1][cell.y], Cell({.x = cell.x-1, .y = cell.y, .marker = cell.marker})));
if (cell.x < map.size()-1 && is_digit(map[cell.x+1][cell.y]))
queue.insert(make_pair(map[cell.x+1][cell.y], Cell({.x = cell.x+1, .y = cell.y, .marker = cell.marker})));
if (cell.y > 0 && is_digit(map[cell.x][cell.y-1]))
queue.insert(make_pair(map[cell.x][cell.y-1], Cell({.x = cell.x, .y = cell.y-1, .marker = cell.marker})));
if (cell.y < map[cell.x].size()-1 && is_digit(map[cell.x][cell.y+1]))
queue.insert(make_pair(map[cell.x][cell.y+1], Cell({.x = cell.x, .y = cell.y+1, .marker = cell.marker})));
}
}
}
int main()
{
vector<vector<char>> map =
{
{'1', '0', '2', '5', '8'},
{'2', '3', '4', '7', '9'},
{'3', '5', '7', '8', '9'},
{'1', '2', '5', '4', '2'},
{'3', '3', '5', '2', '1'}
};
clasterize(map);
for (auto v : map)
{
for (auto c : v)
cout << c << " ";
cout << endl;
}
return 0;
}
Thank you.
There is a bug which I corrected but the post did not update for some reason.
In count_common in for loop with inner if condition there should be an else branch doing simple break when elements are not equal.
This is not correct enough, since it does not consider a case when a palindrome is formed with an odd number of nodes.
- shoumikhin November 30, 2015struct ListNode
{
int data;
ListNode *next;
};
int count_common(ListNode *a, ListNode *b)
{
int ret = 0;
for (; a && b; a = a->next, b = b->next)
if (a->data == b->data)
++ret;
else
break;
return ret;
}
int max_palindrome(ListNode *head)
{
int ret = 0;
ListNode *p = nullptr, *q = head;
while (q)
{
auto t = q->next;
q->next = p;
ret = max(ret, 2 * count_common(p, t) + 1);
ret = max(ret, 2 * count_common(q, t));
p = q;
q = t;
}
return ret;
}
int main()
{
auto head = new ListNode({.data = 1}), p = head;
p->next = new ListNode({.data = 2}); p = p->next;
p->next = new ListNode({.data = 1}); p = p->next;
p->next = new ListNode({.data = 2}); p = p->next;
p->next = new ListNode({.data = 1}); p = p->next;
p->next = nullptr;
cout << max_palindrome(head) << endl; //5
return 0;
}
I guess so.
Simplest example, given a row of balloons with coins for them:
8, 5, 6, 9, 3, 0, 2, 4, 1, 7
burst 0, get 3*0*2 coins -> 8, 5, 6, 9, 3, 2, 4, 1, 7
burst 1, get 4*1*7 coins -> 8, 5, 6, 9, 3, 2, 4, 7
burst 2, get 3*2*4 coins -> 8, 5, 6, 9, 3, 4, 7
burst 3, get 3*2*4 coins -> 8, 5, 6, 9, 4, 7
burst 4, get 9*4*7 coins -> 8, 5, 6, 9, 7
burst 5, get 8*5*6 coins -> 8, 6, 9, 7
burst 6, get 8*6*9 coins -> 8, 9, 7
burst 9, get 8*9*7 coins -> 8, 7
burst 7, get 8*7*1 coins -> 8
burst 8, get 1*8*1 coins
That's an optimal strategy and you can get (summing up) 1652 coins with it.
At each step you choose the least local minimum among all local minimums.
That helps make the balloons with higher value adjanced, and so gain bigger product later.
More interesting example:
1, 2, 3, 4, 5, 6, 7, 8, 9
There's no local minimum, so you should choose a triple with maximum product and burst the middle balloon:
burst 8, get 7*8*9 coins -> 1, 2, 3, 4, 5, 6, 7, 9
burst 7, get 6*7*9 coins -> 1, 2, 3, 4, 5, 6, 9
burst 6, get 5*6*9 coins -> 1, 2, 3, 4, 5, 9
burst 5, get 4*5*9 coins -> 1, 2, 3, 4, 9
burst 4, get 3*4*9 coins -> 1, 2, 3, 9
burst 3, get 2*3*9 coins -> 1, 2, 9
burst 2, get 1*2*9 coins -> 1, 9
burst 1, get 1*1*9 coins -> 9
burst 9, get 1*9*1 coins
That will bring you 1530 coins total.
Unfortunately, any dynamic programming solution will assume trying all combinations of inflated on deflated balloons, and there're 2^N combinations. Though, a brute force approach would require O(N!) operations, so O(2^N) is still an improvement. With a downside of O(2^N) memory, of course.
For this problem you'll need a more clever way. We need to look at the least local minimum and burst it. Plus some corner cases when it happens to appear at one of the ends of the balloon row.
It's a kind of shortest path problem, so use BFS and a priority queue.
- shoumikhin December 11, 2015At the beginning traverse the map and find all sinks. Push them to the priority queue, where primary priority is land's height at that sink. You should also assign a marker to any cell you push to the queue. Initially just increment your marker starting with 'A' and assign it to each sink you find.
The loop until queue is empty. Pop a cell on the top of the queue and if the land corresponding to that cell has not being marked, mark it with the cell's marker and add to the queue any unmarked neighbors.
To count the number of As, Bs, etc. just count what marker you're assigning to an unmarked land once you've popped the next cell from the queue.