moizik
BAN USERI think you have flaw in your solution.
consider next example : 1189119999 and k = 5;
The correct answer will be 9999981111.
Your algorithm on step c will get all indexes of '9' {3,6,7,8,9} , on step d indexes of 5 lower digits while skipping '9'th {0,1,2,4,5}.
Then you starting swap digits in ascending order with 9th from right to left.
It will give you 9998991111.
The problem is with last 9. After 4 swap operation and before last one your number looks like 99 "89" 991111, ( i put in quotes the only unswapped digits ). The correct answer achieved by swap 8 with already used in swap '9'.
The solution i think is to remember how much digits you skipped in step d, lets say it x digits, and after k-x swap operations, do next x swaps with the already swapped '9'th from right to left
EDIT :
No, my solution won't work too.
consider 191899 k = 3
after two swaps 999811 , it is allready maximum , now my solution will do last swap and will make it 998911.
We can solve it if we will check that we are not swapping 9 to lower index, but i am not sure i see all the problems with this algorithm,
EDIT 2:
It seems this greedy algorithm is working.
code :
#include "kswap.h"
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
using namespace std;
class comp {
public:
bool operator() (pair<int, int> a, pair <int,int> b)
{
if (a.first == b.first)
{
return a.second > b.second;
}
return a.first > b.first;
}
};
vector<int> getIndexesOfCurrentDigit(int curr_digit, int k, vector <int> *vec)
{
vector <int> indexes;
for (int i = (int)vec->size() -1 ; i > 0 ; i--)
{
if ( (int)indexes.size() == k )
{
return indexes;
}
if ((*vec)[i] == curr_digit)
{
indexes.push_back(i);
}
}
return indexes;
}
vector<pair<int,int>> getHeapOfLowerDigits(int curr_digit, int size, int k, vector <int> *vec ,int *x)
{
vector <pair<int,int>> heap;
for (int i = 0; i < vec->size(); i++)
{
if (heap.size() == size)
{
make_heap(heap.begin(),heap.end(), comp());
return heap;
}
if ((*vec)[i] <= curr_digit)
{
if ((*vec)[i] < curr_digit)
{
heap.push_back(make_pair((*vec)[i],i));
}
else
{
(*x)++;
}
}
}
make_heap(heap.begin(),heap.end(), comp());
return heap;
}
void carefullSwap(vector<int> indexes, vector<pair<int,int>> heap, int curr_digit,int x, int *k, vector <int> *vec)
{
int high_digit_index, lower_digit_index = 0;
int swaps = 0;
int i = 0;
int size = (int)heap.size();
while(heap.empty() == false)
{
high_digit_index = indexes[i++];
lower_digit_index = heap.front().second;
pop_heap(heap.begin(), heap.end(), comp());
heap.pop_back();
//swap
if(lower_digit_index < high_digit_index )
{
int tmp = (*vec)[high_digit_index];
(*vec)[high_digit_index] = (*vec)[lower_digit_index];
(*vec)[lower_digit_index] = tmp;
swaps++;
}
if(swaps == (size - x) )
{
indexes = getIndexesOfCurrentDigit(curr_digit, *k, vec);
i = 0;
}
}
*k = *k - swaps;
}
void kswap (vector <int> * vec , int k)
{
for (int curr_digit = 9 ; curr_digit > 1 ; curr_digit--)
{
if (k == 0)
{
return;
}
int x = 0;
vector<int> indexes = getIndexesOfCurrentDigit(curr_digit, k, vec);
vector<pair<int,int>> heap = getHeapOfLowerDigits(curr_digit,(int)indexes.size(), k, vec , &x);
carefullSwap(indexes, heap, curr_digit, x, &k, vec);
}
}
Testing:
k - 2
input - 8799
output - 9987
k - 2
input - 7899
output - 9987
k - 2
input - 34155
output - 55143
k - 2
input - 12520
output - 52210
k - 3
input - 876959
output - 998657
k - 2
input - 1399
output - 9931
k - 5
input - 1189119999
output - 9999981111
k - 5
input - 191899
output - 999811
k - 350
input - 123456789098765432199998888777777266655
output - 999999888888777777776666655545433222110
k - 35
input - 123456789098765432199998888777777266655
output - 999999888888777777143216650775432266655
k - 9
input - 123456789098765432199998888777777266655
output - 999999888858765432143218760777777266655
Program ended with exit code: 0
EDIT 3 the last one.
No this solution doesn't work either. I got to conclusion you can't do it with greedy algorithm. You have to do some routines recursively
If someone could tell me how easily i can come to conclusion that some problem can't be solved greedy, i will appreciate it.
inhnnsoc , you are absolutely right. I think there a minor defect in a icomputational solution.
Score should start from zero every time we encounter a 'b' , this is how we can determine the longest sequence of consecutive 'a' .
So the algorythm should be
1. find first 'b'
2. from the next position after the first 'b', find the maximum continuous sub list of 'a'
3. if it is longer than prefix sequence (from start to first b) then reverse the first 'b' and the end of maximal subsequence of 'a'
here is correct code and results for your example
def maxswap(clist):
clen = len(clist)
i, j = 0, 0
while i < clen:
if clist[i] == 'b':
break
i += 1
if i == clen:
return [0, 0]
val = - i # first fix, initial val should represent length of starting
# 'a' sequence
rj = i
cval = 0
for j in range(i + 1, clen):
if clist[j] == 'a':
cval += 1
else:
cval = 0 # second fix , we should start over calculation
# when we see 'b'
if cval > val:
rj = j
val = cval
if rj == i:
return [0, 0]
return [i, rj]
print ( maxswap ( 'baaabaabbbbbb' ) )
print ( maxswap ( 'baabaaabbbbbb' ) )
output:
kirillmoizik$ python test.py
[0, 3]
[0, 6]
define array[100]
- moizik October 23, 2014run over data and for each entry lower than 100 set array[current_number] = 1
then run over data secondly and for every entry lookup if complementary number exist in array.
o(n) time
0(1) place