[Codeforces Round 938] B. Progressive Square

Problem details

https://codeforces.com/problemset/problem/1955/B

Problem - 1955B - Codeforces

 

Ideas

1. The b(1,1) is the smallest number of all b(i,j).
2. The numbers in array b and progressive square must be equal in number.

 

Answer code (Java)

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int t, n, c, d, b;
		String ans;
		
		Map<Integer, Integer> bMap;
		int miniVal, tmpSum;
		
		t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			n = sc.nextInt();
			c = sc.nextInt();
			d = sc.nextInt();
			bMap = new HashMap<Integer, Integer>();
			
			miniVal = 1000000001;
			
			for (int j = 0; j < n * n; j++) { // n * n < 25 * 10000
				b = sc.nextInt();
				bMap.put(b, bMap.getOrDefault(b, 0) + 1);
				
				if (b < miniVal) {
					miniVal = b;
				}
			}
			
			ans = "YES";
			for (int j = 0; j < n; j++) {						// n < 500
				for (int k = 0; k < n; k++) {					// n < 500
					tmpSum = miniVal + k * c + j * d;			// Idea1 : The b(1,1) is the smallest number of all b(i,j).
					if (bMap.getOrDefault(tmpSum, 0) <= 0) {
						ans = "NO";
						break;
					}
					bMap.put(tmpSum, bMap.get(tmpSum) - 1);		// Idea2 : The numbers in array b and progressive square must be equal in number.
				}
				if (ans.equals("NO")) break;
			}
			System.out.println(ans);
		}
	}
}