coderhk Posted January 20, 2018 Share Posted January 20, 2018 (edited) 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. Edited January 20, 2018 by coderhk Link to comment Share on other sites More sharing options...
Sensei Posted January 20, 2018 Share Posted January 20, 2018 How about starting from making rectangle class taking all data as params in constructor, and putting these rectangles to (custom made class) kd-tree (or quadtree), but just 2D, not 3D, and checking whether they intersected, which will be easier/faster in kd-tree (quadtree), rather than regular list. Link to comment Share on other sites More sharing options...
coderhk Posted January 21, 2018 Author Share Posted January 21, 2018 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 Link to comment Share on other sites More sharing options...
Sensei Posted January 21, 2018 Share Posted January 21, 2018 Attached code should fail because it's hardcoding limits in this line: int[][] diff = new int[25][25]; Nobody in your assignment said there will be just 25^2=625 cells.. Link to comment Share on other sites More sharing options...
coderhk Posted January 21, 2018 Author Share Posted January 21, 2018 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. Link to comment Share on other sites More sharing options...
Sensei Posted January 21, 2018 Share Posted January 21, 2018 (edited) 10 minutes ago, coderhk said: 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. LOL... 1<<30 is > 1 bln entries.. 2D array of ints with 1 bln entries per row, per column, won't allocate on any currently existing computer.. Edited January 21, 2018 by Sensei Link to comment Share on other sites More sharing options...
coderhk Posted January 21, 2018 Author Share Posted January 21, 2018 The original number was 2004. Regardless, it just has to be big enough and the algorithm is guaranteed correct. Link to comment Share on other sites More sharing options...
Sensei Posted January 21, 2018 Share Posted January 21, 2018 7 minutes ago, coderhk said: The original number was 2004. Regardless, it just has to be big enough and the algorithm is guaranteed correct. Regardless what is put there, teacher should fail student, because of hardcoding.. Link to comment Share on other sites More sharing options...
coderhk Posted January 21, 2018 Author Share Posted January 21, 2018 7 minutes ago, Sensei said: Regardless what is put there, teacher should fail student, because of hardcoding.. haha in the end he did qualify for the international Olympiad. Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now