Competitive Programming 3

Competitive Programming 3

Leave a comment

So I finally shelled out $40 and bought this book, I’ve been wanting to buy it for a while so I went all out and bought the hardcover. Books pretty well written and a definite improvement over the first edition. The first edition is free now by the way; you can either donate to lulu and get it or you can just download it for free. You’ll still learn a lot from the first edition so I recommend that people read up on that if they can’t afford to buy this most recent edition.

Competitive Programming 3
Competitive Programming 3

The questions mentioned in the book are available on the UVA Online Judge so if you just want to practice they are all there. However, you will seriously miss out on all the insights and tips that the authors share. I highly recommend that people buy the book if they want to get better like I do. I’m giong to be going through every single question in this book and see how it effects my ranking on Codeforces and Topcoder. I’ll be posting solutions to all the UVA Questions mentioned in the book in case anyone is interested. The link for the free first edition can be found on the authors booksite :)

My solutions to the questions in the book are listed in the “Competitive Programming 3” page over on the right side of this page.

Algorithms, Java

Factors

Leave a comment

A naive way of figuring out the number of factors of a particular number is to try every number from 1 up to the number itself.

public ArrayList getFactors(int N) {
  ArrayList factors = new ArrayList();
  for (int i=0; i if (N%i==0) {
      factors.add(i);
  }
  return factors;
}

We can do much better than this by noticing that for every number i that is a factor of N; the number N/i is also a factor of N! This means that we can change out O(N) algorithm to O(sqrt(N)) which is much much faster.

F(x) vs F(sqrt(X))
O(N) algorithm vs O(sqrt(N)) algorithm
public ArrayList getFactors(int N) {
  ArrayList factors = new ArrayList();
  int sqrt = (int) Math.sqrt(N);
  for (int i=0; i if (N%i==0) {
    factors.add(i);
  }
  if (sqrt * sqrt == N) {
    factors.add(sqrt);
  }
  return factors;
}

Save this code somewhere, I guarantee it’ll come in handy!

Codeforces

Airport (218B) – Codeforces Round #134 (Div. 2)

1 Comment

http://codeforces.com/problemset/problem/218/B

This is a very easy problem to solve given that you know what data structure to use!

The data structure you need here is a heap. A heap is a tree like data structure which offers O(log(n)) inserts and removes and it also keeps the smallest or biggest element at the head.

Here is my code for solving the question:
PriorityQueue<> is the heap like data structure in java. It is a min-heap by default so I used some trickery to quickly convert it into a max-heap.

import java.util.*;

public class B {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] seats = new int[m];
    for (int i = 0; i < seats.length; i++) {
      seats[i] = sc.nextInt();
    }
    sc.close();

    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>();
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    for (int i = 0; i < seats.length; i++) {
      if (seats[i] != 0) {
        maxHeap.add(-seats[i]);
        minHeap.add(seats[i]);
      }
    }

    long max = 0;
    for (int i = 0; i < n; i++) {
      int t = -maxHeap.poll();
      max += t;
      if (t - 1 != 0)
        maxHeap.add(-(t - 1));
    }

    long min = 0;
    for (int i = 0; i < n; i++) {
      int t = minHeap.poll();
      min += t;
      if (t - 1 != 0)
        minHeap.add(t - 1);
    }

    System.out.println(max + " " + min);
  }
}