Sponsors

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();
}

}

The Future Of Sustainable...

Revolutionizing Sustainability: How CLEANR and Worldly Axion are Reshaping...

Together, Power Plants and...

The Symbiotic Solution: Power Plants Fueling Global Greenhouses In the...

Regional Lenders Are Merging...

The Consolidation Wave: Why Regional Lenders Are Merging to...

Rush announce reunion tour...

Rush Announces Triumphant Reunion Tour Five Years After Neil...

Partnership turns soggy paddocks...

The Kidney of the Landscape: How Partnerships are Revitalizing...

More CEOs want Elon...

The High-Stakes Gamble: Why 'Moonshot' CEO Pay is Worrying...

The Future Of Sustainable Innovation In Microplastics And Supply Chain

Revolutionizing Sustainability: How CLEANR and Worldly Axion are Reshaping Industry The push for true sustainability is no longer a niche concern—it is a mandatory requirement...

Together, Power Plants and Greenhouses Can Feed Humanity.

The Symbiotic Solution: Power Plants Fueling Global Greenhouses In the quest for sustainable practices and improved global food security, engineers are increasingly looking toward solutions...

Regional Lenders Are Merging to Answer the Challenge From Megabanks

The Consolidation Wave: Why Regional Lenders Are Merging to Fight Megabank Dominance The landscape of American banking is undergoing a rapid transformation, characterized by a...

Rush announce reunion tour five years after the death of drummer Neil Peart

Rush Announces Triumphant Reunion Tour Five Years After Neil Peart’s Passing The landscape of progressive rock was irrevocably changed five years ago with the passing...

Partnership turns soggy paddocks into wetlands – and a model for cleaner waterways

The Kidney of the Landscape: How Partnerships are Revitalizing Waterways Through Wetland Creation Wetlands have long been dubbed the 'kidneys of the landscape,' and for...

More CEOs want Elon Musk–style ‘moonshot’ pay packages—but comp experts are raising alarms

The High-Stakes Gamble: Why 'Moonshot' CEO Pay is Worrying Compensation Experts A new, highly ambitious trend is sweeping through corporate boardrooms: the demand for "moonshot"...

I did not expect this midrange Sony soundbar to rival my Sonos system like this

I Did Not Expect This Midrange Sony Soundbar to Rival My Sonos System Sony's Bravia Theater System 6, a mid-range soundbar, has surprisingly impressed reviewers...

Combination of coaching, personnel has LSU’s defense ‘playing great’

LSU's Defensive Surge: A Winning Combination of Coaching and Personnel The LSU Tigers' impressive defensive turnaround hasn't been a matter of luck; it's a strategic...

Disney’s Kimmel suspension shows Trump’s increasing grip over media

Disney’s Kimmel Suspension: Trump’s Tightening Grip on Media? The recent suspension of Jimmy Kimmel from Disney, following controversial comments about former President Trump, has sparked...