editorial-01.md

Alhazn Contest - 01

Contest Descirption

• This an assesement contest for the group, 16 people participated and 8 have solved at least one problem.
• Contest URL: alhazn contest

Problem A: Solving for Carrots

• This problem actually just boils down to printing the second integer read.

  void solve(Scanner in) {
    int a = in.nextInt(), b = in.nextInt();
    for(int i = 0; i < a; ++i) {
      in.next(); // ignore the values
    }
    System.out.println(b);
  }

Problem B: I've Been Everywhere, Man

• This problem asks us to count the number of distinct cities from a given list, which can be fairly done with a Set.

  void solve(Scanner in) {
    int t = in.nextInt();
    while(t-- > 0) {
      int n = in.nextInt();
      Set<String> set = new HashSet<>();
      for(int i = 0; i < n; ++i) {
        set.add(in.next());
      }
      System.out.println(set.size());
    }
  }

Problem C: Faktor

• In this problem we have: (A + (B - 1)) / B = C and we want to find A so this becomes: A = C * B - (B - 1)

  void solve(Scanner in) {
    long  b = in.nextLong(), c = in.nextLong();
    long a = c * b - (b - 1);
    System.out.println(a);
  }

Problem D: Symmetric Order

• Just implement what's required in the statement.

  void solve(Scanner in) {
    int n = in.nextInt();
    List<String> left = new Arraylist<>(), right = new ArrayList<>();
    for(int i = 0; i < n; ++i) {
      String cur = in.next();
      if(i % 2 == 0) left.add(cur);
      else right.add(cur);
    }
    Collections.reverse(right);
    left.addAll(right);
    // print left
  }

Problem E: Speed limit

• Again, Just implement what's required in the statement.

  void solve(Scanner in) {
    int n = in.nextInt();
    long ans = 0;
    int prev = 0;
    for (i = 0; i < n; ++i) {
        int s = in.nextInt(), t = in.nextInt();
        ans += s * (t - p);
        p = t;
    }
    System.out.println(ans);
  }

Problem F: Odd man out

• This problem asks to print the number that occured an odd number of times, you can simply keep a counter in a Map or an arr and see which one occurs an odd number of times, and the statment guarentees that there is just one.

  void solve(Scanner in) {
    int n = in.nextInt();
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < n; ++i) {
      int cur = in.nextInt();
      map.put(cur, map.getOrDefault(0, cur) + 1);
    }
    for(Entry<Integer, Integer> entry: map.entrySet()) { 
      if(entry.getValue() % 2 == 1) {
        System.out.println(entry.getKey());
      }
    }
  }

• Another approach can be derived from the xor operation identity: a xor a = 0 and a xor 0 = a
• In other words if some number a occurs an odd number of times then a ^ a ^ a = a
• And if it occurs an even number of times then: a ^ a ^ a ^ a = 0
• So all you have to do is get the xor of all the numbers

  void solve(Scanner in) {
    int n = in.nextInt();
    int res = 0;
    for(int i = 0; i < n; ++i) {
      res ^= in.nextInt();
    }
    System.out.println(res);
  }

Problem G: A classy problem

• This is standard sort problem, just the define the comparator as described in the statement.

class Person implements Comparable<Person> {
    
    public String name;
    String hash;
    
    public Person(String line) {
        String[] spl = line.split("\\s+");
        name = spl[0].substring(0, spl[0].length() - 1);
        StringBuilder sb = new StringBuilder();
        for (String c : spl[1].split("-"))
            sb.insert(0, c.charAt(0));
        while (sb.length() < 10)
            sb.append('m');
        hash = sb.toString();
    }
    
    @Override
    public int compareTo(Person b) {
        int ans = b.hash.compareTo(hash);
        if (ans == 0) {
            ans = name.compareTo(b.name);
        }
        return ans;
    }
}

Problem G: Anagram Counting

• This is also a standard problem, so if we assume that there are no repeated characters, the answer is going to be N!.
• But since allowed characters are allowed, we need to account for them, so the answer becomes N! / MUL{0, 26}(F[i]!) where F[i] is the frequency of character i
• One other note here: the answer can get pretty huge so you must use big integers, a good idea is to use Java's bulting BigInteger or some language that supports it out of the box like python or ruby. in C/C++ you have to write it yourself link for inspiration

void solve(Scanner in) {
  String s = in.next();
  int[] f = new int[26];
  for(int i = 0; i < s.length(); ++i) {
    f[s.charAt(i) - 'A']++;
  }
  
  BigInteger down = BigInteger.valueOf(1);
  for (int i = 0; i < 26; i++) {
      BigInteger factored = factorial(f[i]);
      down = down.multiply(factored);
  }
  BigInteger result = factorial(s.length()).divide(down);
  System.out.println(result);
}

Problem I: Birds on a wire

• In this problem you need to add as much birds on that wire while respecting the rules mentionned in the statement.

void solve(Scanner in) {

  long l = sc.nextLong();
  long d = sc.nextLong();
  long n = sc.nextLong();

  ArrayList<Long> sol = new ArrayList<>();
  for (int i = 0; i < (int) n; i++) {
      sol.add(sc.nextLong());
  }
  sol.add(6 - d); // account for the posts
  sol.add(l + d - 6);
  Collections.sort(sol);
  int ans = 0;
  for (int i = 0; i < n + 1; i++) {
      ans += (sol.get(i + 1) - sol.get(i) - d) / d; // how many birds can you put is the distance between two already - the min distance over d
  }
  System.out.println(ans);