PuzzlersWorld.com

  • Hacker Puzzle
  • Interview Puzzles
  • Number Puzzles
  • Maths Puzzles

Dead Pixels solution: Facebook hacker cup 2013 Round 1

(No Ratings Yet)

February 8, 2013 by puzzler Leave a Comment

From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details

This question is the third question(Carried 45 marks out of 100) for the Round 1 of 2013 hacker cup. only top 500 contestants will be moved to Round 2.

Problem Statement

John’s friend Peter purchases a new high resolution monitor with dimension W * H where W is the number of pixels in each row (i.e. width) and H is the number of pixels in each column (i.e. height).

However, there are N dead pixels on the monitor. The i-th dead pixel is located at (x[i], y[i]). (0, 0) is the top-left pixel and (W – 1, H – 1) is the bottom-right pixel. The locations of the dead pixels could be generated by 6 given integers X, Y, a, b, c and d by the following rules. If 2 pixels are at the same location, they are considered the same. It is possible that there are less than N distinct dead pixels.

  • x[0] = X
  • y[0] = Y
  • x[i] = (x[i – 1] * a + y[i – 1] * b + 1) % W (for 0 < i < N)
  • y[i] = (x[i – 1] * c + y[i – 1] * d + 1) % H (for 0 < i < N)

Peter connects his monitor to his computer and opens an image with dimension P (width) * Q (height). How many unique positions can the image be placed so that it can be displayed perfectly (i.e. all pixels of the picture are shown on the monitor)? The image cannot be rotated.

Input

The first line contains an integer T, which is the number of test cases. Then T test cases follow. Each test case contains 11 integers W, H, P, Q, N, X, Y,a, b, c, d.

Output

For each of the test cases numbered in order from 1 to T, output “Case #”, followed by the case number (with 1 being the first test case), followed by “: “, followed by an integer which is the number of different possible positions for the poster.

Constraints

  • 1 ≤ T ≤ 20
  • 1 ≤ W, H ≤ 40 000
  • 1 ≤ P ≤ W
  • 1 ≤ Q ≤ H
  • 1 ≤ N ≤ min(1 000 000, W * H)
  • 1 ≤ a, b, c, d ≤ 100
  • 0 ≤ X < W
  • 0 ≤ Y < H

Example Input

5
4 4 2 2 1 0 2 1 2 3 4
4 4 1 1 3 1 1 2 2 2 2
6 10 3 2 2 0 0 5 4 3 2
16 18 5 1 5 10 8 21 27 29 87
14 15 12 4 4 3 5 84 74 53 68

Example Output

Case #1: 7
Case #2: 15
Case #3: 32
Case #4: 197
Case #5: 16

Solution

Basically we have to see how many total rectangles of size PxQ size are possible such that there is no dead pixels inside those rectangles. We can first count the total number of rectangles and subtract the rectangles with dead pixels.

Total number of PxQ rectangles possible in WxH LED screen = (W-P+1)*(H-Q+1);

For any one dead pixel(x, y) all rectangles with top left position in the range for X =x-P+1 to x and Y = y-Q+1 to y are damaged rectangles.

This is the Java implementation of above explanation:-

import java.util.HashSet;
import java.util.Set;


public class DeadPixels {
	public int getUniqueWays(int W, int H, int P, int Q, int N, int X, int Y, int a, int b, int c, int d){
		int currX = X;
		int currY = Y;
		
		Set<String> damagedRectangles = new HashSet<String>();
		
		addDamagedRectangles(currX, currY, W, H, P, Q, damagedRectangles);
		for(int i = 1; i < N; i++){
			int tempX = getNextX(currX, currY, a, b, W);
			int tempY = getNextY(currX, currY, c, d, H);
			currX = tempX;
			currY = tempY;
			addDamagedRectangles(currX, currY, W, H, P, Q, damagedRectangles);
		}
		
		System.out.println("Total damaged Rectangles = " + damagedRectangles.size());
		System.out.println("Total possible rectangles = " + ((W-P+1)*(H-Q+1) - damagedRectangles.size()));
		return  ((W-P+1)*(H-Q+1) - damagedRectangles.size());
	}
	
	public void addDamagedRectangles(int x, int y, int W, int H, int P, int Q, Set<String> damagedRectangles){
		for(int i = x; i > x - P ; i--){
			for(int j = y; j > y- Q; j--){
				if(j >= 0 && i >=0){
					damagedRectangles.add(i +"," + j);
				}
			}
		}
	}
	
	public int  getNextX(int x, int y, int a, int b, int W){
		return ((x*a + y*b + 1)%W);
	}
	
	public int  getNextY(int x, int y, int c, int d, int H){
		return ((x*c + y*d + 1)%H);
	}
}
  • Share on Whatsapp
  • Share on Facebook
  • Share on Twitter
Facebook Comments
Next Puzzle
Cake Cutting solution: Facebook hacker cup 2013 Round 2

Checkout more Interview Questions Tags: Algorithm, Difficult, Facebook Hacker Cup, Interview, Java, Solved Puzzles

Leave a Comment Cancel reply

Submit your Puzzle

You may also like

  • Reverse a link list without using another
  • Beautiful Strings solution: Facebook hacker Cup 2013 Qual Round
  • Security problem solution: Facebook hacker cup 2013 Round 1
  • DS with insert, delete and getRandomElement in O(1)
  • Consonants Solution: Google codejam 2013 Round 1C
  • Sort the array in O(N)
  • Find Number present only once
  • Bullseye Solution: Google codejam 2013 Round 1A
  • Find nth element from end of linked list
  • Basic Concepts C/C++

Categories

  • Aive hi Puzzles
  • Akbar and Birbal
  • Alphabetical Puzzles
  • Bollywood Puzzles
  • Google Code jam
  • Hindi Riddles
  • Interview Puzzles
  • Interview Questions
  • Logical Puzzles
  • Malayalam Puzzles
  • Maths Puzzles
  • Miscellaneous
  • Number Puzzles
  • Picture Puzzles
  • Riddles
  • Tamil Puzzles
  • Technical

Social

  • View puzzlersworld’s profile on Twitter
privacy policy

Copyright © 2023 · eleven40 Pro Theme on Genesis Framework · WordPress · Log in

  • Hacker Puzzle
  • Logo Puzzles
  • Optical Illusions
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    ▼
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    ▲
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous