Kosei::WebLog

I’ve decided that took asleep before SRM starts. But I’ve overslept and cannot attend :( The followings are in practice room, not in match.

Easy – SpidersOnTheGrid

The problem statement is little ambigiously. I couldn’t understand what is “free cells”. And direction “NSEW” is not clear, especially “N” and “S” since I can understand these directions two way: (-1, 0) or (1, 0) (for A[i][j]). I think the problem statement need to clealy define these directions.

I’ve wrote this code referring other person’s one.

class SpidersOnTheGrid {
public:
  int find(vector <string> A) {
    int ret = 0;
    bool ok[A.size()][A[0].size()];
    memset(ok, false, sizeof(ok));
    int dirx[4] = {-1, 1, 0, 0}; // NSEW
    int diry[4] = {0, 0, 1, -1};
    string dir = "NSEW";

    for (int i=0; i<A.size(); i++)
      for (int j=0; j<A[0].size(); j++) {
        int k = 0;
        for (k=0; k<4; k++)
          if (A[i][j] == dir[k])
            break;
        int nextx = i + dirx[k], nexty = j + diry[k];
        if (0 <= nextx && nextx < A.size() && 0 <= nexty && nexty < A[0].size())
          ok[nextx][nexty] = true;
      }

    for (int i=0; i<A.size(); i++)
      for (int j=0; j<A[0].size(); j++)
        if (!ok[i][j])
          ret++;

    return ret;
  }
};

Medium – EasySequence

Generate back of the sequence “A” until “A” has a loop. How to detect a loop is that when length of “A” is a multiple of 2, compare the first half and the latter half of “A”, and “A” has loop if the first half and the latter half is equal. Then simply check the “B” is contained in “A”.

This algorithm assumes these two things:

• “A” always has a loop.
• The loop is found within 2 seconds. (Computatinal complexity of loop searching.)

I’ve not been able to prove these, but luckily passed the system test.

class EasySequence {
public:
  int find(vector <int> A, vector <int> B) {
    int ret = -1;
    int n = A.size();

    // generate A
    for (int i=0; ; i++) {
      int tmp = 0;
      for (int j=0; j<n; j++)
        tmp += A[i+j];
      A.push_back(tmp%10);

      // loop detection
      if (A.size() % 2 == 0) {
        vector <int> first_half, second_half;
        for (int j=0; j<A.size(); j++)
          if (j < A.size()/2)
            first_half.push_back(A[j]);
          else
            second_half.push_back(A[j]);

        if (first_half == second_half)
          break;
      }
    }

    while (A.size() < B.size())
      A.insert(A.begin() + A.size(), A.begin(), A.end());

    // search B in A
    for (int i=0; i<A.size() - B.size() + 1; i++) {
      bool ok = true;
      for (int j=0; j<B.size(); j++)
        if (A[i+j] != B[j]) {
          ok = false;
          break;
        }

      if (ok) {
        ret = i;
        break;
      }
    }

    return ret;
  }
};

Passed easy problem, failed medium problem at system test. 5th place among my room and 298th place among entire div2. Rating decreases from 1152 to 1139 (-13). I’m still green :(

Easy – MinimalDifference

Value of B – A is at most 100,000. So it’s enough small to take brute-force approach. Simply check each value between A to B, and update smallest number of absolute value of difference.

class MinimalDifference {
public:
  int getDigitSum(int n) {
    int ret = 0;

    while (n > 0) {
      ret += n%10;
      n /= 10;
    }

    return ret;
  }

  int findNumber(int A, int B, int C) {
    int digit_sum_c = getDigitSum(C);
    int mini = INT_MAX;
    int ret = 0;

    for (int i=A; i<=B; i++) {
      int ds = getDigitSum(i);
      if (mini > abs(ds-digit_sum_c)) {
        mini = abs(ds-digit_sum_c);
        ret = i;
      }
      if (mini == 0)
        break;
    }

    return ret;
  }
};

Medium – WordsGame

How many times we swaps, the element itself in certain row/column doesn’t change (only position of the element in the row/column changes). So the row/column which can generate a word is that which elements are same to word (it’s ok if position of some elements are different). Concern these rows and columns as candidates of word. Count how many swap is needed for each candidates, and return minimum one. To calculate the number of swap, used an algorithm which likes insertion sort. Search from head of the word and a candidate string, and if the i-th element is different between word[i] and candidate[i], search correct character in a candidate (suppose it’s at j-th index) and swap candidate[i] and candidate[j].

After the contest I’ve failed system test. The cause of this was my misunderstanding. I’ve wrongly believed that all character contained in word is distinct. I’ve lacked consideration for this. So when my code choses candidate strings, simply checking that whether a character grid[i][j] is contained in the word or not. And if all character in certain row or column are contained in the word, the row/column is added into the candidates. This way of selecting candidate cannot handle the case that the word or the row/column has multiple same character. I’ve fixed this bug by changing the approach. To check whether the row or column is valid or invalid, comparing sorted row/column and sorted word. If these are same it’s able to be the candidate.

class WordsGame {
public:
  int minimumSwaps(vector <string> grid, string word) {
    vector <string> candidates;
    int ret = INT_MAX;

    string sorted_word = word;
    sort(sorted_word.begin(), sorted_word.end());
    for (int i=0; i<grid.size(); i++) {
      string s1, s2, sorted_s1, sorted_s2;
      for (int j=0; j<grid.size(); j++) {
        s1 += grid[i][j];
        s2 += grid[j][i];
      }

      sorted_s1 = s1;
      sorted_s2 = s2;
      sort(sorted_s1.begin(), sorted_s1.end());
      sort(sorted_s2.begin(), sorted_s2.end());

      if (sorted_s1 == sorted_word)
        candidates.push_back(s1);
      if (sorted_s2 == sorted_word)
        candidates.push_back(s2);
    }

    for (int i=0; i<candidates.size(); i++) {
      int swap_count = 0;

      for (int j=0; j<word.size(); j++) {
        if (word[j] != candidates[i][j]) {
          int pos = 0;
          for (int k=j+1; k<word.size(); k++)
            if (candidates[i][k] == word[j])
              pos = k;
          char tmp = candidates[i][j];
          candidates[i][j] = word[j];
          candidates[i][pos] = tmp;
          swap_count++;
        }
      }

      if (candidates[i] == word)
        ret = min(ret, swap_count);
    }

    if (ret == INT_MAX)
      ret = -1;

    return ret;
  }
};

Hard – NumbersAndMatches

I’ve not been able to submit this problem. The number of digit is at most 18 and K is at most 126. The largest input is too large to process it by simple searching like dfs. So I’ve thought that the dp is needed, but I’ve not been able to figure out good algorithm.

Hard – IngredientProportions

This is a kind of problem that an algorithm is straight, but implementation are bit complex. Firstly, I’ve took such approach:

1. Calculate ratios for each cocktail. In this time doesn’t consider the scale of these values.
   • e.g., in sample test case #0, we want to get a series {6, 4}. Or in #3 case, {360, 120, 378, 504}.
   • Representes a relationship among cocktails as a tree. Search this tree and calculate the series.
2. Calculate greates common divisor for each number of that series and divide these by this gcd.

I used a 2 dimensional array to represent a tree. Make a [proportions.size()+1] x [proportions.size()+1] size array. The i, j element of it corresponds to connection from node i to node j. In this time I’ve took a BFS approach to search the tree. So need to take care to select start node of searching. It must be a leaf or node of tree, otherwise all nodes cannot be searched. The leaf node is placed in the array such that there is only one node in the row. So search the leaf note such way and consider it as a start point of searching.

class IngredientProportions {
public:
  int gcd(const int _a, const int _b) {
    int a = max(_a, _b);
    int b = min(_a, _b);

    while (b) {
      int tmp = a % b;
      a = b;
      b = tmp;
    }

    return a;
  }

  vector <int> getMasses(vector <string> proportions) {
    vector <int> ret(proportions.size()+1, 0);
    int graph[proportions.size()+1][proportions.size()+1];
    memset(graph, 0, sizeof(graph));

    // make a tree
    for (int i=0; i<proportions.size(); i++) {
      int num1 = proportions[i][1] - '0';
      int num2 = proportions[i][8] - '0';
      int ratio1 = proportions[i][13] - '0';
      int ratio2 = proportions[i][15] - '0';
      graph[num1][num2] = ratio1;
      graph[num2][num1] = ratio2;
    }

    //     for (int i=0; i<=proportions.size(); i++) {
    //       for (int j=0; j<=proportions.size(); j++)
    //         cout << graph[i][j] << " ";
    //       cout << endl;
    //     }

    queue <pair <int, int> > q;

    // search a leaf node and push it to queue as a start point
    for (int i=0; i<=proportions.size(); i++) {
      int counter = 0;
      int index = 0;
      for (int j=0; j<=proportions.size(); j++)
        if (graph[i][j] != 0) {
          counter++;
          index = j;
        }
      if (counter == 1) {
        q.push(make_pair(i, index));
        break;
      }
    }

    // search a tree by bfs
    while (!q.empty()) {
      pair <int, int> cur = q.front();
      q.pop();

      int ratio1 = graph[cur.first][cur.second];
      int ratio2 = graph[cur.second][cur.first];
      graph[cur.second][cur.first] = 0;

      for (int i=0; i<=proportions.size(); i++)
        if (graph[cur.second][i] != 0)
          q.push(make_pair(cur.second, i));

      if (ret[cur.first] == 0 && ret[cur.second] == 0) {
        ret[cur.first] = ratio1;
        ret[cur.second] = ratio2;
      } else {
        int mul_for_cur = 0;
        int mul_for_exist = 0;
        int index = 0;
        if (ret[cur.first] != 0) {
          mul_for_cur = ret[cur.first] * ratio2;
          mul_for_exist = ratio1;
          index = cur.second;
        } else {
          mul_for_cur = ret[cur.second] * ratio1;
          mul_for_exist = ratio2;
          index = cur.first;
        }

        for (int i=0; i<ret.size(); i++)
          ret[i] *= mul_for_exist;

        ret[index] = mul_for_cur;
      }
    }

    // calculate gcd and divide all of results by it
    int divisor = ret[0];
    for (int i=1; i<ret.size(); i++)
      divisor = gcd(divisor, ret[i]);

    for (int i=0; i<ret.size(); i++)
      ret[i] /= divisor;

    return ret;
  }
};

Hard – HexagonalBattlefieldEasy

Took a greedy aproach. Recursively place a Vasyl’s hero for every possible way to put step by step.

I used a 2 dimensional array to represent a hexagonal battle field. Like this:

**...
*....
.....
....*
...**

A “.” on center of the field represents a cell (0, 0) of hexagonal battle field. And “*” is a pixel which is out of the range. Additionally, in this time, there is 6 way to put a Vasyl’s hero with containing certain pixel (x, y):

• (x+1, y)
• (x, y-1)
• (x-1, y-1)
• (x-1, y)
• (x, y+1)
• (x+1, y+1)

Place a hero one by one following these rules. Execution time doesn’t become a problem because N is at most 4, so the largest field size is only 37 cells.

class HexagonalBattlefieldEasy {
public:
  vector <string> splits(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty()) {
      size_t pos = s.find(del);
      string sub = "";
      sub = s.substr(0, pos);
      ret.push_back(sub);
      if (pos != string::npos)
        pos += del.size();
      s.erase(0, pos);
    }

    return ret;
  }

  int table[7][7];
  int N;
  int ret;

  pair <int, int> searchStart() {
    int len = N*2-1;
    for (int i=0; i<len; i++)
      for (int j=0; j<len; j++)
        if (table[i][j] == 0)
          return make_pair(i, j);
    return make_pair(-1, -1);
  }

  bool isInRange(int x, int y) {
    if (0 <= x && x < N*2-1 && 0 <= y && y < N*2-1)
      return true;
    return false;
  }

  int r(pair <int, int> pos) {
    int curx = pos.first, cury = pos.second;
    int dirx[6] = {1, 0, -1, -1, 0, 1};
    int diry[6] = {0, -1, -1, 0, 1, 1};

    for (int i=0; i<6; i++) {
      int nextx = curx + dirx[i], nexty = cury + diry[i];
      if (isInRange(nextx, nexty) && table[nextx][nexty] == 0) {
        table[curx][cury] = table[nextx][nexty] = 1;

        pair <int, int> tmp = searchStart();
        if (tmp.first != -1)
          r(tmp);
        else
          ret++;

        table[curx][cury] = table[nextx][nexty] = 0;
      }
    }

    return 0;
  }

  int countArrangements(vector <int> X, vector <int> Y, int _N) {
    ret = 0;
    N = _N;
    memset(table, 0, sizeof(table));
    vector <string> black_list;
    black_list.push_back("");
    black_list.push_back("20");
    black_list.push_back("30 40 41");
    black_list.push_back("40 50 60 51 61 62");

    vector <string> tmp = splits(black_list[N-1], " ");
    for (int i=0; i<tmp.size(); i++) {
      int a = tmp[i][0] - '0', b = tmp[i][1] - '0';
      table[a][b] = 1, table[b][a] = 1;
    }

    for (int i=0; i<X.size(); i++)
      table[X[i] + N-1][Y[i] + N-1] = 1;

    pair <int, int> t = searchStart();
    if (t.first != -1)
      r(t);
    else
      ret++;

    return ret;
  }
};

Hard – TheProduct

Using Dynamic Programming. The key idea of the algorithm is that increments number of ‘k’ from 1. Make 2 dimension array dp. dp[i][j] keeps optimal solution of the case that take ‘i’ element from right side of sequence from ‘j’th element, and multiply them.

Note that there are negative numbers in sequence. So it’s not enough to keep only maximum number of each step. Because if multiplying negative numbers odd times, the result of that calculation becomes smaller than optimal solution. To figure it out, make two 2 dimensional array and keep both maximum and minimum value of each step.

class TheProduct {
public:
  long long maxProduct(vector <int> numbers, int K, int maxDist) {
    long long dpmax[11][51];
    long long dpmin[11][51];

    for (int i=0; i<11; i++)
      for (int j=0; j<51; j++)
        {
          dpmax[i][j] = LLONG_MIN;
          dpmin[i][j] = LLONG_MAX;
        }

    for (int i=0; i<numbers.size(); i++)
      dpmax[1][i] = dpmin[1][i] = numbers[i];

    for (int k=2; k<=K; k++)
      for (int i=0; i<numbers.size(); i++)
        for (int j=0; j<i; j++)
          if (i - j <= maxDist && dpmax[k-1][i] != LLONG_MIN)
            {
              dpmax[k][j] = max(dpmax[k][j], max(numbers[j] * dpmax[k-1][i], numbers[j] * dpmin[k-1][i]));
              dpmin[k][j] = min(dpmin[k][j], min(numbers[j] * dpmax[k-1][i], numbers[j] * dpmin[k-1][i]));
            }

    long long ret = LLONG_MIN;
    for (int i=0; i<numbers.size(); i++)
      ret = max(ret, dpmax[K][i]);

    return ret;
  }
};

Solved easy and medium problems. Got a 87th place among whole div2. My rating is gained from 1101 to 1152 (+51). Hopefully I want to become a blue coder on next srm…

Easy – ToolsBox

Easy problem. Used spilt() function, I wrote it previously, which splits a string by certain delimiter (” ” in this case) and return results as vector . And also used std::set.

class ToolsBox {
vector <string> splits(const string _s, const string del)
{
  vector <string> ret;
  string s = _s;

  while (!s.empty())
    {
      size_t pos = s.find(del);
      string sub = "";
      sub = s.substr(0, pos);
      ret.push_back(sub);
      if (pos != string::npos)
        pos += del.size();
      s.erase(0, pos);
    }

  return ret;
}

public:
  int countTools(vector <string> need)
  {
    set <string> s;

    for (int i=0; i<need.size(); i++)
      {
        vector <string> v = splits(need[i], " ");
        for (int j=0; j<v.size(); j++)
          s.insert(v[j]);
      }

    return s.size();
  }
};

Medium – MazeMaker

Calculate minimum cost for each cell in maze using BFS from start position. And return maximum value of these, or return -1 if there is a cell not to be able to reach.

class MazeMaker {
public:
  int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol)
  {
    int visited[maze.size()][maze[0].size()];
    memset(visited, -1, sizeof(visited));
    queue <pair <int, pair <int, int> > > q;
    q.push(make_pair(0, make_pair(startRow, startCol)));
    visited[startRow][startCol] = 0;

    while (!q.empty())
      {
        pair <int, pair <int, int> > cur = q.front();
        q.pop();

        for (int i=0; i<moveRow.size(); i++)
          {
            int row = cur.second.first + moveRow[i];
            int col = cur.second.second + moveCol[i];
            int point = cur.first+1;

            if (0 <= row && row < maze.size() && 0 <= col && col < maze[0].size())
              if (maze[row][col] == '.')
                {
                  if (visited[row][col] == -1)
                    {
                      q.push(make_pair(point, make_pair(row, col)));
                      visited[row][col] = point;
                    }
                  else
                    visited[row][col] = min(point, visited[row][col]);
                }
          }
      }

    int ret = 0;
    for (int i=0; i<maze.size(); i++)
      for (int j=0; j<maze[0].size(); j++)
        if (visited[i][j] == -1 && maze[i][j] != 'X')
          return -1;
        else
          ret = max(ret, visited[i][j]);

    return ret;
  }
};

Hard – TheProduct

I couldn’t solve this problem. I felt that this is problem of dp, but I couldn’t find out the approach. Instead of dp approach I’ve wrote a code of backtracking using recursion and DFS. But off course it’ll be TLE when worst case of input, such as size of numbers is 50, k = 50 and maxDist = 50. Here is that code, have not passed system test yet.

class TheProduct {
public:
  long long ret;
  vector <int> numbers;
  int k;
  int maxDist;

  int r(int pos, int num, long long score)
  {
    if (num == k)
      {
        ret = max(ret, score);
      }
    else
      {
        int lim = min(pos+maxDist-1, (int)numbers.size() - k + num);

        for (int i=pos; i<=lim; i++)
          {
            r(i+1, num+1, score*numbers[i]);
          }
      }

    return 0;
  }

  long long maxProduct(vector <int> _numbers, int _k, int _maxDist)
  {
    ret = LLONG_MIN;
    numbers = _numbers;
    k = _k;
    maxDist = _maxDist;

    r(0, 0, 1);

    return ret;
  }
};