physics0523's blog

By physics0523, history, 7 months ago, In English

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?

Full text and comments »

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

By physics0523, history, 12 months ago, In English

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

Full text and comments »

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

By physics0523, history, 12 months ago, In English

Hello, Codeforces!

We are happy to invite you to TheForces Round #27 (3^3-Forces), which will take place on 10.12.2023 17:35 (Московское время)

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!

You can get more information about theforces rating and prizes in our discord server.

Contests' archive

Congratulations to the winners:

1.liympanda

2.Joshc

3.arvindf232

And $$$2$$$ lucky participants:

MarcosK

DF_Pite

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

Editorial

Full text and comments »

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

By physics0523, history, 12 months ago, In English

104802A - Submission Bait Writer: wuhudsm

Editorial
Rate the problem

104802B - Snowy Bus Writer: pavlekn

Editorial
Rate the problem

104802C - Nafis and Strings Writer: BF_OF_Priety

Editorial
Rate the problem

104802D - Rudraksh's Sleepiness Writer: Ashutosh.Singh

Editorial
Rate the problem

104802E - Anuj's Longest Subarray Writer: Ashutosh.Singh

Editorial
Rate the problem

104802F - Nafis and Mex Writer: BF_OF_Priety

Editorial
Rate the problem

104802G - Che Forest Writer: pavlekn

Editorial
Rate the problem



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

Full text and comments »

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

By physics0523, history, 12 months ago, In English

Hello, Codeforces!

We are happy to invite you to TheForces Round #26 (Readall-Forces), which will take place on 16.11.2023 17:35 (Московское время). 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!

You can get more information about Theforces rating and prizes in our discord server.

Contests' archive

UPD:

Congratulations to the winners:

1.Golovanov399

2.neal

3.1_2_3_4_5_9

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

Full text and comments »

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

By physics0523, history, 23 months ago, In English

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

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

// add y to a[x]
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);
int add_point=n;

// add y to b[x]
if(b[x]!=empty){
  b[add_point]=b[x];
  b[x].second=add_point;
  add_point++;
}
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

Full text and comments »

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

By physics0523, history, 2 years ago, In English
  • 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!!!

Full text and comments »

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

By physics0523, history, 2 years ago, In English

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.

Full text and comments »

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

By physics0523, history, 4 years ago, In English
Tutorial is loading...

Jury solution: 85699387

Tutorial is loading...
Jury solution: 85699884
Tutorial is loading...
Jury solution: 85699939

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

Tutorial is loading...
Jury solution: 85700178
Tutorial is loading...
Jury solution: 85700334
Tutorial is loading...
Jury solution (Solution 1): 85700515

Jury solution (Solution 2): 85700518

Tutorial is loading...
Jury solution: 85700669

Feel free to share your approach here!

Full text and comments »

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

By physics0523, history, 4 years ago, In English

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

Full text and comments »

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

By physics0523, history, 7 years ago, In English

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)
Twitter:@butsurizuki

Nice to meet you!

Ja: こどふぉ始めてみました!(とはいえこれ含めもう5回コンテスト出てるんですが)
ブログのシステムがよく分かっておらず、とりあえず一本書いてみました(解法…ですかねぇ…)
これから日本人にとって人権的な時間のコンテストなら積極的に出ようと思います!
精進を重ねてひとまず青になりたい…
暫くはDiv.2で戦いますが、将来的にはDiv.1でも戦えるような地力を付けたいです(^q^)

Full text and comments »

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