Codechef 2017 November LunchTime

https://www.codechef.com/LTIME54

1. Smart Strategy (SMRSTR)

Tag : Implementation, Number Theory

\(N\)개의 수 \(D_1 , \cdots , D_N \)이 있을 때, \(Q\)개의 정수 \(X_1 , \cdots , X_Q \)에 대해 다음 과정을 수행하는 프로그램 작성하여라.

procedure f(X):

for i = 1 .. N:

X = floor ( X / D[i] )

return X

\(1 \le \text{TESTCASE} \le 1,000\)

\(1 \le N \le 10^5, \ \sum N \le 3 \cdot 10^{5} \)

\(1 \le Q \le 10^5, \ \sum Q \le 3 \cdot 10^{5} \)

\(1 \le X, \ D_{i} \le 10^{9}\)

EN : 

For given \(N\) numbers \(D_1 , \cdots D_N \), write a program runs procedure \(f(X)\) for given \(Q\) queries, \(X_1 , X_2 , \cdots X_Q \).

procedure f(X):

for i = 1 .. N:

X = floor ( X / D[i] )

return X

양의 정수 \(X,a,b\)에 대해 다음의 식이 성립한다.

$ (X / a) / b = X / ab $

(/는 정수 나눗셈)

따라서 \(D_i\)들을 다 곱해두는데, 그냥 무식하게 곱하면 당연히 \(10^{900000}\)으로 오버플로우가 나게 된다.

\(X\)도 제한이 \(10^9\)로 작으므로(!), 곱한 값이 \(10^{9}\)보다 커지게 되면 어떤 \(X\)에 대해서도 답이 0이 된다. 따라서 \(10^{9}\)보다 커지게 되는 순간 곱하는 것을 멈춰도 무방하다.

쿼리는 미리 구해놓은 \(\prod D\)로 \(O(1)\)에 처리할 수 있다.

This special equality holds for natural numbers \(X,a,b\) and integer quotient operation /.

$ (X/a)/b = X/ab $

So we multiply all \(D_i\)s, but we need another idea to avoid overflow.

We have another constraint that \(X\) cannot exceed \(10^9\), then we know if the product of \(D_i\) exceeds \(10^{9}\), the value of \(f(X)\) will be always 0. So in this case, we have no difference whether we consider \(\prod_{i=1}^{j} D_{i}\) as \(\prod_{i=1}^{N} D_{i}\) or not.

We can run each query in \(O(1)\) time with precalculated \(\prod D\).

\(O(N + Q)\)

2. L - R Queries (LRQUER)

Tag : Data Structure, Merge Sort Tree, Segment Tree

수열 \(A_{1}, A_{2}, \cdots A_{N}\)이 주어져 있다. 다음의 쿼리를 \(Q\)번 수행하는 프로그램을 작성하여라.

 1 L R : \(M \in [L,R]\)에 대해 \((A_M-A_L) \cdot (A_R-A_M)\)의 최댓값을 출력한다.

2 i v : \(A_i\)를 \(v\)로 바꾼다.

\(1 \le \text{TESTCASE} \le 1000\)

\(1 \le \sum N \le 2 \cdot 10^{5}\)

\(1 \le \sum Q \le 2 \cdot 10^{5}\)

\(1 \le A_i , v \le 10^{9}\)

Construct a Special Segment tree whose each node \([s,e]\) contains a binary search tree, such as std::multiset that I used, which stores all numbers in \(A_s , \cdots , A_e \) in ascending order.

Running the second query (update query) is very simple : Just update all BSTs contains \(A_i\).

We need to observe the shape of formula stated in problem. If we expand it and sort it by descending order on \(A_m\), we can get the equation of parabola \(-A_{m}^{2} + (A_l + A_r)A_m - A_{l}A_{r}\). So the query eventually requires \(A_m\), which belongs to \(A_l \cdots A_r\) and the closest to \(\frac{A_l + A_r}{2}\). And it can be implemented with BST easily, or std::multiset::lower_bound() function if you use std::multiset.

$O(N \lg^{2} N + Q \lg^{2} N)$

3. Shuffling (SHUFFL)

(풀이 준비중)

4. Strange Query (STRQUER)

(풀이 준비중)