Sam’s Puzzle (Approximate) – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <utility>
using namespace std;
static default_random_engine dre;
static const unsigned max_moves = 500;
static unordered_map<unsigned, unsigned> n3_penalty;
static unordered_map<unsigned, pair<unsigned, unsigned>> n3_best_move;
class CField3
{
public:
static const unsigned n = 3;
vector<unsigned> vmap, vpos;
CField3() { vmap.resize(n*n); vpos.resize(n*n); }
void Set(unsigned pos, unsigned value)
{
vmap[pos] = value;
vpos[value] = pos;
}
static unsigned PenaltyBase(const vector<unsigned>& vmap)
{
unsigned penalty = 0;
for (unsigned i = 0; i < n; ++i)
{
for (unsigned j = 0; j < n; ++j)
{
unsigned x = vmap[i * n + j];
for (unsigned i1 = i + 1; i1 < n; ++i1)
{
if (vmap[i1 * n + j] < x) ++penalty;
}
for (unsigned j1 = j + 1; j1 < n; ++j1)
{
if (vmap[i * n + j1] < x) ++penalty;
}
}
}
return penalty;
}
static unsigned Hash3FromPos(const vector<unsigned>& vpos)
{
assert(vpos.size() == 9);
unsigned s = 0, m = 1;
for (unsigned i = 0; i < 9; ++i)
{
s += m * vpos[i];
m *= 9;
}
return s;
}
static unsigned Hash3FromMap(const vector<unsigned>& vmap)
{
static vector<unsigned> vs(9);
assert(vmap.size() == 9);
for (unsigned i = 0; i < 9; ++i)
{
vs[vmap[i]] = i;
}
return Hash3FromPos(vs);
}
unsigned Hash3() const { return Hash3FromPos(vpos); }
void SetFromHash3(unsigned h)
{
assert(n == 3);
for (unsigned i = 0; i < 9; ++i)
{
unsigned p = h % 9; h /= 9;
vpos[i] = p;
vmap[p] = i;
}
}
static const vector<unsigned>& GetMove3FromIndex(unsigned index)
{
static const vector<vector<unsigned>> vt{ { 0u, 0u, 3u },{ 0u, 0u, 2u },{ 0u, 1u, 2u },{ 1u, 0u, 2u },{ 1u, 1u, 2u } };
return vt[index];
}
void Rotate(unsigned i, unsigned j, unsigned k)
{
unsigned kh0 = k / 2, kh1 = (k + 1) / 2;
for (unsigned i1 = 0; i1 < kh0; ++i1)
{
for (unsigned j1 = 0; j1 < kh1; ++j1)
{
unsigned x = vmap[(i1 + i) * n + (j1 + j)];
Set((i1 + i) * n + (j1 + j), vmap[(k - j1 - 1 + i) * n + (i1 + j)]);
Set((k - j1 - 1 + i) * n + (i1 + j), vmap[(k - i1 - 1 + i) * n + (k - j1 - 1 + j)]);
Set((k - i1 - 1 + i) * n + (k - j1 - 1 + j), vmap[(j1 + i) * n + (k - i1 - 1 + j)]);
Set((j1 + i) * n + (k - i1 - 1 + j), x);
}
}
}
void Rotate(const vector<unsigned>& v)
{
assert(v.size() == 3);
Rotate(v[0], v[1], v[2]);
}
void RotateI(unsigned i, unsigned j, unsigned k)
{
unsigned kh0 = k / 2, kh1 = (k + 1) / 2;
for (unsigned i1 = 0; i1 < kh0; ++i1)
{
for (unsigned j1 = 0; j1 < kh1; ++j1)
{
unsigned x = vmap[(i1 + i) * n + (j1 + j)];
Set((i1 + i) * n + (j1 + j), vmap[(j1 + i) * n + (k - i1 - 1 + j)]);
Set((j1 + i) * n + (k - i1 - 1 + j), vmap[(k - i1 - 1 + i) * n + (k - j1 - 1 + j)]);
Set((k - i1 - 1 + i) * n + (k - j1 - 1 + j), vmap[(k - j1 - 1 + i) * n + (i1 + j)]);
Set((k - j1 - 1 + i) * n + (i1 + j), x);
}
}
}
void RotateI(const vector<unsigned>& v)
{
assert(v.size() == 3);
RotateI(v[0], v[1], v[2]);
}
static void BuildSolutionMap()
{
queue<unsigned> qh;
vector<unsigned> vmap(9);
for (unsigned i = 0; i < 9; ++i) vmap[i] = i;
for (; ;)
{
unsigned h = Hash3FromMap(vmap);
unsigned p = PenaltyBase(vmap);
n3_penalty[h] = p;
if (p == 0)
{
qh.push(h);
n3_best_move[h] = make_pair(0u, 0u);
}
if (!next_permutation(vmap.begin(), vmap.end()))
break;
}
CField3 f;
unsigned maxl = 0;
for (; !qh.empty(); )
{
unsigned h = qh.front(); qh.pop();
unsigned l = n3_best_move[h].first >> 3;
maxl = max(maxl, l);
f.SetFromHash3(h);
for (unsigned i = 0; i < 5; ++i)
{
f.RotateI(GetMove3FromIndex(i));
unsigned fh = f.Hash3();
if (n3_best_move.find(fh) == n3_best_move.end())
{
qh.push(fh);
n3_best_move[fh] = make_pair(((l + 1) << 3) + i, h);
}
f.Rotate(GetMove3FromIndex(i));
}
}
// cout << n3_best_move.size() << "\t" << maxl << endl;
}
};
class CField
{
public:
unsigned n;
vector<unsigned> vmap;
CField() : n(0) {}
CField(unsigned _n) : n(_n) { vmap.resize(n*n); }
void Set(unsigned pos, unsigned value) { vmap[pos] = value; }
void Read()
{
cin >> n;
vmap.resize(n*n);
for (unsigned i = 0; i < n * n; ++i)
{
int x;
cin >> x;
Set(i, x - 1);
}
AddCurrentPenalty();
}
static unsigned PenaltyBase(unsigned n, const vector<unsigned>& vmap)
{
unsigned penalty = 0;
for (unsigned i = 0; i < n; ++i)
{
for (unsigned j = 0; j < n; ++j)
{
unsigned x = vmap[i * n + j];
for (unsigned i1 = i + 1; i1 < n; ++i1)
{
if (vmap[i1 * n + j] < x) ++penalty;
}
for (unsigned j1 = j + 1; j1 < n; ++j1)
{
if (vmap[i * n + j1] < x) ++penalty;
}
}
}
return penalty;
}
unsigned PenaltyBase() const { return PenaltyBase(n, vmap); }
void Rotate(unsigned i, unsigned j, unsigned k)
{
unsigned kh0 = k / 2, kh1 = (k + 1) / 2;
for (unsigned i1 = 0; i1 < kh0; ++i1)
{
for (unsigned j1 = 0; j1 < kh1; ++j1)
{
unsigned x = vmap[(i1 + i) * n + (j1 + j)];
Set((i1 + i) * n + (j1 + j), vmap[(k - j1 - 1 + i) * n + (i1 + j)]);
Set((k - j1 - 1 + i) * n + (i1 + j), vmap[(k - i1 - 1 + i) * n + (k - j1 - 1 + j)]);
Set((k - i1 - 1 + i) * n + (k - j1 - 1 + j), vmap[(j1 + i) * n + (k - i1 - 1 + j)]);
Set((j1 + i) * n + (k - i1 - 1 + j), x);
}
}
}
void Rotate(const vector<unsigned>& v)
{
assert(v.size() == 3);
Rotate(v[0], v[1], v[2]);
}
void RotateI(unsigned i, unsigned j, unsigned k)
{
unsigned kh0 = k / 2, kh1 = (k + 1) / 2;
for (unsigned i1 = 0; i1 < kh0; ++i1)
{
for (unsigned j1 = 0; j1 < kh1; ++j1)
{
unsigned x = vmap[(i1 + i) * n + (j1 + j)];
Set((i1 + i) * n + (j1 + j), vmap[(j1 + i) * n + (k - i1 - 1 + j)]);
Set((j1 + i) * n + (k - i1 - 1 + j), vmap[(k - i1 - 1 + i) * n + (k - j1 - 1 + j)]);
Set((k - i1 - 1 + i) * n + (k - j1 - 1 + j), vmap[(k - j1 - 1 + i) * n + (i1 + j)]);
Set((k - j1 - 1 + i) * n + (i1 + j), x);
}
}
}
void RotateI(const vector<unsigned>& v)
{
assert(v.size() == 3);
RotateI(v[0], v[1], v[2]);
}
static void CalcAccumSumS(unsigned n, const vector<unsigned>& vmap, vector<vector<unsigned>>& output)
{
assert(vmap.size() == n*n);
if (output.size() != (n + 1))
{
output.resize(n + 1);
for (unsigned i = 0; i < output.size(); ++i)
output[i].resize(n + 1);
}
for (unsigned i = 0; i <= n; ++i)
{
output[i][0] = output[0][0] = 0;
}
for (unsigned i = 0; i < n; ++i)
{
for (unsigned j = 0; j < n; ++j)
{
output[i + 1][j + 1] = output[i + 1][j] + output[i][j + 1] - output[i][j] + vmap[i * n + j];
}
}
}
static void CalcAccumSumS(unsigned n, const vector<unsigned>& vmap, vector<vector<vector<unsigned>>>& output)
{
assert(vmap.size() == n*n);
if (output.size() != 3)
output.resize(3);
for (unsigned l = 0; l < 3; ++l)
{
if (output[l].size() != (n + 1))
{
output[l].resize(n + 1);
for (unsigned i = 0; i < output[l].size(); ++i)
output[l][i].resize(n + 1);
}
}
for (unsigned l = 0; l < 3; ++l)
{
for (unsigned i = 0; i <= n; ++i)
{
output[l][i][0] = output[l][0][0] = 0;
}
}
for (unsigned i = 0; i < n; ++i)
{
for (unsigned j = 0; j < n; ++j)
{
output[0][i + 1][j + 1] = output[0][i + 1][j] + output[0][i][j + 1] - output[0][i][j] + vmap[i * n + j];
output[1][i + 1][j + 1] = output[1][i + 1][j] + output[1][i][j + 1] - output[1][i][j] + i * vmap[i * n + j];
output[2][i + 1][j + 1] = output[2][i + 1][j] + output[2][i][j + 1] - output[2][i][j] + j * vmap[i * n + j];
}
}
}
static void CalcAccumSumS(unsigned n, const vector<unsigned>& vmap, double noise_amplitude, vector<vector<vector<double>>>& output)
{
static uniform_real_distribution<double> urd(0.0, 1.0);
assert(vmap.size() == n*n);
if (output.size() != 3)
output.resize(3);
for (unsigned l = 0; l < 3; ++l)
{
if (output[l].size() != (n + 1))
{
output[l].resize(n + 1);
for (unsigned i = 0; i < output[l].size(); ++i)
output[l][i].resize(n + 1);
}
}
for (unsigned l = 0; l < 3; ++l)
{
for (unsigned i = 0; i <= n; ++i)
{
output[l][i][0] = output[l][0][0] = 0;
}
}
for (unsigned i = 0; i < n; ++i)
{
for (unsigned j = 0; j < n; ++j)
{
double d = vmap[i * n + j] + noise_amplitude * urd(dre);
output[0][i + 1][j + 1] = output[0][i + 1][j] + output[0][i][j + 1] - output[0][i][j] + d;
output[1][i + 1][j + 1] = output[1][i + 1][j] + output[1][i][j + 1] - output[1][i][j] + i * d;
output[2][i + 1][j + 1] = output[2][i + 1][j] + output[2][i][j + 1] - output[2][i][j] + j * d;
}
}
}
void CalcAccumSum(vector<vector<unsigned>>& output) const { CalcAccumSumS(n, vmap, output); }
void CalcAccumSum(vector<vector<vector<unsigned>>>& output) const { CalcAccumSumS(n, vmap, output); }
void CalcAccumSum(double noise_amplitude, vector<vector<vector<double>>>& output) const { CalcAccumSumS(n, vmap, noise_amplitude, output); }
static void FindBestMove(unsigned n, const vector<vector<vector<unsigned>>>& accum, vector<unsigned>& output_move)
{
output_move.resize(3); output_move[2] = 0;
unsigned best_score = 0;
for (unsigned k = 2; k <= n; ++k)
{
for (unsigned i = 0; i + k <= n; ++i)
{
for (unsigned j = 0; j + k <= n; ++j)
{
unsigned a000 = accum[0][i][j];
unsigned a001 = accum[0][i][j + k];
unsigned a010 = accum[0][i + k][j];
unsigned a011 = accum[0][i + k][j + k];
unsigned a100 = accum[1][i][j];
unsigned a101 = accum[1][i][j + k];
unsigned a110 = accum[1][i + k][j];
unsigned a111 = accum[1][i + k][j + k];
unsigned a200 = accum[2][i][j];
unsigned a201 = accum[2][i][j + k];
unsigned a210 = accum[2][i + k][j];
unsigned a211 = accum[2][i + k][j + k];
unsigned s0 = a011 + a000 - a001 - a010;
unsigned s1 = a111 + a100 - a101 - a110;
unsigned s2 = a211 + a200 - a201 - a210;
if (best_score + 2 * s1 < (k - 1 + 2 * i) * s0)
{
best_score = (k - 1 + 2 * i) * s0 - 2 * s1;
output_move[0] = i; output_move[1] = j; output_move[2] = k;
}
if (2 * best_score + 2 * (s1 + s2) < 2 * (k - 1 + i + j) * s0)
{
best_score = (k - 1 + i + j) * s0 - (s1 + s2);
output_move[0] = i; output_move[1] = j; output_move[2] = k;
}
if (3 * best_score + 2 * s2 < (k - 1 + 2 * j) * s0)
{
best_score = ((k - 1 + 2 * j) * s0 - 2 * s2) / 3;
output_move[0] = i; output_move[1] = j; output_move[2] = k;
}
}
}
}
}
static void FindBestMove(unsigned n, const vector<vector<vector<double>>>& accum, vector<unsigned>& output_move)
{
output_move.resize(3); output_move[2] = 0;
double best_score = 0;
for (unsigned k = 2; k <= n; ++k)
{
for (unsigned i = 0; i + k <= n; ++i)
{
for (unsigned j = 0; j + k <= n; ++j)
{
double a000 = accum[0][i][j];
double a001 = accum[0][i][j + k];
double a010 = accum[0][i + k][j];
double a011 = accum[0][i + k][j + k];
double a100 = accum[1][i][j];
double a101 = accum[1][i][j + k];
double a110 = accum[1][i + k][j];
double a111 = accum[1][i + k][j + k];
double a200 = accum[2][i][j];
double a201 = accum[2][i][j + k];
double a210 = accum[2][i + k][j];
double a211 = accum[2][i + k][j + k];
double s0 = a011 + a000 - a001 - a010;
double s1 = a111 + a100 - a101 - a110;
double s2 = a211 + a200 - a201 - a210;
if (best_score + 2 * s1 < (k - 1 + 2 * i) * s0)
{
best_score = (k - 1 + 2 * i) * s0 - 2 * s1;
output_move[0] = i; output_move[1] = j; output_move[2] = k;
}
if (2 * best_score + 2 * (s1 + s2) < 2 * (k - 1 + i + j) * s0)
{
best_score = (k - 1 + i + j) * s0 - (s1 + s2);
output_move[0] = i; output_move[1] = j; output_move[2] = k;
}
if (3 * best_score + 2 * s2 < (k - 1 + 2 * j) * s0)
{
best_score = ((k - 1 + 2 * j) * s0 - 2 * s2) / 3;
output_move[0] = i; output_move[1] = j; output_move[2] = k;
}
}
}
}
}
void FindBestMoveBase(vector<unsigned>& output_move)
{
output_move.resize(3); output_move[2] = 0;
unsigned best_score = PenaltyBase();
for (unsigned k = 2; k <= n; ++k)
{
for (unsigned i = 0; i + k <= n; ++i)
{
for (unsigned j = 0; j + k <= n; ++j)
{
Rotate(i, j, k);
unsigned p = PenaltyBase();
RotateI(i, j, k);
if (best_score > p)
{
best_score = p;
output_move[0] = i; output_move[1] = j; output_move[2] = k;
}
}
}
}
}
vector<vector<unsigned>> moves;
vector<unsigned> penalties;
void AddCurrentPenalty() { penalties.push_back(PenaltyBase()); }
void MakeMove(const vector<unsigned>& move)
{
moves.push_back(move);
Rotate(move);
AddCurrentPenalty();
}
unsigned GetBestPenalty() const
{
unsigned best_penalty = penalties[0];
for (unsigned p : penalties)
best_penalty = min(p, best_penalty);
return best_penalty;
}
void PrintMoves() const
{
unsigned best_index = 0;
for (unsigned i = 1; i < penalties.size(); ++i)
{
if (penalties[i] < penalties[best_index])
{
best_index = i;
}
}
// assert(penalties[best_index] == penalties.back());
cout << best_index << endl;
for (unsigned i = 0; i < best_index; ++i)
{
const auto& p = moves[i];
cout << p[0] + 1 << " " << p[1] + 1 << " " << p[2] << endl;
}
}
void SolveGreedy(double min_noise, double max_noise)
{
unsigned moves_so_far = 0;
vector<unsigned> move;
// vector<vector<unsigned>> accum;
// vector<vector<vector<unsigned>>> accum;
vector<vector<vector<double>>> accum;
for (; moves_so_far < max_moves; ++moves_so_far)
{
// CalcAccumSum(accum);
double noise = (min_noise * moves_so_far + max_noise * (max_moves - moves_so_far - 1)) / (max_moves - 1);
CalcAccumSum(noise, accum);
FindBestMove(n, accum, move);
// FindBestMoveBase(move);
if (move[2] != 0)
MakeMove(move);
else
break;
}
// PrintMoves();
}
void FindBestLocalMove(vector<unsigned>& output_move)
{
output_move.resize(3); output_move[2] = 0;
unsigned best_moves = 4;
for (unsigned i = 0; i < n - 1; ++i)
{
for (unsigned j = 0; j < n - 1; ++j)
{
unsigned v00 = vmap[i * n + j];
unsigned v01 = vmap[i * n + j + 1];
unsigned v10 = vmap[i * n + j + n];
unsigned v11 = vmap[i * n + j + n + 1];
bool hp = ((v00 > v01) && (v10 > v11));
bool vp = ((v00 > v10) && (v01 > v11));
bool vpi = ((v00 < v10) && (v01 < v11));
if (vp)
{
output_move[0] = i; output_move[1] = j; output_move[2] = 2;
best_moves = 1;
break;
}
else if (hp)
{
if (vpi)
{
// 3 moves required
if (best_moves > 3)
{
output_move[0] = i; output_move[1] = j; output_move[2] = 2;
best_moves = 3;
}
}
else
{
// 2 moves required
if (best_moves > 2)
{
output_move[0] = i; output_move[1] = j; output_move[2] = 2;
best_moves = 2;
}
}
}
}
if (best_moves == 1)
break;
}
}
void FindBestLocal3Move(vector<unsigned>& output_move)
{
output_move.resize(3); output_move[2] = 0;
vector<pair<unsigned, unsigned>> vp(9);
vector<unsigned> vpos(9);
double best_score = 0.0;
for (unsigned i = 0; i < n - 2; ++i)
{
for (unsigned j = 0; j < n - 2; ++j)
{
for (unsigned k = 0; k < 9; ++k)
{
vp[k] = make_pair(vmap[(i + k / 3) * n + (j + k % 3)], k);
}
sort(vp.begin(), vp.end());
for (unsigned k = 0; k < 9; ++k)
{
vpos[k] = vp[k].second;
}
unsigned h = CField3::Hash3FromPos(vpos);
assert(n3_best_move.find(h) != n3_best_move.end());
unsigned pen = n3_penalty[h];
auto p = n3_best_move[h];
unsigned moves_req = (p.first >> 3);
double score = double(pen) / moves_req;
if (score > best_score)
{
best_score = score;
output_move = CField3::GetMove3FromIndex(p.first & 7);
output_move[0] += i;
output_move[1] += j;
}
}
}
}
void LocalOptimization()
{
vector<unsigned> move;
for (; moves.size() < max_moves; )
{
// FindBestLocalMove(move);
FindBestLocal3Move(move);
if (move[2] != 0)
MakeMove(move);
else
break;
}
}
void RemoveUselessMoves()
{
unsigned last_position = 0;
for (unsigned i = 1; i < penalties.size(); ++i)
{
if (penalties[i] < penalties[last_position])
last_position = i;
}
for (; moves.size() > last_position; )
{
RotateI(moves.back());
moves.pop_back();
penalties.pop_back();
}
}
};
int main()
{
auto start_time = chrono::system_clock::now();
dre.seed(100);
CField3::BuildSolutionMap();
CField fbase;
fbase.Read();
CField fbest = fbase, ftemp;
fbest.SolveGreedy(0.0, 0.0);
fbest.RemoveUselessMoves();
fbest.LocalOptimization();
unsigned best_penalty = fbest.GetBestPenalty();
for (; best_penalty > 0;)
{
ftemp = fbase;
ftemp.SolveGreedy(1.0, 1.0 * ftemp.n);
ftemp.RemoveUselessMoves();
ftemp.LocalOptimization();
unsigned p = ftemp.GetBestPenalty();
if (best_penalty > p)
{
best_penalty = p;
fbest = ftemp;
}
auto now_time = chrono::system_clock::now();
auto time_ms = chrono::duration_cast<std::chrono::milliseconds>(now_time - start_time);
if (time_ms.count() > 1900)
break;
}
fbest.PrintMoves();
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
import static java.lang.Math.min;
import static java.lang.Math.max;
public class Solution {
static class DynamicList<E> extends AbstractList<E> implements List<E> {
static final private class Block<E> {
int size;
private int offset;
private final E[] values;
@SuppressWarnings("unchecked")
Block(int capacity) {
this.offset = 0;
this.size = 0;
this.values = (E[]) new Object[capacity];
}
E addFirst(final E value) {
offset = (offset - 1) & (values.length-1);
E last = values[offset];
values[offset] = value;
if (size < values.length) {
size++;
}
return last;
}
void addLast(final E value) {
if (size == values.length)
return;
values[(offset + size) & (values.length-1)] = value;
size++;
}
E add(final int index, final E value) {
E last = (size == values.length) ? values[(offset - 1) & (values.length-1)] : null;
if (2*index < size) {
offset = (offset - 1) & (values.length-1);
for (int i = 0; i < index; i++) {
values[(offset + i) & (values.length-1)] = values[(offset + i + 1) & (values.length-1)];
}
}
else {
for (int i = (size == values.length) ? size-1 : size; i > index; i--) {
values[(offset + i) & (values.length-1)] = values[(offset + i - 1) & (values.length-1)];
}
}
values[(offset + index) & (values.length-1)] = value;
if (size < values.length) size++;
return last;
}
E set(final int index, final E value) {
int i = (offset + index) & (values.length-1);
E replaced = values[i];
values[i] = value;
return replaced;
}
E removeFirst() {
E removed = values[offset];
values[offset] = null;
offset = (offset + 1) & (values.length-1);
size--;
return removed;
}
E remove(final int index) {
E removed = values[(offset + index) & (values.length-1)];
if (2*index < size) {
for (int i = index; i > 0; i--) {
values[(offset + i) & (values.length-1)] = values[(offset + i - 1) & (values.length-1)];
}
values[offset] = null;
offset = (offset + 1) & (values.length-1);
}
else {
for (int i = index + 1; i < size; i++) {
values[(offset + i - 1) & (values.length-1)] = values[(offset + i) & (values.length-1)];
}
values[(offset + size - 1) & (values.length-1)] = null;
}
size--;
return removed;
}
E get(final int index) {
return values[(offset + index) & (values.length-1)];
}
}
public int size;
private final int blockBitsize;
private Block<E>[] data;
@SuppressWarnings("unchecked")
public DynamicList(int capacity) {
byte blockBitsize = 4;
while (capacity > 1L << (2*blockBitsize)) {
blockBitsize++;
}
data = new Block[1 + (int) ((capacity-1) >> blockBitsize)];
for (int i = 0; i < data.length; i++)
data[i] = new Block<E>(1 << blockBitsize);
this.size = 0;
this.blockBitsize = blockBitsize;
}
public E get(final int index) {
final int blockIndex = (int) (index >>> blockBitsize);
final int valueIndex = (int) (index & (-1L >>> -blockBitsize));
return data[blockIndex].get(valueIndex);
}
public E set(final int index, E value) {
final int blockIndex = (int) (index >>> blockBitsize);
final int valueIndex = (int) (index & (-1L >>> -blockBitsize));
return data[blockIndex].set(valueIndex, value);
}
public void add(final int index, E value) {
int blockIndex = (int) (index >>> blockBitsize);
int valueIndex = (int) (index & (-1L >>> -blockBitsize));
int blockSize = 1 << blockBitsize;
if (data[blockIndex].size < blockSize) {
data[blockIndex].add(valueIndex, value);
}
else {
value = data[blockIndex].add(valueIndex, value);
while (data[++blockIndex].size == blockSize) {
value = data[blockIndex].addFirst(value);
}
data[blockIndex].addFirst(value);
}
size++;
}
public E remove(final int index) {
int blockIndex = (int) (index >>> blockBitsize);
int valueIndex = (int) (index & (-1L >>> -blockBitsize));
E removed = data[blockIndex].remove(valueIndex);
while (++blockIndex < data.length && data[blockIndex].size > 0) {
data[blockIndex-1].addLast(data[blockIndex].removeFirst());
}
size--;
return removed;
}
public int size() {
return size;
}
}
static class ImmutableArray {
ImmutableArray parent;
int[] value;
final int length;
ImmutableArray(ImmutableArray arr, int... value) {
this.parent = arr;
this.value = value;
length = (parent == null) ? 0 : (parent.length+1);
}
ImmutableArray add(int... value) {
return new ImmutableArray(this, value);
}
public String toString() {
if (parent == null)
return "";
return parent.toString() + (value[0]+1) + ' ' + (value[1]+1) + ' ' + value[2] + '\n';
}
}
static class Grid implements Comparable<Grid> {
private final int n;
private final int[][] data;
private final ImmutableArray moves;
private int score = -1;
private final int[] rowScores;
private final int[] colScores;
public Grid(int[][] grid) {
n = grid.length;
data = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
data[i][j] = grid[i][j];
moves = new ImmutableArray(null, null);
rowScores = new int[n];
Arrays.fill(rowScores, -1);
colScores = new int[n];
Arrays.fill(colScores, -1);
}
public Grid(Grid parent, int row, int col, int k) {
n = parent.n;
data = new int[n][n];
for (int i = 0; i < n; i++)
if (i < row | i >= row+k)
data[i] = parent.data[i];
else
data[i] = parent.data[i].clone();
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++)
data[row+i][col+j] = parent.data[row+k-j-1][col+i];
}
moves = parent.moves.add(row, col, k);
rowScores = parent.rowScores.clone();
colScores = parent.colScores.clone();
for (int i = 0; i < k; i++) {
rowScores[row+i] = -1;
colScores[col+i] = -1;
}
}
private static int evaluateScore(int[] v) {
int score = 0;
for (int i = 1; i < v.length; i++) {
int vi = v[i];
for (int j = 0; j < i; j++)
score += (v[j] - vi) >>> 31;
}
return score;
}
private void evaluateScore() {
score = 0;
for (int i = 0; i < n; i++) {
if (rowScores[i] < 0)
rowScores[i] = evaluateScore(data[i]);
score += rowScores[i];
}
int[] b = new int[n];
for (int j = 0; j < n; j++) {
if (colScores[j] < 0) {
for (int i = 0; i < n; i++)
b[i] = data[i][j];
colScores[j] = evaluateScore(b);
}
score += colScores[j];
}
}
public int score() {
if (score < 0)
evaluateScore();
return score;
}
public String toString() {
return moves.length + "\n" + moves.toString();
}
public int compareTo(Grid o) {
return (score() > o.score()) ? -1 : (score() < o.score()) ? 1 : (moves.length - o.moves.length);
}
}
static int randIdx(Random rand, int size) {
return min(rand.nextInt(size), rand.nextInt(size));
}
private static int MAX_GRIDS = 1250;
private static int MAX_MOVES = 500;
public static void main(String[] args) {
long executionStart = System.currentTimeMillis();
Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in), 256 << 10));
int n = in.nextInt();
int[][] grid = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
grid[i][j] = in.nextInt();
in.close();
List<Grid> grids = new DynamicList<Grid>(MAX_GRIDS+1);
Grid srcGrid = new Grid(grid);
grids.add(srcGrid);
for (int k = n; k > 1 & k > n-7; k--) {
for (int row = 0; row < n-k+1; row++)
for (int col = 0; col < n-k+1; col++) {
Grid ng = srcGrid;
for (int i = 0; i < 3; i++) {
ng = new Grid(ng, row, col, k);
int insertionIndex = Collections.binarySearch(grids, ng);
if (insertionIndex < 0)
insertionIndex = ~insertionIndex;
grids.add(insertionIndex, ng);
}
}
}
Grid best = grids.get(0);
if (n > 1) {
Random rand = new Random();
long timePassed = System.currentTimeMillis() - executionStart;
int maxk = max(2, (int) (n * 0.70));
while (timePassed < 3600) {
int idx = randIdx(rand, grids.size());
while (grids.get(idx).moves.length >= MAX_MOVES) {
if (best.compareTo(grids.get(idx)) > 0)
best = grids.get(idx);
grids.remove(idx);
idx = randIdx(rand, grids.size());
}
if (grids.isEmpty())
break;
int k = max(2, min(rand.nextInt(n+1), maxk));
int row = rand.nextInt(n-k+1);
int col = rand.nextInt(n-k+1);
Grid ng = new Grid(grids.get(idx), row, col, k);
int insertionIndex = Collections.binarySearch(grids, ng);
if (insertionIndex < 0)
insertionIndex = ~insertionIndex;
grids.add(insertionIndex, ng);
if (grids.size() > MAX_GRIDS)
grids.remove(MAX_GRIDS);
timePassed = System.currentTimeMillis() - executionStart;
if (timePassed > 600)
maxk = max(2, (int) (n * 0.40));
if (timePassed > 1200)
maxk = max(2, (int) (n * 0.30));
if (timePassed > 1800)
maxk = max(2, (int) (n * 0.20));
if (timePassed > 2400)
maxk = max(2, (int) (n * 0.15));
if (timePassed > 3000)
maxk = 2;
}
}
if (best.compareTo(grids.get(0)) > 0)
best = grids.get(0);
System.out.print(best);
//System.out.print(best.score());
}
}
Python 3 rep HackerRank Solution
import math
import os
import random
import re
import sys
import itertools
import time
def score(a):
count = 0
for r in range(len(a)):
for ind in itertools.combinations(range(len(a)), 2):
if a[r][ind[0]] < a[r][ind[1]]:
count += 1
for c in range(len(a[0])):
for ind in itertools.combinations(range(len(a[0])), 2):
if a[ind[0]][c] < a[ind[1]][c]:
count += 1
return count
def rotate(a, r, c, d):
seg = [[a[i][c+j] for i in range(r+d, r-1, -1)] for j in range(d+1)]
for i in range(d+1):
for j in range(d+1):
a[r+i][c+j] = seg[i][j]
def undo(a, r, c, d):
seg = [[a[r+i][j] for i in range(d+1)] for j in range(c+d, c-1, -1)]
for i in range(d+1):
for j in range(d+1):
a[r+i][c+j] = seg[i][j]
def getRandom():
r = random.randint(0, len(a)-2)
c = random.randint(0, len(a)-2)
d = random.randint(1, len(a)-1-max(r,c))
return r, c, d
def countDes(a):
arrayMax = []
for i in range(len(a[0])-1):
count = 1
curI = 0
curMax = 1
posMax = 0
for j in range(1, len(a)):
if a[j][i] < a[j-1][i]:
count+= 1
if j == len(a) - 1:
if count > curMax:
curMax = count
posMax = curI
else:
if count > curMax:
curMax = count
posMax = curI
count = 1
curI = j
# length #r #c
arrayMax.append([curMax, posMax, i])
return arrayMax
def processNotRandom(a, getArray, history):
maxPos = -1
maxScore = score(a)
for i in range(len(getArray)):
r = getArray[i][1]
c = getArray[i][2]
d = min(len(a)-1-max(r,c), getArray[i][0])
rotate(a, r, c, d)
sc = score(a)
if sc > maxScore:
maxPos = i
maxScore = sc
undo(a, r, c, d)
if maxPos != -1:
r = getArray[maxPos][1]
c = getArray[maxPos][2]
d = min(len(a)-1-max(r,c), getArray[maxPos][0])
rotate(a, r, c, d)
history.append([r+1, c+1, d+1])
n = int(input())
a = []
for _ in range(n):
a.append(list(map(int, input().rstrip().split())))
# Write Your Code Here
curMax = score(a)
curSc = curMax
start = time.time()
Beta = 0.8
Beta_increase = 0.8
history = []
maxScore = score(a)
maxPos = -1
i = 0
while time.time() - start < 8.0 and len(history) < 500:
r, c, d = getRandom()
numRotate = 0
for j in range(3):
rotate(a, r, c, d)
sc = score(a)
if sc > maxScore:
maxScore = sc
numRotate = j + 1
rotate(a, r, c, d)
for j in range(numRotate):
history.append([r+1, c+1, d+1])
rotate(a, r, c, d)
print(len(history))
for i in range(0, len(history)):
print('{} {} {}'.format(history[i][0], history[i][1], history[i][2]))
Python 2 rep HackerRank Solution
C rep HackerRank Solution
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
