Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

SPyofgame's blog

By SPyofgame, history, 6 days ago, In English,
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)

Read more »

 
 
 
 
  • Vote: I like it
  • +76
  • Vote: I do not like it

By SPyofgame, history, 13 days ago, In English,

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 ?

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

By SPyofgame, history, 4 weeks ago, In English,

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
Masking approach: Mask every multiple of primes
Another approach


My Planning on this post

  • Add compilations
  • Add relative blogs
  • Add some more implementations
  • Add tutorial & reasoning for each implementation

Read more »

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

By SPyofgame, history, 4 weeks ago, In English,

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 relative blogs

  • Add some more implementations

  • Add tutorial & reasoning for each implementation

Read more »

 
 
 
 
  • Vote: I like it
  • +32
  • Vote: I do not like it

By SPyofgame, history, 5 weeks ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By SPyofgame, history, 2 months ago, In English,

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)

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

By SPyofgame, history, 3 months ago, In English,

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • -14
  • Vote: I do not like it

By SPyofgame, history, 3 months ago, In English,
Original templates

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

Changed templates

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By SPyofgame, history, 3 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -29
  • Vote: I do not like it

By SPyofgame, history, 3 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By SPyofgame, history, 3 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • -19
  • Vote: I do not like it

By SPyofgame, history, 3 months ago, In English,

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 ?

Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

By SPyofgame, history, 3 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By SPyofgame, history, 3 months ago, In English,

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)

Read more »

 
 
 
 
  • Vote: I like it
  • +66
  • Vote: I do not like it

By SPyofgame, history, 3 months ago, In English,

Nice logo Codeforces UwU Love it <3

Read more »

 
 
 
 
  • Vote: I like it
  • +34
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English,

---------- 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

---------- About: ----------

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

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

  • Fread Buffer Implementation
  • 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)

Read more »

 
 
 
 
  • Vote: I like it
  • -20
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English,

----------

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

----------

About:

----------

Similiar Topic:

----------

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)

Read more »

 
 
 
 
  • Vote: I like it
  • +62
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English,

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.

Thanks for reading <3

Read more »

 
 
 
 
  • Vote: I like it
  • -25
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English,

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.

If I am wrong about something please guide me.

Thanks for reading <3

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English,

Question: Given two positive numbers N and M, find minimal |c — M| where N mod c = 0

Can we solve this problem in O(log (n)) or faster ?

Here is my approach in O(sqrt(n))

My code

Sorry for my bad English ;-;

If I have wrong something, please tell me. It is better to do that than just downvote me because I and someone will learn many new things <3

Read more »

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English,

I am just begin to learn Graph so if I wrong something please tell me ;-;

1) Is DFS tree a type of tree or just algorithms to traverse on tree ?

2) If DFS can be used to detect Ancestor / Descendant. Can I use BFS tree to detect Ancestor / Descendant ?

3) Is there a good website to learn and practice graph problems ?

4) Is the time complexity of Dijkstra implements by priority_queue O((E + V) log V) ? How about implements by set, what its time complexity ?

5) If DFS can use 2 or 3 colors implementations, are there another well-know implementation for BFS ?

6) Can we combine BFS and DFS effectively

7) When should I use SPFA instead of Dijkstra

8) I read that Dijkstra can be optimize by using Fibonacci Heap Implementation. Is there a simple way to make Fibonacci Heap

Sorry for my bad English ;-;

Sorry for asking about these but it can make the community better to answer than downvote my post ;-;

The meme below is just for fun

Thanks for reading

Read more »

 
 
 
 
  • Vote: I like it
  • -39
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English,

I use Visual Studio Code and run Linear Sieve (using Smallest Prime Factor). When I compile in vscode, the limit under 1 second is ~27e6 = 27.000.000. But when I use Custom Test in Codeforces. It can run up to ~120e6 = 120.000.000 in 888ms :O (I was shock when see that, it is very fast)

I have searched on google but see no answer ;-;

My code right here

#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> vi;
typedef vector<bool> vb;

vi prm;
vi spf;

void sieve(int n) // up_to 27e6 = 27.000.000
{
    prm.clear();
    if (n < 2) return ; prm.push_back(2);

    spf.assign(n + 1, 2); 
    spf[0] = spf[1] = 0;
    for (int i = 3; i <= n; i += 2) {
        if (spf[i] == 2)
            prm.push_back (spf[i] = i);

        for (int j = 0; j < prm.size() && prm[j] <= spf[i] && i * prm[j] <= n; ++j)
            spf[i * prm[j]] = prm[j];
    }
}

bool isPrime(int x) { return spf[x] == x; }

int main()
{
    int n;
    cin >> n;

    sieve(n);
    int p = prm.size();
    cout << p << endl;
    return 0;
}

Sorry for my bad English and if I have mistaken something please tell me. ;-;

Thanks for reading. Have a good coding day guys <3

Read more »

 
 
 
 
  • Vote: I like it
  • -30
  • Vote: I do not like it