Match Editorials

Match summary

This match was defined by a tough problemset for the competitors, with no solutions to the hard problem and only 12 coders solving the other two. However, there were few wrong submissions, thanks perhaps to the examples in the problems.

The winner of the match was exod40 with two problems and a fast submit in the medium, followed by yifan.oi and szsz with two problems solved each. Congratulations to them for their great performance.

The Problems

Value	250
Submission Rate	29 / 42 (69.05%)
Success Rate	26 / 29 (89.66%)
High Score	yuhch123 for 240.83 points (5 mins 35 secs)
Average Score	169.03 (for 26 correct submissions)

To make the browser simulation three structures are needed: a stack for the back pages, a stack for the forward pages and a vector to store the sequence of pages loaded. Then, we have to iterate each element in actions and execute it following what is descibed in the statement. Finally, just return the vector of pages loaded. For a straightforward solution, look at exod40's code.

Value	500
Submission Rate	20 / 42 (47.62%)
Success Rate	14 / 20 (70.00%)
High Score	exod40 for 465.93 points (7 mins 47 secs)
Average Score	341.45 (for 14 correct submissions)

To solve this problem, some knowledge about graph theory might be very useful. To solve the problem, we have to recognize some properties about the references:

• If you have to walk to the left to go from place A to place B, then you have to walk to the right to go from place B to place A.
• If you have to walk to the right to go from place A to place B and you have to walk to the right to go from place B to place C, then you have to walk to the right to go from place A to place C.

Using the first property, we can change every reference that goes from A to B walking to the left to a reference that goes from B to A walking to the right, so all our references will go in a single direction - in this case, to the right.

Then, for each query asking for the direction from C to D, we will make two queries, one to check if to go from C to D you have to walk to the right and another to check if to go from D to C you have to walk to the right. If the first query returns true, you have to return "RIGHT". If the second query returns true, you have to return "LEFT". Finally, if both queries return false, you have to return "UNKNOWN".

The only part left in the solution is to implement the queries. There are two basic algorithms to implement this:

• Before processing any query, create a graph using an adjacency matrix and find its Transitive Closure. Then, we can resolve a query looking to the requested position in the closure. yifan.oi used this approach to solve the problem, the code is here.
• Before processing any query, create a graph using your favorite representation (adjacency matrix, adjacency list or edge list). Then, we can resolve a query by making a DFS or BFS from the source to the destination. _sunrise used this approach to solve the problem, the code is here

Value	1000
Submission Rate	3 / 42 (7.14%)
Success Rate	0 / 3 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

The easiest way to solve this problem is to try each integer in the interval [low, high] and return the one with the lowest bit difference for each values[k]. However, this approach is too slow to pass system tests, because the interval can have up to 2³⁰ elements.

One way to solve this problem in time involves two recursive searchs. The first step is to split the binary representation of low, high and values[k] in two parts, one where the bits of low and high are the same, and the other where the low and high numbers start to differ (from the most significant bit to the lowest significant bit). For example:

high      = (181)10 = (10110101)2 = (101 10101)2
low       = (173)10 = (10101101)2 = (101 01101)2
values[k] =  (38)10 = (00101010)2 = (001 00110)2

To solve the first part we just have to change the first part of values[k] to the first part of low, because if we put a different value in the first part then the final result will be lower than low or higher than high. Now, we can ignore the first part and work only with the second part:

high      = (10101)2 = (21)10
low       = (01101)2 = (13)10
values[k] = (00110)2 = (6)10

Then, the interval can be split in two parts, those where the most significant bit is 0 and and the most significant bit is 1:

interval = [01101, 10101] = [01101, 01111] U [10000, 10101]

Then, we could search the lowest different number in the both intervals separately and return the one with the lowest difference (or the lowest lexicografically if the difference is equal). To search the best number in the lower interval, we can search recursively from the most significant bit to the least significant bit, comparing the bits in low and value. Then, we have four cases (lowBit is the actual bit of low and valueBit is the actual bit of values[k]):

• lowBit == 0 && valueBit == 0 : We have two choices: Change the value to 1 with cost 1, or leave the bit as is and process the remaining bits.
• lowBit == 0 && valueBit == 1 : The value bit is strictly higher than value bit, so we can leave the remaining bits equal.
• lowBit == 1 && valueBit == 0: We have to make the value bit 1 and process the remaining bits.
• lowBit == 1 && valueBit == 1: We can't change the value bit to 0, so the only thing we can do is process the remaining bits.

Something similar can be done with the higher interval. The algorithm runs in O(N), where N is the number of different bits between low and high. The following commented code in Java implements this algorithms using bit manipulation:

import java.math.*;
import java.util.*;

public class RangeFixer {
  // strucutre to store the algorithm results
  public class FixResult {
    public int value, cost;
    public FixResult(int value, int cost) {
      this.value = value; this.cost = cost;
    }
  }

  public int getEqualMask(int low, int high) {
    // return a mask with the longest most-significant consecutive block of ones
    // at the left
    int eqBits = ~(low ^ high), shift = 0;
    while ((eqBits & (eqBits + 1)) != 0) {
      eqBits >>= 1; ++shift;
    }
    return eqBits << shift;
  }

  FixResult closestToLow(int low, int value, int bit) {
    // base case, all bits were processed
    if (bit == 0) return new FixResult(0, 0);

    // the actual bit in value is higher than the actual bit in low, so no
    // change to value is needed
    if ((low & bit) == 0 && (value & bit) != 0) return new FixResult(value, 0);

    // the actual bit in low is one, so the bit in value must be changed to one
    // if needed, and then the lowest bits must be adjusted
    if ((low & bit) != 0) {
      FixResult next = closestToLow(low & ~bit, value & ~bit, bit >> 1);
      next.value |= bit;
      if ((value & bit) == 0) ++next.cost;
      return next;
    }

    // both bits are zero, so we have two options, the first is to change the
    // actual bit in value to one and left the remaining bits equal, and the
    // second is to keep the bit in zero and adjust the remaining bits
    FixResult change = new FixResult(value | bit, 1);
    FixResult noChange = closestToLow(low & ~bit, value & ~bit, bit >> 1);
    return noChange.cost <= change.cost ? noChange : change;
  }

  FixResult closestToHigh(int high, int value, int bit) {
    // base case, all bits were processed
    if (bit == 0) return new FixResult(0, 0);

    // the actual bit in value is lower than the actual bit in high, so no
    // change to value is needed
    if ((high & bit) != 0 && (value & bit) == 0) return new FixResult(value, 0);

    // the actual bit in high is zero, so the bit in value must be changed to
    // zero if needed, and then the lowest bits must be adjusted
    if ((high & bit) == 0) {
      FixResult next = closestToHigh(high & ~bit, value & ~bit, bit >> 1);
      if ((value & bit) != 0) ++next.cost;
      return next;
    }

    // both bits are one, so we have two options, the first is to change the
    // actual bit in value to zero and left the remaining bits equal, and the
    // second is to keep the bit in one and adjust the remaining bits
    FixResult change = new FixResult(value & ~bit, 1);
    FixResult noChange = closestToHigh(high & ~bit, value & ~bit, bit >> 1);
    noChange.value |= bit;
    return change.cost <= noChange.cost ? change : noChange;
  }

  public int closestValue(int low, int high, int value) {
    // get the most-significant consecutive equal bits between low and high,
    // then truncate all the numbers to the non-equal part
    int eqMask = getEqualMask(low, high), eqPart = eqMask & low;
    low &= ~eqMask; high &= ~eqMask; value &= ~eqMask;

    // find the closest value the closest value higher than low with bit in 0
    int bit = (~eqMask + 1) >> 1;
    FixResult lowRes = closestToLow(low & ~bit, value & ~bit, bit >> 1);
    if (((low ^ value) & bit) != 0) ++lowRes.cost;

    // find the closest value lower than high with bit in 1
    FixResult highRes = closestToHigh(high & ~bit, value & ~bit, bit >> 1);
    highRes.value |= bit;
    if (((high ^ value) & bit) != 0) ++highRes.cost;

    // attach the result with the lowest cost to the equal part and return
    return eqPart | (lowRes.cost <= highRes.cost ?
                     lowRes.value : highRes.value);
  }

  public int[] closestValue(int low, int high, int[] values) {
    // calculate the solution for each value and return
    int[] result = new int[values.length];
    for (int k = 0; k < values.length; ++k)
      result[k] = closestValue(low, high, values[k]);
    return result;
  }
}