SPyofgame's blog

By SPyofgame, history, 3 weeks ago,

Original Problem

In this problem. The statement give you a deque of $n$ number. There are two players take turn alternately. In one turn, they can select either leftmost or rightmost element and remove it, and earn $x$ points where $x$ is the removed number. They play until the deque is empty. Lets $X, Y$ are the scores of the first player and the second. Find the maximum $X - Y$ when they play optimally

We can use dynamic-programming to solve it in $O(n^2)$ or we can improve upto $O(n\ polylog(n))$ using data-structure like Treap and fully-optimized by deque in linear $O(n)$

Recursive DP - O(n^2)
DP iterative - O(n^2)
Deque - O(n)

Variant Problem

Then, I come to a problem, here is the statement.

There is a cycle of $n (n \leq 10^4)$ binary number ${a_1, a_2, \dots, a_n}$ and ($a_i \in {0, 1}$) First player take a random number, lets say $a_p$ then remove it and gain $a_p$ points The second player take a number which is consecutive with last number removed ($a_p$) — select either $a_{p - 1}$ or $a_{p + 1}$ (notice that $a_1$ and $a_n$ is consecutive) They start to play alternately until there are no number left and they plays optimally

The question is in each game where as the first player select the number $a_p$, $p \in [1, n]$. How many games did the first player have more score than the second player

Example 1
Example 2
Example 3

I try to use dp to solve it in $O(n^2)$ but I dont know how to optimize by using deque and only come up to an $O(n^2)$ solution. Can someone suggest me a better algorithm ?

Dynamic programming - O(n^2)
Deque way - O(n^2)

• 0

By SPyofgame, history, 5 weeks ago,

The problem is to calculate the number of such subsequence ${a_1, a_2, \dots a_n}$ that ($a_1 + a_2 + \dots + a_k = n$) where ($k \geq 2$) and ($a_i \in {1, 2, \dots, n}$)

It is the sequence OEIS A111133

My approach for small n

Lets $magic(left, last)$ is the number of valid subsequences whose sum equal $left$ which next selected element is such $next$ in range $(last, left]$ ($next$ is strictly greater then last selected number $last$ and not greater than current sum $left$). The recursive stop when $left = 0$ then we found one valid subsequence

Recursive dp - O(n^3) - small n

My approach for bigger n

Lets $magic(sum, cur)$ is the number of valid subsequences whose selected sum is $sum$ and current selecting element is $cur$

• $cur$ is init as $1$ (smallest element) and recursive stop when it greater than $n$ (largest element)

• $sum$ is in range $[0, n]$ when it equal $n$ then we found 1 valid subsequence so we return $1$, else if it greater than $n$ we stop the recursive

The complexity is still $O(n^3)$ which $O(n^2)$ calculation and $O(n)$ for bignum implementation

Recursive dp - O(n^3) - bignum result
Iterative dp - O(n^3) - bignum result

My question

• Can I solve the problem in $O(n^2)$ or in $O(n^2 \times polylog(n))$

• Can I find the n_th element faster than $O(n^3)$

• +3

By SPyofgame, history, 2 months ago,

Simplest way:

Approach
Brute-force <TLE> - O(n! * n ^ 2) time - O(n) space

Improving the algorithm

Approach
BIT, Binary-search, Dynamic-programming <TLE> - O((n! * n + n) log n) time - O(n) space

Using formula to improve furthur more

Approach
Recursive Dynamic Programming Approach <AC> - O(n * k) time - O(n * k) space
Iterative Dynamic Programming Approach <AC> - O(n * k) time - O(k) space

I solved this problem but I wonder if there is a better way (faster than $O(n \times k)$)

So my question is "Is there a faster approach for this problem ?"

• +21

By SPyofgame, history, 3 months ago,

There is a simple problem like that on Codeforces

With ($1 \leq x, y \leq n$) then the result will just simply $pair(1; n - 1)$

When $(b\ \text{mod}\ a = 0)$ we have $(gcd(a, b) = a\ ;\ lcm(a, b) = b)$, therefor $gcd(a, b) + lcm(a, b) = a + b = n$

So if we choose $(a, b) = pair(1; n - 1)$ then $1 + (n - 1) = n$ true

But can I find the result in Linear or faster when both $x$ and $y$ have to be in range $[l, r]$ ? Maybe we give $pair(-1; -1)$ when there is no result

I found answers in some special cases but not general

Input:

Positive integer $n, l, r$

Output:

Find such $pair(x, y)$ in $range [l, r]$ that $(gcd(x, y) + lcm(x, y) = n)$

Example 1
Example 2

• +5

By SPyofgame, history, 3 months ago,

I read in this paper and know that Binary GCD Implementation is proven to be about 2 times faster than Normal GCD Implementation.

Binary Iterative GCD Implementation (wikipedia)
Normal Iterative GCD Implementation

I just wonder if there is an Efficient Binary Extended GCD Implementation and how fast can it be ?

• +4

By SPyofgame, history, 3 months ago,

Thanks to Suffix Array Tutorial from Codeforces I could learn easily how to build Suffix Array and solve some problems

I learn about $O(n \log^2(n))$ solution and optimize it into $O(n \log(n)$, it is fast and good. In some contests, I saw some div-1 rankers discuss about $O(n)$ solution. Now I am wondering if there is an simple implementation but efficient Suffix Array in Linear Time and Space ?

From their conversation about Linear Solution, I read from this paper and this too but I am not be able to implement it. I know those implementations are hard and higher above my levels but I just curiously to know about the implementation

• 0

By SPyofgame, history, 3 months ago,
In problem $\overbrace{(((a ^ n) ^ {{}^n}) ^ {{}^{{}^{...}}})}^{b\ times\ n} \mod m$
• My approach is calculating each part $((a ^ n) \mod m)$ then $(((a ^ n) ^ n) \mod m) = ((t ^ n) \mod m)$ ... all together in $O(\log n)$ each part and $O(b \times \log n)$ total time complexity

• Can I improve it somehow faster where $b$ is large ($b \leq 10^{16}$) and ($m$ can be composite number)

In problem $\overbrace{a ^ {(n ^ {(n ^ {(...)})})}}^{b\ times\ n} \mod m$
• I only know the way to use bignum to calculate $n ^ n$ then $n ^ {n ^ n}$ all together then I just have to calculate the modulo of $a ^ {...} \mod m$ but the total complexity will be very huge (since the number of digits of bignum will raise very fast)

• Can I apply these formula from phi-function:

$a ^ {\phi(m)} \equiv 1 \pmod m$
$a ^ n \equiv a ^ {n \mod \phi(m)} \pmod m$
$a ^ n \equiv a ^ {\phi(m) + (n \mod \phi(m))} \pmod m$
• Can I improve it somehow faster where $n$ is large ($n \leq 10^{16}$) and ($m$ can be composite number)

• +76

By SPyofgame, history, 3 months ago,

There is an empty rectangle of size

$n \times m$

where

$1 \leq n, m \leq 10^6$

We cover the rectangles k times from (u1, v1) to (u2, v2), where

$1 \leq k \leq 400$
$1 \leq u1 \leq u2 \leq n$
$1 \leq v1 \leq v2 \leq m$

The question is: How many squares of that rectangle have been covered ?

• +8

By SPyofgame, history, 4 months ago,

Here are some implementations for getting primes.

• Some are well-known & effectively algorithms you might need
• There are several blogs for these implementations, I only collect and edit it to same style code
• You can show your way below and I will add to the post ^^

Sorry, I am not sure if there are some corner cases or I calculated wrong complexity. If there are, please correct m

Here are the algorithms. Enjoy ^^

Division approach: Check if there are only 2 divisors
Another approach

My Planning on this post

• Add tutorial & reasoning for each implementation

• -11

By SPyofgame, history, 4 months ago,

I found these implementations ^^

Sorry, I am not sure if there are some corner cases or I calculated wrong complexity. If there are, please correct me.

I am wondering if there are some other implementations ^^ (you can comment below and I will add to the post)

Implementation 0: Trivial
Implementation 1: Optimized Trivial
Implementation 2: Naive Factorization
Implementation 3: Factorization
Implementation 4: Miller-rabin
Implementation 5: Sieve + Factorization
Implementation 6: Sieve + Miller-rabin + Pollard-rho
Implementation 7: Divisor Sum Sieve

Compilation:

Implementation Main Algorithm Time Complexity Space Complexity Coding Space Coding Complex
0. Trivial Implementation O(n) O(1) Short Simple
1. Trivial Implementation O(√n) O(1) Short Simple
2. Factorization + Math Math O(n ^ 2) ? O(1) Normal Normal
3. Factorization + Math Factorization O(n√n) O(1) Normal Normal
4. Factorization + Math Miller-rabin O(n * log^5(n)) O(1) Long Normal
5. Factorization + Math Sieve O(n) + O(log n) O(n) Normal Normal
6. Factorization + Math Pollard-rho O(√n) + O(√(√(n)) polylog n) query O(√n) + O(log n / log(log n)) query Very Long Complex

Planning:

• Add tutorial & reasoning for each implementation

• +40

By SPyofgame, history, 4 months ago,

I am wondering if I could always replace all long long type into int64_t type without breaking the program ? Will it somehow affects the program or remains the same ?

And how about the relationship between int and int32_t types

• +4

By SPyofgame, history, 5 months ago,

Recently while I am solving a problem, I realised that increase iterator after erasing the last element of the map (the map is empty) then it would run infinitively

So I stop the loop by adding a small line to check whether it is empty or not

/// map-looping using either iterator or reverse iterator
{
/// some code upper that erase the element but possible to make the map empty
if (map.empty()) break;
}


Is there an alternative way (some other implementations) to prevent from iterator increament when the map is empty (and reverse_iterator too if possible)

• -5

By SPyofgame, history, 6 months ago,

Given an array of N elements where |Ai| ≤ 1e9

How can I find the longest subsequences whose sum is positive efficiently

• -14

By SPyofgame, history, 6 months ago,
Original templates

If I want to make those templates simpler by using --bit instead of (bit — 1). Will this cause undefined behaviour ?

Changed templates

• -3

By SPyofgame, history, 6 months ago,

Issue: I feel laggy to comment and the contest which I took part in isnt been highlighted anymore.

Hope: Codeforces after the maintaining would work faster and more stable (and even during the contest if possible) <3.

• -29

By SPyofgame, history, 6 months ago,

Given two number n and q where 1 ≤ n, q ≤ 10.000

There are n nodes, each node have a green string connect to another. Each 2 node only have 1 string connect between them. There are n * (n — 1) * (n — 2) / 6 total string

You have to answer q queries, each query give 2 number u and v. You paint the string connect (u, v) by color red if they are green, and green if they are red (red <-> green). Then you have to count the number of triangle ABC (1 ≤ A, B, C ≤ n) where (A, B), (B, C), (C, A) have same color (all are red or green).

Time limit for the problem is 1s

Memory limit for the problem is 256Mb

Here are examples

Example 1
Example 2
Example 3

Notice that the number of valid triangle can be bigger than 10 ^ 9

I think the problem can be solved using map

My brute-force approach give 50% points
Update: Solution

• +3

By SPyofgame, history, 6 months ago,

Given 2 string S and T where 1 ≤ |T| ≤ |S| ≤ 100

We have to insert + into string S so that it is "equal to" T

Time limit for the problem is 1s

Memory limit for the problem is 256Mb

Here are examples

Example 1:
Example 2:
Example 3:

I think the problem can be solved using DP but I dont know how to do it

My brute-force approach give 50% points

If there are mutiple answers, pick one of them to output. It is allow to output leading zero number such as 00001, 00123, 00

Update: Solution

• -19

By SPyofgame, history, 6 months ago,

In this problem. How can I solve it using dsu ?

I see the problem has dsu-tag, but the editorial but doesnt show dsu approach there :(

Have this the code already dsu ?

• -4

By SPyofgame, history, 6 months ago,

Are there any effeciency algorithms to find shortest path using disjoin-set data structure ?

• +1

By SPyofgame, history, 6 months ago,

I know I am a low-ranker contestant. But during the contest, it took me more than 2 minutes just to do something. And every 30 minutes I been logged out and it take me again 3 ~ 5 minutes to log-in. It is very annoy :( Please help me, why the codeforces was so slow. This is the second time I write this blog (The first was ignore by auto-log-out)

• +66

By SPyofgame, history, 6 months ago,

Nice logo Codeforces UwU Love it <3

• +34

By SPyofgame, history, 7 months ago,

---------- Purpose: ----------

• First, sorry for my bad English.
• Second, I know there are lots of topics about this. But after solving a problem that need FastIO, I feel interested in FastIO and decide to do the implementations and comparing them. But it maybe time-consuming so I make this post for ones who maybe try to find the Effeciency-Simple-IO, so you can save time instead of searching more.
• Third, usually it is need not to use FastIO. In the contest, they usually have twice or more time of the solutions code than the given time limitation. Dont worry about faster IO if it is not needed, you should improve your algorithms first, maybe you can use Bitwise Operations for x8 x32 x64 faster.
• Fourth, if the problem need to be solve in O(n) ~ O(n log n), and your algorithms work in O(n ^ 2), this Micro-Optimization doesnt help you at all (maybe you will get some more points but hard get AC), you should change the algorithms for further approach.
• Final, for some problems that needed to be solved by FastIO, you can use the suitable template and modify it for your solving the problem. Dont use the template if you dont really know how to use (I may add a guide path to the post in the future)
• Conclusion, this post is about comparing the implementations for each version of C++ language and you should choose the most suitable for you.

Here are some implementations to input numbers I found

Time to input 1.000.000 elements (1 then 1.000.000)

(Testing on test #27 of this problem // GNU G++ 17 7.3.0)

Normal Cin Implementation: 1029ms
synchronized(true) Cin Implementation: 1029ms
Printf Implementation: 218ms
synchronized(false) Cin Implementation: 217ms
Getchar Implementation: 217ms
Unlocked-Getchar Implementation: 30ms

Single Line Template

Getchar Implementation
Unlocked-Getchar Implementation
synchronized(off) Implementation
synchronized(true) Implementation
Scanf Implementation
Cin Implementation

---------- Similiar Topic: ----------

---------- Planning: ----------

• Test with GNU G++ 14 6.4.0
• Test with GNU G++ 11 5.1.0
• Test with Microsoft Visual C++ 2010
• Test with Microsoft Visual C++ 2017
• Test about random 10.000.000 big numbers
• More implementations (Actually the post is about Faster and Faster Short Input Implementation but I will add some for speed comparing)
• New output types (long long, double, string)

• -20

By SPyofgame, history, 7 months ago,

----------

Purpose:

• First, sorry for my bad English.
• Second, I know there are lots of topics about this. But after solving a problem that need FastIO, I feel interested in FastIO and decide to do the implementations and comparing them. But it maybe time-consuming so I make this post for ones who maybe try to find the Effeciency-Simple-IO, so you can save time instead of searching more.
• Third, usually it is need not to use FastIO. In the contest, they usually have twice or more time of the solutions code than the given time limitation. Dont worry about faster IO if it is not needed, you should improve your algorithms first, maybe you can use Bitwise Operations for x8 x32 x64 faster.
• Fourth, if the problem need to be solve in O(n) ~ O(n log n), and your algorithms work in O(n ^ 2), this Micro-Optimization doesnt help you at all (maybe you will get some more points but hard get AC), you should change the algorithms for further approach.
• Final, for some problems that needed to be solved by FastIO, you can use the suitable template and modify it for your solving the problem. Dont use the template if you dont really know how to use (I may add a guide path to the post in the future)
• Conclusion, this post is about comparing the implementations for each version of C++ language and you should choose the most suitable for you.

Here are some implementations to output numbers I found

Time to write first 10.000.000 non-negative numbers

(base on Codeforces Custom Test // GNU G++ 17 7.3.0 // GNU G++ 14 6.4.0 // GNU G++ 11 5.1.0)

Sort by GNU G++ 17 7.3.0
Sort by GNU G++ 14 6.4.0
Sort by GNU G++ 11 5.1.0
Sort by Microsoft Visual C++ 2010
Sort by Microsoft Visual C++ 2017

Time to write 1.000 times first 10000 numbers

(base on Codeforces Custom Test // GNU G++ 17 7.3.0 // GNU G++ 14 6.4.0 // GNU G++ 11 5.1.0)

Sort by GNU G++ 17 7.3.0
Sort by GNU G++ 14 6.4.0
Sort by GNU G++ 11 5.1.0
Sort by Microsoft Visual C++ 2010
Sort by Microsoft Visual C++ 2017

Time to write first 10.000.000 non-positive numbers

(base on Codeforces Custom Test // GNU G++ 17 7.3.0 // GNU G++ 14 6.4.0 // GNU G++ 11 5.1.0)

Sort by GNU G++ 17 7.3.0
Sort by GNU G++ 14 6.4.0
Sort by GNU G++ 11 5.1.0
Sort by Microsoft Visual C++ 2010
Sort by Microsoft Visual C++ 2017

Single Line Template

Putchar Non-recursive toString Implementation
Putchar Non-recursive Dividing Implementation
Putchar Reverse Implementation
Putchar Recursive Implementation
Unlocked-Putchar Non-recursive toString Implementation
Unlocked-Putchar Non-recursive Dividing Implementation
Unlocked-Putchar Reverse Implementation
Unlocked-Putchar Recursive Implementation
Printf Implementation
synchronized(off) Implementation
synchronized(true) Implementation
Cout Implementation
fwrite buffer Implementation

----------

----------

----------

Planning:

• Test about random 10.000.000 big numbers
• Test about 10.000.000 numbers 2 ^ k, k integer
• More implementations (Actually the post is about Faster and Faster Short Output Implementation but I will add some for speed comparing)
• New output types (long long, double, string)

• +62

By SPyofgame, history, 7 months ago,

I dont know how to use Template for multiple input. Can you help me ?

Fast Input Code

Sorry for my bad English. Correct me if I am wrong.

• -25

By SPyofgame, history, 7 months ago,

I recently found the opperator co_await and co_yield in C++. How should I apply this into the code and should I use these operator in competitive programming ?

Sorry for my bad English and knowledge.