SRM 451

Match Summary

Round Overview
Discuss this match

ReverseMagicalSource

Used as: Division Two - Level One:

This was a simple simulation problem. Where source and A are given and x must be calculated. x is equal to source initially. While x is less than or equal to A, multiply source by 10 and then add it to x.

1
2
3
4
5
6
7
8
9
10
class ReverseMagicalSource {
  public: int find(int source, int A) {
    int x = source;
    while (x <= A) {
      source *= 10;
      x += source;
    }
    return x;
  }
};

BoredPhilosophers

Used as: Division Two - Level Two:

A Simple java implementation below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
  public int[] simulate(String[] text, int N) {
    HashSet < String > hs = new HashSet < String > ();
    StringBuilder sb = new StringBuilder();
    for (String s: text) {
      sb.append(s);
    }
    String words[] = sb.toString()
      .split(" +");
    for (String s: words)
      hs.add(s); //To count distinct words
    int res[] = new int[N];
    res[0] = hs.size();
    for (int nrw = 2; nrw <= N; nrw++) {
      HashSet < String > hs1 = new HashSet < String > (); //To count distinct sequences
      for (int i = 0; i + nrw <= words.length; i++) {
        String seq = "";
        int j;
        for (j = 0; j < nrw; j++) {
          seq = seq + " " + words[i + j];
        }
        hs1.add(seq);
      }
      res[nrw - 1] = hs1.size();
    }
    return res;
  }

Do not forget to form the input string by concatenating all elements in text. First element in the result array is the number of distinct words. Number of different distinct sequences(of length nrw) can be found by generating all sequence of length nrw. Count of distinct sequences can be determined by adding it into a HashSet.

PizzaDelivery

Used as: Division Two - Level Three:

Let assume we have only one boy and he delivers  a set S of pizza  from the given pizzas. let m be the size of the set S. let Ts be the time needed to deliver all the pizzas from set S. Ti = shortest time from the restaurant to i-th pizza which he delivers at i-th step during delivering.  Now we know  Ts = 2*T1+2*T2+…+2*Tm-1+Tm. We can minimize Ts by delivering in a order such that T1<=T2<=…<=Tm-1<=Tm. Now, consider we have 2 boys namely a and b and Sa=set of pizza boy a delivers and Sb=set of pizza boy b delivers.To deliver all pizzas we need time equals to maximum of Ta and Tb. We can apply bruteforce on given  set of pizzas to partition it into two sets and get the required answer.

MagicalSource

Used as: Division One - Level One:

Let’s take a look at the example first:

1
2
3
4
5
6
7
8
9
10
        1234
          +
          12340 +
          123400 +
          1234000 +
          12340000 +
          123400000 +
          1234000000
          -- -- -- -- -- --
        1371110974

From this we can see that 1371110974=1234*1111111. Furthermore, any valid product that satisfies the condition must be the form x=(1111…)y, for some sequence of 1’s. Therefore, we want to find the maximum “11111-like” number which is a factor of x, and then return x/111…. Since x has a small number of digits, then we can just try all possible “111-like” numbers that are less than or equal to x.

As an example, here is oldherl’s code:

1
2
3
4
5
6
7
8
9
10
11
lass MagicalSource {
  public: long long calculate(long long x) {
    long long ans = x;
    long long t = 1;
    while (t <= x) {
      if (x % t == 0) ans = x / t;
      t = t * 10 + 1;
    }
    return ans;
  }
};

BaronsAndCoins

Used as: Division One - Level Two:

BrickPuzzle

Used as: Division One - Level Three: