SPyofgame's blog

By SPyofgame, history, 5 years 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

Full text and comments »

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

By SPyofgame, history, 5 years 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)

Full text and comments »

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

By SPyofgame, history, 5 years 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

Full text and comments »

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

By SPyofgame, history, 5 years 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 ?

Full text and comments »

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

By SPyofgame, history, 5 years ago, In English

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

Full text and comments »

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

By SPyofgame, history, 5 years 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)

Full text and comments »

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

By SPyofgame, history, 5 years ago, In English

Nice logo Codeforces UwU Love it <3

Full text and comments »

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

By SPyofgame, history, 5 years 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)

Full text and comments »

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

By SPyofgame, history, 5 years 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

Full text and comments »

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

By SPyofgame, history, 5 years 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

Full text and comments »

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

By SPyofgame, history, 5 years 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

Full text and comments »

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