Codeforces Round #411 (Div. 1), problem: (F) Fake bullions Solution In JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Div1_411F {

int numTV;
int A;
int B;

ArrayList<Integer>[] tAList;

boolean[][] tVAct;
int[] numM;

int cTime = 0;
int[] disc;
int[] low;

ArrayDeque<Integer> stack = new ArrayDeque<Integer>();

ArrayList<ArrayList<Integer>> sCCs = new ArrayList<ArrayList<Integer>>();

int numC;

boolean[][] compAct;

// represents the minimum and the maximum amounts of active members a tournament vertex can have
int[] min;
int[] max;

long MOD = 1_000_000_007L;

int[][] comb;

void dfs(int cV) {
disc[cV] = low[cV] = cTime++;
stack.push(cV);

for (int adj : tAList[cV]) {
if (disc[adj] == -1) {
dfs(adj);
}
if (low[adj] < low[cV]) {
low[cV] = low[adj];
}
}
if (disc[cV] == low[cV]) {
ArrayList<Integer> cSCC = new ArrayList<Integer>();
while (stack.peek() != cV) {
low[stack.peek()] = Integer.MAX_VALUE;
cSCC.add(stack.pop());
}
low[stack.pop()] = Integer.MAX_VALUE;
cSCC.add(cV);
sCCs.add(cSCC);
}
}

void findSCCs() {
disc = new int[numTV];
low = new int[numTV];
Arrays.fill(disc, -1);

for (int i = 0; i < numTV; i++) {
if (disc[i] == -1) {
dfs(i);
}
}

numC = sCCs.size();
}

int fGCD(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}

void condenseComps() {
compAct = new boolean[numC][];
for (int cComp = 0; cComp < numC; cComp++) {
ArrayList<Integer> cMems = sCCs.get(cComp);
int cGCD = numM[cMems.get(0)];
for (int j : cMems) {
cGCD = fGCD(cGCD, numM[j]);
}
boolean[] cCompSet = compAct[cComp] = new boolean[cGCD];
for (int cM : cMems) {
for (int sM = 0; sM < numM[cM]; sM++) {
if (tVAct[cM][sM]) {
cCompSet[sM % cGCD] = true;
}
}
}
}
}

void pushConnections() {
boolean[] cSet = compAct[numC – 1];

for (int cComp = numC – 2; cComp >= 0; cComp–) {
boolean[] pSet = cSet;
cSet = compAct[cComp];
int gcd = fGCD(pSet.length, cSet.length);

boolean[] resSet = new boolean[gcd];

for (int i = 0; i < pSet.length; i++) {
if (pSet[i]) {
resSet[i % gcd] = true;
}
}

for (int cRes = 0; cRes < gcd; cRes++) {
if(resSet[cRes]){
for (int cNum = cRes; cNum < cSet.length; cNum += gcd) {
cSet[cNum] = true;
}
}
}
}
}

void findMaxs() {
max = new int[numTV];

for (int cComp = 0; cComp < numC; cComp++) {
int aCnt = 0;
for (boolean b : compAct[cComp]) {
if (b) {
aCnt++;
}
}
for (int cM : sCCs.get(cComp)) {
max[cM] = numM[cM] / compAct[cComp].length * aCnt;
}
}
}

// uses Pascal’s identity
void preComb() {
comb = new int[numTV + 1][];
comb[0] = new int[] { 1 };
for (int i = 1; i <= numTV; i++) {
int[] pRow = comb[i – 1];
int[] cRow = comb[i] = new int[i + 1];
cRow[0] = 1;
for (int j = 1; j < i; j++) {
int val = pRow[j] + pRow[j – 1];
cRow[j] = val < 1_000_000_007 ? val : val – 1_000_000_007;
}
cRow[i] = 1;
}
}

long findAns() {
long ans = 0;

for (int sLws = 0; sLws < numTV; sLws++) {
int sGrt = 0;
int pGrt = 0;
for (int oth = 0; oth < numTV; oth++) {
if (oth == sLws) {
continue;
}
if (min[oth] > max[sLws]) {
if (++sGrt >= A) {
continue;
}
}

// secondary condition in case of equality to prevent overcounting
else if (max[oth] > max[sLws] || (max[oth] == max[sLws] && sLws < oth)) {
pGrt++;
}
}

// condition: B – 1 – sGrt <= numT
int s = B – 1 – sGrt;
for (int numT = s > 0 ? s : 0; numT < B && numT <= pGrt && numT + sGrt < A; numT++) {
ans = (ans + ((long) comb[pGrt][numT]) * comb[sGrt][B – 1 – numT]) % MOD;
}
}
return ans;
}

@SuppressWarnings(“unchecked”)
void execute() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer inputData = new StringTokenizer(reader.readLine());
numTV = Integer.parseInt(inputData.nextToken());
A = Integer.parseInt(inputData.nextToken());
B = Integer.parseInt(inputData.nextToken());

tAList = new ArrayList[numTV];

for (int i = 0; i < numTV; i++) {
tAList[i] = new ArrayList<Integer>();
String nLine = reader.readLine();
for (int j = 0; j < numTV; j++) {
if (nLine.charAt(j) == ‘1’) {
tAList[i].add(j);
}
}
}

tVAct = new boolean[numTV][];
numM = new int[numTV];
min = new int[numTV];

for (int i = 0; i < numTV; i++) {
inputData = new StringTokenizer(reader.readLine());
int cNumM = numM[i] = Integer.parseInt(inputData.nextToken());
boolean[] cVAct = tVAct[i] = new boolean[cNumM];

String nLine = inputData.nextToken();
for (int j = 0; j < cNumM; j++) {
if (cVAct[j] = nLine.charAt(j) == ‘1’) {
min[i]++;
}
}
}
reader.close();

findSCCs();
condenseComps();
pushConnections();
findMaxs();
preComb();

long ans = findAns();
System.out.println(ans);
}

public static void main(String[] args) throws IOException {
new Div1_411F().execute();
}

}

Advertisement

spot_img

7 Reasons This Viral...

📢 As an Amazon Associate, I earn from qualifying...

Jaishankar meets senior Japanese...

In a significant step forward for Indo-Pacific diplomacy, External...

Why Viral Kitchen Gadgets...

📢 As an Amazon Associate, I earn from qualifying...

How does a raccoon...

Raccoons are ubiquitous across both rural woodlands and bustling...

We Tested Viral Kitchen...

📢 As an Amazon Associate, I earn from qualifying...

Brad Pitt and Ines...

Hollywood royalty made a stylish statement in Los Angeles...

7 Reasons This Viral Kitchen Gadgets Is Worth Every Single Penny

📢 As an Amazon Associate, I earn from qualifying purchases.If you had told me six months ago that a single purchase would change how...

Jaishankar meets senior Japanese leaders; discusses deeper strategic, economic ties

In a significant step forward for Indo-Pacific diplomacy, External Affairs Minister S. Jaishankar met with senior Japanese leaders in Tokyo to deliberate on enhancing...

Why Viral Kitchen Gadgets Is Currently Breaking the Internet

📢 As an Amazon Associate, I earn from qualifying purchases.I stumbled across this while desperately trying to fix a recurring problem in my routine....

How does a raccoon act with rabies?

Raccoons are ubiquitous across both rural woodlands and bustling suburban neighborhoods. While these masked foragers are generally cautious and nocturnal, their close proximity to...

We Tested Viral Kitchen Gadgets Here Is What You Must Know

📢 As an Amazon Associate, I earn from qualifying purchases.There comes a point when you realise that tolerating a frustrating situation is costing you...

Brad Pitt and Ines De Ramon walk ‘The Further Mis-Adventures of Cliff Booth’ premiere red carpet hand in hand

Hollywood royalty made a stylish statement in Los Angeles as Oscar-winning actor Brad Pitt arrived hand in hand with his partner, jewelry designer Inés...

Why Viral Kitchen Gadgets Is Currently Breaking the Internet

📢 As an Amazon Associate, I earn from qualifying purchases.Most products in this category disappoint within weeks. Cheap materials, vague instructions, and results that...

US and rivals spar over next UN boss as race lurches towards deadline

According to a report by Al Jazeera, diplomatic tensions among global powers have intensified as the United Nations nears the deadline to select its...

Why Viral Kitchen Gadgets Is Currently Breaking the Internet

📢 As an Amazon Associate, I earn from qualifying purchases.If you had told me six months ago that a single purchase would change how...