Notifications

Good job! You’re all caught up

Join challenges and check your notification settings if you don’t receive notifications. We’re actively adding new notifications. Read our blog post for more info

Notifications
TOSCA Editor - Web Application Wireframe Challenge (1)
Dismiss notification
Earlier Dismiss All
You have no more notifications

April 18, 2020 2020 TCO Algorithm Round 1A

AveragePrice

Let’s process the prices one by one. For each of them, we check if we have seen it before and if not, we add it to the sum.

For example, for { 10, 20, 10 }:

  • We see 10. We didn’t ever see 10 before. So add 10 to sum.
  • We see 20. We didn’t ever see 20 before. So add 20 to sum.
  • We see 10. We have seen it before. So do not add 10 to sum.
  • Sum = 30

    To check if we have seen a number before, we use for loop on previous seen elements.
public double nonDuplicatedAverage(int[] prices) {
  Arrays.sort(prices);
  int last = prices[0];
  double sum = prices[0];
  int count = 1;
  for (int i = 1; i < prices.length; i++)
    if (prices[i] > prices[i - 1]) {
      sum += prices[i];
      count++;
    }
  return sum / count;
}

def nonDuplicatedAverage(self, prices):
    prices = set(prices)
    return 1. * sum(prices) / len(prices)

BlindBoxSets

Suppose we are in the middle of the routine. For each item let’s keep how many times we’ve seen it. If we have seen an item more than numSets times, consider we have seen it numSets times.

This way, we can check if the state is final. There is only one final state where the count of each of the items equals numSets.

The transactions between states are simple. For each state, we uniformly at random choose an item and if its number of occurrences is less than numSets, we jump to the state which has this item one time more.

This leads to a slow solution.

To make it faster we should change the definition of states. We keep tuple (a[0], a[1], a[2], a[3], …, a[numSets]). a[i] shows how many types of items like x that there that number of occurrences of x.

def solve(self, distribution):
    distribution = tuple(distribution)
    if distribution not in self.memo:
        if distribution[-1] == self.collectionSize:
            self.memo[distribution] = 0
        else:
            rhs = 0
            for type_drawn in range(self.numSets):
                if distribution[type_drawn] == 0: continue
                prob = 1. * distribution[type_drawn] / self.collectionSize
                new_distribution = list(distribution)
                new_distribution[type_drawn] -= 1
                new_distribution[type_drawn+1] += 1
                rhs += prob * self.solve(new_distribution)

            prob_remains = 1. * distribution[-1] / self.collectionSize
            # E = 1 + prob_remains*E + rhs
            self.memo[distribution] = (rhs + 1.) / (1 - prob_remains)
    return self.memo[distribution]

def expectedPurchases(self, numSets, collectionSize):
    self.memo = {}
    self.numSets = numSets
    self.collectionSize = collectionSize
    distribution = [collectionSize] + [0] * numSets
    return self.solve(distribution)



double[][][][] expected = new double[51][51][51][51];
int S;
int N;

private double solve(int n1, int n2, int n3, int n4) {
  if (expected[n1][n2][n3][n4] > 0) return expected[n1][n2][n3][n4];
  if (n1 == 0 &amp;&amp; n2 == 0 &amp;&amp; n3 == 0 &amp;&amp; n4 == 0) return 0;
  double ret = 1;
  int sum = 0;
  if (n1 > 0) {
    sum += n1;
    ret += (1.0 * n1 / N) * solve(n1 - 1, n2, n3, n4);
  }
  if (n2 > 0) {
    sum += n2;
    ret += (1.0 * n2 / N) * solve(n1 + 1, n2 - 1, n3, n4);
  }
  if (n3 > 0) {
    sum += n3;
    ret += (1.0 * n3 / N) * solve(n1, n2 + 1, n3 - 1, n4);
  }
  if (n4 > 0) {
    sum += n4;
    ret += (1.0 * n4 / N) * solve(n1, n2, n3 + 1, n4 - 1);
  }
  ret *= N;
  ret /= sum;
  // System.out.println(n1 + "," + n2 + "," + n3 + "," + n4 + ": " + ret);
  return expected[n1][n2][n3][n4] = ret;
}

public double expectedPurchases(int numSets, int collectionSize) {
  N = collectionSize;
  S = numSets;
  if (numSets == 4) return solve(0, 0, 0, collectionSize);
  if (numSets == 3) return solve(0, 0, collectionSize, 0);
  if (numSets == 2) return solve(0, collectionSize, 0, 0);
  if (numSets == 1) return solve(collectionSize, 0, 0, 0);
  return 0;
}


ThreeNeighbors

There are several ways to solve this problem. Let’s find a pattern and solve the problem. Consider the following table:

…………………………………………..

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

…………………………………………..

It has width = 50. Exactly 96 cells are there that will become alive in the next turn. If we repeat this pattern we can achieve 50 // 3 * 96 such cells that is more than 500.

The remaining part is to handle when N is not divisible by 96. We add something like this:

…………………………………………..

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

…………………………………………..

It has 19 X’s and thus it creates (19 – 2) * 2 cells that will become alive in the next turn. So we handled when N is even.

Just to handle when N is odd, we add this:

XX

X.

public String[] construct(int N) {
  ArrayList<String> ret = new ArrayList<String>();
  while (N >= 96) {
    ret.add("..................................................");
    ret.add("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX");
    ret.add("..................................................");
    N -= 96;
  }
  ret.add("..................................................");
  String s = "XX";
  while (N > 1) {
    s += "X";
    N -= 2;
  }
  while (s.length() < 50) s += ".";
  ret.add(s);
  ret.add("..................................................");
  if (N == 1) {
    ret.add("..................................................");
    ret.add("XX................................................");
    ret.add("X.................................................");
  }
  return ret.toArray(new String[0]);
}



a.poorakhavan

Guest Blogger



UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds