LuckyPaper's blog

By LuckyPaper, history, 8 months ago, , Recently I have participated in the national olympiad of my country. Sadly, I wasn't able to pass to the next round (Team Selection Test). After failing exam, my family, teacher and friends advised me to learn English and other things (I can't participate in the national olympiad next year). But I'm not interested in it at all, so I still spend many time solving problems. Because solving problems is the only thing that help me to be happy and forget about the failure.

So I asked here if anyone give me an advice to improve myself. Thanks for reading.

By LuckyPaper, history, 10 months ago, , Given a connected unweighted undirected graph with N (N <= 100000) vertices and M (M <= 200000) edges (there is no multiedge nor loop). For each bridge in graph determine the size of two subgraphs formed by removing this bridge.

I am trying to solve a problem, but I have just encountered this subproblem when following my approach. Could anyone have an idea to solve above problem? Thanks

By LuckyPaper, history, 10 months ago, , We usually use hash on strings to determine whether they are the same. But now I am wondering how to determine if two sub-board consists of lowercase English letters from (x1, y1) to (x2, y2) are the same. Is it possible to use hash? If yes, then how to get hash value of them?

By LuckyPaper, history, 11 months ago, , How to sort points in clockwise/counter-clockwise order efficiently? I use atan2 to get angle created by Ox axis and point but it seems slow and sometimes it causes precision error. Appreciate for any help.

By LuckyPaper, history, 11 months ago, , Recently I have encountered an interesting problem:

Given a grid of N x N (1 <= N <= 1500) consist of integers. Define F(i, j) is the maximum value of a path (value of a path is sum of number on that path) can be obtained by moving from (1, 1) to (i, j) using only moving right and moving down operation, i.e from (i, j) you can only move to (i + 1, j) and (i, j + 1). Your task is calculate sum of F(i, j) over 1 <= i <= N and 1 <= j <= N.

Now you have Q (Q <= 1500) queries, each query denote by character c and two integers x and y. c is either '-' or '+'. If c is '-', then a[x][y]--, otherwise a[x][y]++. After each query you have to print on a line the sum of F(i, j) over 1 <= i <= N and 1 <= j <= N.

I couldn't optimize my O(Q * N * N) algorithm. Could anyone have an idea to solve this problem?

By LuckyPaper, history, 12 months ago, , Hi,

so far I have known that the time complexity for concatenating two strings is O(n). So

while (a.length() < b.length()) a = "0" + a;

is O(n^2). But it still passed the TL: http://codeforces.com/contest/1066/submission/44198754

I am wondering why it passed. Could anyone help me?

By LuckyPaper, history, 13 months ago, , Given an array A consist of N integers (N <= 100000, 0 <= Ai <= sqrt(i) for 1 <= i <= N). Count the number of triple (i, j, k) such that i <= j <= k and (Ai xor Aj xor Ak) = 0.

I tried many approaches but I couldn't optimize my O(N^2) solution. Is there any efficient algorithm to solve this problem?

By LuckyPaper, history, 13 months ago, , Given an array A consist of N integers. (N <= 10^5). There are Q (Q <= 10^5) queries of two types:

• 1 x y: Increase x smallest elements, each by 1 which satisfy the following condition: all elements greater than or equal to y. (1 <= x <= N, 0 <= y <= 10^9).

• 2 l r: Count the number of elements in array A have value in range [l..r]. (1 <= l <= r <= 10^9).

I haven't found an approach to process queries type 1 yet. Could someone help me? Thanks.

By LuckyPaper, history, 14 months ago, , Recently I have encountered a difficult problem.

Given a matrix with size n * m (1 <= n, m <= 1500) consist of only 0 and 1, count the number of submatrix contains exactly k 1's. (0 <= k <= 6).

Could you help me to find an approach for this problem? Thanks

By LuckyPaper, history, 15 months ago, , https://szkopul.edu.pl/problemset/problem/eC-cABL-jWd4JdZDmfWufeeQ/site/?key=statement

I think this problem can be solved using graph matching. But I am stuck when trying to create such graph.

Could anyone help me ? Thanks.

Sorry for bad English

By LuckyPaper, history, 16 months ago, , https://szkopul.edu.pl/problemset/problem/l85hlaT4lDfPzwm3IPUHIMVo/site/?key=statement

I'm getting stuck at this problem. Could you give me a hint ? Thanks.

By LuckyPaper, history, 17 months ago, , 