### physics0523's blog

By physics0523, history, 3 months ago,

Sadly, until today, many people use single $\rm{mod} = 10^9+7$ or so on for hashing, so why not write how to blow up them easily, with minimized thinking process?

The key idea is simple. Just use Birthday attack.

1. Write a function to calculate the hash value
2. Write a random generator of string
3. When there are $k$ possible distinct hash values, look up $O(\sqrt{k})$ random candidates
4. Now we get a pair of strings that has exactly the same hash value!

In this method, the only things we should consider are that $k$ is small enough (around $k \le 10^{12}$ ), and the number of possible candidates is large enough. We don't need to care about what the hashing function is!

Example Code(C++)

Exercise:
Find two $18$-digit integers $x,y$ such that:

• Each digit of $x,y$ are $1,3,5,7,9$
• $x \equiv y \mod 998244353$
Short Explanation
Example Code(C++)
... then how to avoid attacking?
• +159

By physics0523, history, 8 months ago,

104855A - GCD,LCM and AVG

Editorial
Rate the problem

104855B - Yugandhar's Letter for Diya

Editorial
Rate the problem

104855C - Hungry Shark

Editorial
Rate the problem

104855D - Colorful Paths

Editorial
Rate the problem

104855E - Perfect Permutation

Editorial
Rate the problem

104855F - Regular Covering

Editorial
Rate the problem

Appendix: Code for all problems
• +16

By physics0523, history, 8 months ago,

Hello, Codeforces!

We are happy to invite you to TheForces Round #27 (3^3-Forces), which will take place on Dec/10/2023 17:35 (Moscow time)

Editorial is out!

What is TheForces Round?

You will have 120 minutes to solve 6 problems.

Note:there is an interactive problem in this round. If you are unfamiliar with interaction problems,you can read the guide for interactive problems here.

The round is TheForces rated! After the round you can find your rating changes here.

Prizes: the participant in the $i$th place will receive $2^{3-i}$ dollars $(1 \leq i \leq 3)$ as a prize. In addition, we will randomly select $\lfloor \frac{p}{30} \rfloor$ lucky participants and give each of them $1$ dollar as a prize, where $p$ is the number of participants. Please actively participate!

Contests' archive

Congratulations to the winners:

2.Joshc

And $2$ lucky participants:

MarcosK

DF_Pite

(Pls DM wuhudsm in CF or Discord for your prize :) )

Editorial

• +33

By physics0523, history, 9 months ago,
Editorial
Rate the problem

104802B - Snowy Bus Writer: pavlekn

Editorial
Rate the problem
Editorial
Rate the problem
Editorial
Rate the problem
Editorial
Rate the problem
Editorial
Rate the problem

104802G - Che Forest Writer: pavlekn

Editorial
Rate the problem

Appendix: physics0523's code for all problems (C++)
• +40

By physics0523, history, 9 months ago,

Hello, Codeforces!

We are happy to invite you to TheForces Round #26 (Readall-Forces), which will take place on Nov/16/2023 17:35 (Moscow time). As you can see in the subtitle, you are highly encouraged to read all the problems!

What is TheForces Round?

You will have 150 minutes to solve 7 problems.

The round is TheForces rated! After the round you can find your rating changes here.

Prizes: the participant in the $i$th place will receive $2^{3-i}$ dollars $(1 \leq i \leq 3)$ as a prize. In addition, we will randomly select $\lfloor \frac{p}{30} \rfloor$ lucky participants and give each of them $1$ dollar as a prize, where $p$ is the number of participants. Please actively participate!

Contests' archive

UPD:

Congratulations to the winners:

2.neal

And $5$ lucky participants:

11.IgorI

45.satyam343

58.pgiaminh8368

99.hi124

124.cseshamim47

(Pls DM wuhudsm in CF or Discord for your prize :) )

Editorial

• +63

By physics0523, history, 20 months ago,

If we want to use a 2D dynamic array, some C++ user writes following 2D vector:

vector<vector<int>> a(n);

a[x].push_back(y);

// walkthrough a[x]
for(auto &nx : a[x]){
cout << nx << "\n";
}


But we can do the equivalent thing with handwritten linked list (when we know the total size) by using 1D vector<pair<int,int>>:

pair<int,int> empty={-1,-1};
vector<pair<int,int>> b(n+total_size,empty);

if(b[x]!=empty){
}
b[x].first=y;

// walkthrough b[x]
int current=x;
while(current!=empty.second && b[currnt]!=empty){
cout << b[current].first << "\n";
current=b[current].second;
}


So, what's the benefit for the later implementation? The merit is the generation time of later one is very fast.

vector size = $10^5$, Total elements = $10^6$ (this means we need vector<vector<int>>(1e5) and the sum of the size of $10^5$ vectors is $10^6$)

generate walkthrough
vector<vector<int>> 49.04 ms 3.12 ms
vector<pair<int,int>> 12.78 ms 19.52 ms

vector size = $10^6$, Total elements = $10^6$

generate walkthrough
vector<vector<int>> 138.56 ms 10.92 ms
vector<pair<int,int>> 17.4 ms 7.8 ms

vector size = $10^6$, Total elements = $10^7$

generate walkthrough
vector<vector<int>> 1406.84 ms 32.86 ms
vector<pair<int,int>> 120.48 ms 437.28 ms

( on CF judge(C++20 64bit), x10 average, experiment code )

So, when the vector size is large and need small number of walkthrough, the vector<pair<int,int>> implementation have an advantage.
I use this implementation for 303C - Minimum Modular (because the package is old, current TL is 1s). 185222734

• +67

By physics0523, history, 20 months ago,
• According to some comments, dXqwq may be a rhythm game player.
• As a rhythm game player, I receive a huge motivation for my CP journey from dXqwq.
• dXqwq is not only a DX competitor but also a choseinou(super-skilled) writer of Pinely Round 1.

So, to honor him, I made a theoretical maximum score for this song in CHUNITHM. You are shining!!!

• +35

By physics0523, history, 22 months ago,

These days, the current usual haking system is in danger because new cheating method was discovered ( this ).
So let me share my ideas for the hacking system instead of the current one.

#### Current hacking system

• Contestants can hack the codes of other contestants in the same room during the coding phase.
• Contestants who can't solve a task or who don't lock their solution can't make hacking attempts at the task.
• Successful: +100pts
• Unsuccessful: -50pts

scoring by me

#### Suggestion 1: Open hacking system(long)

• Contestants can hack the codes of any other contestants, Like edu.
• Hacking has around 12h, and no points will be awarded.
• Any contestants can make hacking attempts on any submissions.
• Users can copy and execute the codes by themselves.
• The only benefit for contestants is reducing other contestants' scores.

scoring by me

#### Suggestion 2: Open hacking system(short)

• Exactly the same as Suggestion 1, except for the length of the hacking phase.
• The length of the hacking phase is around 30min, at most 60min
• these lengths are just my idea

scoring by me

#### Suggestion 3: Room-division hacking phase

• Contestants can hack the codes of other contestants in the same room, but it's not at the coding phase but at a hacking phase separated from the coding phase.
• Duration is 30min or 15min.
• maybe uncopiable 30min or copiable 15min is good?
• Any contestants can make hacking attempts on any pretest passed submissions in the same room.
• Successful: +100pts
• Unsuccessful: -50pts

scoring by me

#### Suggestion 4: Room-free hacking phase

• Any contestants are presented with about min(20,AC count for the problem) submissions (chosen equally, randomly, independently) for each problem.
• Duration is 30min or 15min.
• maybe uncopiable 30min or copiable 15min is good?
• Any contestants can make hacking attempts on any submissions which are presented to the contestants.
• Successful: +100pts
• Unsuccessful: -50pts

scoring by me

#### Suggestion 5: Removing the hacking system

• Nowadays tests are strong enough(really?) and hacking is a thing of the past.
• Then, why not remove the hacking feature?

scoring by me

All of my suggestions are preventing to see other contestants' codes during the coding phase, but there may be some ideas to do coding and hacking in parallel like now.
Feel free to share your idea. I'll add them to the list.

• +74

By physics0523, history, 4 years ago,

Jury solution: 85699387

Jury solution: 85699884
Jury solution: 85699939

UPD: $m<\min(a,b)$ is wrong, the right text is $m\le \min(a,b)$

Jury solution: 85700178
Jury solution: 85700334
Jury solution (Solution 1): 85700515

Jury solution (Solution 2): 85700518

Jury solution: 85700669

Feel free to share your approach here!

• +134

By physics0523, history, 4 years ago,

Codeforcesの皆さん、こんにちは!(Hello, Codeforces!)

I'm glad to invite you to my first contest, Codeforces Round 654 (Div. 2) which will be held on Jul/01/2020 16:35 (Moscow time) (notice earlier time than usual). All of the problems were mainly written and prepared by me. The round is rated if your rating is strictly less than 2100.

You will be given 6 problems (one problem has a subtask) and 2 hours to solve them. Please, read all the problems.

I would really like to thank:

The scoring distribution will be announced later.

Good luck, have fun and wish your high ratings :)

UPD: Scoring distribution : $500 - 1000 - 1250 - 1500 - (1500 + 1250) - 3000$

UPD: Editorial is out

• +732

By physics0523, history, 7 years ago,

Hello,Codeforces!

Tell trueth,I've already joined 4 other contests in here.

Today,I joined in #440(Div.2). Codeforces Round 440 (Div. 2, based on Technocup 2018 Elimination Round 2)

A:First,judge 1~9,After that,judge 10~99.

B:If k==1,output the minimum number.
If k==2,output the maximum of a[0],a[n-1],and the 2nd lowest number.
If k>=3,output the maximum number.

C:The best idea is 4+4+4+...+4+k.
If k==0,the output is q[i]/4.
If k==1, last +4+4+1 change to +9.
So,the output is (q[i]/4)-1.
If k==2, last +4+2 change to +6.
So,the output is q[i]/4.
If k==3, last +4+4+4+3 change to +9+6.
So,the output is (q[i]/4)-1.
In every query, you can response the answer in O(1).

Accepted:ooo--
Rating change:1441->1527(+86,highest)

Atcoder:Blue(1626,max1729)