Problem F. In Queries
Problem Author: Surya Sujarwo
Diberikan tabel yang berisi nilai dan sejumlah query, anda diminta untuk mengoutput hasil dari query yang diberikan. Data inisial digenerate dengan menggunakan formula:
f(r, c) = (a . f(r - 1, c) + b . f(r, c - 1) + x) mod m
f(r, c) = 0, for all r = 0 or c = 0
f(r, c) = the value on row r and column c, where r = 1 ... n, and c = 1 ...5
Hampir semua tim yang mencoba soal ini gagal pada tahap generating data inisial di atas. Nilai a, b dan x pada soal hanya diberitahukan sebagai "non-negative integer", sehingga nilai tertinggi a, b dan x bisa mencapai MAX_INT (231-1). Dengan demikian, yang menggunakan formula generator di atas secara mentah akan mendapatkan perhitungan yang overflow (Wrong Answer). Untuk mengatasinya, gunakan modular aritmatika.
a = a mod m, b = b mod m, x = x mod m
f(r, c) = (a . f(r - 1, c) + b . f(r, c - 1) + x) mod m
Selanjutnya, kunci penyelesaian soal ini ada pada batasan M (10,000) yang lebih kecil daripada N (100,000). Gunakan tabel frekuensi (seperti pada Counting Sort) pada masing-masing kolom, untuk menyimpan informasi jumlah data tak unik yang ada. Tabel tersebut diupdate setiap mendapat query insert atau remove. Sedangkan untuk menjawab query max/min/range, kita cukup bekerja di tabel frekuensi ini (tidak perlu melihat ke tabel data asli lagi). Dengan demikian total kompleksitas yang diperlukan adalah O(N + Q.M)
Solusi C/C++
oleh Suhendry Effendy
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
int f[120000][6];
int calc[6][11000];
bool del[120000];
int main()
{
int T;
scanf( "%d", &T );
for ( int tcase = 1; tcase <= T; tcase++ ) {
printf( "Case #%d:\n", tcase );
int a, b, x, m, n;
scanf( "%d %d %d %d %d", &a, &b, &x, &m, &n );
memset(f,0,sizeof(f));
memset(del,false,sizeof(del));
memset(calc,0,sizeof(calc));
a %= m, b %= m, x %= m;
for ( int r = 0; r <= n; r++ )
for ( int c = 0; c <= 5; c++ )
if ( r == 0 || c == 0 ) f[r][c] = 0;
else {
f[r][c] = (a * f[r-1][c] + b * f[r][c-1] + x) % m;
calc[c][f[r][c]]++;
}
int q, r, c, left, right, sum;
scanf( "%d", &q );
while ( q-- ) {
char line[100];
scanf( "%s", line );
if ( strcmp(line,"insert") == 0 ) {
n++;
for ( int i = 1; i <= 5; i++ ) {
scanf( "%d", &f[n][i] );
calc[i][f[n][i]]++;
}
}
else if ( strcmp(line,"remove") == 0 ) {
scanf( "%d", &r );
if ( r <= n && !del[r] ) {
del[r] = true;
for ( int i = 1; i <= 5; i++ ) calc[i][f[r][i]]--;
}
}
else if ( strcmp(line,"max") == 0 ) {
scanf( "%d", &c );
for ( int i = 10000; i >= 0; i-- )
if ( calc[c][i] != 0 ) { printf( "%d\n", i ); break; }
}
else if ( strcmp(line,"min") == 0 ) {
scanf( "%d", &c );
for ( int i = 0; i <= 10000; i++ )
if ( calc[c][i] != 0 ) { printf( "%d\n", i ); break; }
}
else if ( strcmp(line,"range") == 0 ) {
scanf( "%d %d %d", &c, &left, &right );
sum = 0;
for ( int i = left; i <= right; i++ ) sum += calc[c][i];
printf( "%d\n", sum );
}
}
}
return 0;
}
Solusi JAVA
oleh Suhendry Effendy
import java.util.*;
public class Query {
int[][] f = new int[120000][6];
int[][] calc = new int[6][11000];
boolean[] del = new boolean[120000];
void solve() {
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
for ( int tcase = 1; tcase <= T; tcase++ ) {
System.out.printf( "Case #%d:\n", tcase );
int a = scan.nextInt();
int b = scan.nextInt();
int x = scan.nextInt();
int m = scan.nextInt();
int n = scan.nextInt();
for ( int[] i : f ) Arrays.fill(i,0);
for ( int[] i : calc ) Arrays.fill(i,0);
Arrays.fill(del,false);
a %= m; b %= m; x %= m;
for ( int r = 0; r <= n; r++ )
for ( int c = 0; c <= 5; c++ )
if ( r == 0 || c == 0 ) f[r][c] = 0;
else {
f[r][c] = (a * f[r-1][c] + b * f[r][c-1] + x) % m;
calc[c][f[r][c]]++;
}
int q = scan.nextInt();
int r, c, left, right, sum;
while ( q-- > 0 ) {
String line = scan.next();
if ( line.equals("insert") ) {
n++;
for ( int i = 1; i <= 5; i++ ) {
f[n][i] = scan.nextInt();
calc[i][f[n][i]]++;
}
}
else if ( line.equals("remove") ) {
r = scan.nextInt();
if ( r <= n && !del[r] ) {
del[r] = true;
for ( int i = 1; i <= 5; i++ ) calc[i][f[r][i]]--;
}
}
else if ( line.equals("max") ) {
c = scan.nextInt();
for ( int i = 10000; i >= 0; i-- )
if ( calc[c][i] != 0 ) { System.out.println(i); break; }
}
else if ( line.equals("min") ) {
c = scan.nextInt();
for ( int i = 0; i <= 10000; i++ )
if ( calc[c][i] != 0 ) { System.out.println(i); break; }
}
else if ( line.equals("range") ) {
c = scan.nextInt();
left = scan.nextInt();
right = scan.nextInt();
sum = 0;
for ( int i = left; i <= right; i++ ) sum += calc[c][i];
System.out.println(sum);
}
}
}
}
public static void main(String[] args) {
new Query().solve();
}
}
|