coderhk

haha in the end he did qualify for the international Olympiad.

The original number was 2004. Regardless, it just has to be big enough and the algorithm is guaranteed correct.

Oops, it was suppose to be int[][] diff = new int[x][x]; where x is a very large number like 1<<30 but I changed it so I could test the program with a small input to watch the program run in debug mode.

It wouldn't be necessary to create a class as it would be impractical when we can create a matrix to store/access the info at a constant time complexity. I have a solution from a friend in Java attached. The main problem that I am having is not being able to understand why and how the code works. Secondly, it would be extremely difficult to calculate the area the is required without double counting. Main.java

In the problem found at https://dmoj.ca/problem/ccc14s4 I heard from a friend that I am suppose to use a difference array to solve the problem but I can't seem to figure out how to solve this problem. Could anyone give me some advice? Please keep it simple since I am only a high school student preparing for the national infomatics Olympiad. A solution is python is found at http://mmhs.ca/ccc/2014/2014s4zihaozhang2.txt but I can't understand it. The problem: Canadian Computing Competition: 2014 Stage 1, Senior #4 You are laying N rectangular pieces of grey-tinted glass to make a stained glass window. Each piece of glass adds an integer value "tint-factor". Where two pieces of glass overlap, the tint-factor is the sum of their tint-factors. You know the desired position for each piece of glass and these pieces of glass are placed such that the sides of each rectangle are parallel to either the x-axis or the y-axis (that is, there are no "diagonal" pieces of glass). You would like to know the total area of the finished stained glass window with a tint-factor of at least T. Input Specification The first line of input is the integer N (1≤N≤1000), the number of pieces of glass. The second line of input is the integer T (1≤T≤1000000000), the threshold for the tint-factor. Each of the next N lines contain five integers, representing the position of the top-left and bottom-right corners of the ith piece of tinted glass followed by the tint-factor of that piece of glass. Specifically, the integers are placed in the order x1 y1 x2 y2 t, where the top-left corner is at (x1,y1) and the bottom-right corner is at (x2,y2), and tint-factor is t. You can assume that 1≤t≤1000000. The top-most, left-most co-ordinate where glass can be placed is (0,0) and you may assume 0≤x1 Output Specification Output the total area of the finished stained glass window which has a tint-factor of at least T. Thanks in advance.