PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Soumyadeep Pal
Tester: Radostin Chonev
Editorialist: Nishank Suresh
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given an array A, find the sum of the number of fixed points over all subarrays [A_L, A_{L+1}, \dots, A_R], where a fixed point of an array B is an index i such that B_i = i.
QUICK EXPLANATION:
The answer is the sum of N-i+1 over all indices 1\leq i\leq N such that A_i \leq i.
EXPLANATION:
Counting the number of fixed points for each subarray and summing them up is too slow, so we instead employ a trick commonly used in such counting problems - we instead look at each index and try to figure out how many subarrays it is a fixed point of, and then sum this over all possible indices.
Fix some index 1\leq i\leq N. When is this index a fixed point of a subarray [L, R]?
Of course, the very first condition which needs to be satisfied is that i needs to belong to the subarray in the first place, i.e, L\leq i\leq R.
Further, the condition of i being a fixed point tells us that A_i = i-L+1.
Rewriting this condition, we obtain L = i - A_i + 1 - in other words, there is exactly one choice of L given that i is fixed.
However, we must also have L\geq 1, so i - A_i + 1\geq 1 \iff i\geq A_i.
The choice of R doesn’t affect i being a fixed point, so any R such that R\geq i works, and there are N-i+1 of these.
Our final answer is thus simply the sum of N-i+1 over all indices 1\leq i\leq N such that A_i \leq i.
TIME COMPLEXITY:
\mathcal{O}(N)
CODE:
Setter (C++)
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n ; cin >> n;
long long ans = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (i >= x) ans += (n - i + 1);
}
cout << ans << '\n';
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin >> t;
for (int i = 1; i <= t; i++) solve();
return 0;
}
Tester (Kotlin)
import java.io.BufferedInputStream
fun main(omkar: Array<String>) {
val jin = FastScanner()
var nSum = 0
repeat(jin.nextInt(1000)) {
val n = jin.nextInt(100000)
nSum += n
if (nSum > 500000) {
throw InvalidInputException("constraint on sum n violated")
}
var answer = 0L
for (j in 1..n) {
val x = jin.nextInt(n, j == n)
if (x <= j) {
answer += (n - j + 1).toLong()
}
}
println(answer)
}
jin.endOfInput()
}
class InvalidInputException(message: String): Exception(message)
class FastScanner {
private val BS = 1 shl 16
private val NC = 0.toChar()
private val buf = ByteArray(BS)
private var bId = 0
private var size = 0
private var c = NC
private var `in`: BufferedInputStream? = null
private val validation: Boolean
constructor(validation: Boolean) {
this.validation = validation
`in` = BufferedInputStream(System.`in`, BS)
}
constructor() : this(true)
private val char: Char
private get() {
while (bId == size) {
size = try {
`in`!!.read(buf)
} catch (e: Exception) {
return NC
}
if (size == -1) return NC
bId = 0
}
return buf[bId++].toChar()
}
fun validationFail(message: String) {
if (validation) {
throw InvalidInputException(message)
}
}
fun endOfInput() {
if (char != NC) {
validationFail("excessive input")
}
if (validation) {
System.err.println("input validated")
}
}
fun nextInt(from: Int, to: Int, endsLine: Boolean = true) = nextLong(from.toLong(), to.toLong(), endsLine).toInt()
fun nextInt(to: Int, endsLine: Boolean = true) = nextInt(1, to, endsLine)
fun nextLong(endsLine: Boolean): Long {
var neg = false
c = char
if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') {
validationFail("found character other than digit, negative sign, space, and newline, character code = ${c.toInt()}")
}
if (c == '-') {
neg = true
c = char
}
var res = 0L
while (c in '0'..'9') {
res = (res shl 3) + (res shl 1) + (c - '0').toLong()
c = char
}
if (endsLine) {
if (c != '\n') {
validationFail("found character other than newline, character code = ${c.toInt()}")
}
} else {
if (c != ' ') {
validationFail("found character other than space, character code = ${c.toInt()}")
}
}
return if (neg) -res else res
}
fun nextLong(from: Long, to: Long, endsLine: Boolean = true): Long {
val res = nextLong(endsLine)
if (res !in from..to) {
validationFail("$res not in range $from..$to")
}
return res
}
fun nextLong(to: Long, endsLine: Boolean = true) = nextLong(1L, to, endsLine)
}
Editorialist (Python)
import sys
input = sys.stdin.readline
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
if a[i] <= i+1:
ans += n-i
print(ans)