# | User | Rating |
---|---|---|

1 | tourist | 4009 |

2 | jiangly | 3839 |

3 | Radewoosh | 3646 |

4 | jqdai0815 | 3620 |

4 | Benq | 3620 |

6 | orzdevinwang | 3612 |

7 | Geothermal | 3569 |

8 | ecnerwala | 3494 |

9 | Um_nik | 3396 |

10 | gamegame | 3386 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 164 |

2 | Um_nik | 163 |

3 | atcoder_official | 158 |

3 | cry | 158 |

3 | -is-this-fft- | 158 |

6 | awoo | 156 |

7 | adamant | 154 |

7 | nor | 154 |

9 | TheScrasse | 153 |

10 | Dominater069 | 152 |

Thank mike. Polygon and Codenforces orz

With the broad availability of quick and efficient sorting algorithms, that can sort arrays in $$$O(N*logN)$$$ complexity, little attention has been given to the vast and interesting world of the bad sorting algorithms. Because of this, I will, in this blog, explore this area. To make this list more interesting, we are only going to consider the algorithms in which play a role in the sorting process. That is, there won't be algorithms that use a *wait* function or an infinite loop.

-This may be the most famous bad sorting algorithm. Its legendary strategy consists of randomly shuffling and array until it is sorted.

```
#include<bits/stdc++.h>
using namespace std;
vector<int> v = {10,9,8,7,6,5,4,3,2,1};
bool sorted()
{
bool unsorted = false;
for(int i = 1; i < v.size(); i++) if(v[i] < v[i-1])
unsorted = true;
return !unsorted;
}
int main()
{
bool unsorted = false;
while(!is_sorted(v.begin(),v.end()))
random_shuffle(v.begin(),v.end());
for(int x : v) cout << x << " ";
}
```

*It is also worth mentioning that there is a variant of this algorithms that eliminates the randomness issue: Create all $$$N!$$$ possible permutations of a given array. Go through each one checking if they are ordered or not.

- In average, $$$(N-1)*N!$$$ swaps are made.

-This is another sorting algorithm that relies on randomness to be bad and the strategy it uses to sort is quite simple: If the array is not ordered, randomly select two elements of an array, swap them. The expected time complexity is a bit more complex, but on average $$$N!$$$ swaps are made.

```
#include<bits/stdc++.h>
using namespace std;
vector<int> v = {10,9,8,7,6,5,4,3,2,1};
int main()
{
srand(time(0));
int iteration = 0;
while(!is_sorted(v.begin(),v.end()))
{
int i = rand() % v.size();
int j = rand() % v.size();
swap(v[i],v[j]);
}
for(int x : v) cout << x << " ";
}
```

-This algorithm is a very interesting one. It utilizes the infamous technique of *multiply and surrender* in order to sort its elements. The recursion it utilizes is **very** "efficient" and interesting:

```
function slowsort(begin,end)
mid = floor((begin + end)/2)
slowsort(begin,mid)
slowsort(mid + 1, end)
if(array[mid] > array[end]) swap(array[mid],array[end]) //we compare the greatest element of each half
//now, the greatest element of the array is in the end, so we call recursively without including the last element
slowsort(begin,end - 1)
```

```
#include<bits/stdc++.h>
using namespace std;
vector<int> v = {10,9,8,7,6,5,4,3,2,1};
void slowsort(int st, int ed)
{
if(st >= ed) return;
int mid = (st + ed)/2;
slowsort(st,mid);
slowsort(mid + 1, ed);
if(v[mid] > v[ed]) swap(v[mid],v[ed]);
slowsort(st,ed - 1);
}
int main()
{
slowsort(0,v.size() - 1);
for(int x : v) cout << x << " ";
}
```

- The complexity of this method is kinda sketchy, so I will just say it is very very bad (not polynomial, not by far).

To finish this amazing list, I will present a sorting algorithm that becomes faster the more faith one has. I present to you the unmatched, the most amazing:

This niche method relies solely on the faith the programmer has on whatever it is that he believes. The method to sort consists of 3 simple steps:

- Check if the array is sorted
- Have faith
- Check if, by some miracle, the array is sorted again

```
#include<bits/stdc++.h>
using namespace std;
vector<int> v = {10,9,8,7,6,5,4,3,2,1};
void pray()
{
//put whatever you use to pray here, I will put my prayer
/*
ヴァスコ・ダ・ガマ賛歌
ヴァスコ・ダ・ガマ
心から歌おう
マルタ十字は我が旗
英雄ポルトガル人の名を冠する
ヴァスコ・ダ・ガマ、あなたの名声はこうして築かれた
あなたの絶大なファンは大喜び
ブラジルの南北
地上に輝く君の星
海を照らす
陸上競技では、あなたは腕だ
ボート競技は不滅だ
フットボール界では
ブラジルとポルトガルの結束
陸上競技は腕だ
ボート競技では、あなたは不滅です。
サッカーでは
ブラジルとポルトガルの団結
みんなで心を込めて歌おう
マルタ十字は私の旗！
英雄ポルトガル人の名を冠する
ヴァスコ・ダ・ガマ、それが君が有名になった理由だ
あなたの膨大なファンはとても幸せです
この国の南北、南北
地上に輝く君の星
海を照らす
陸上競技では、あなたは腕だ
ボート競技は不滅だ
フットボール界では、君は不滅だ
ブラジルとポルトガルの結束
陸上競技は腕だ
ボート競技では、あなたは不滅です。
サッカーでは
ブラジルとポルトガルの結束
*/
return;
}
int main()
{
while(!is_sorted(v.begin(),v.end()))
{
pray();
}
for(int x : v) cout << x << " ";
}
```

With this quite reliable method, one can hope that the array will be sorted in $$$O(Faith^{-1})$$$ time complexity.

I hope you enjoyed this trip through the bad sorting algorithms. This is merely an introduction and I have yet to see everything bad algorithms have to offer. I find them interesting because the way they manage to get such a bad complexity is quite creative.

Hello codeforcers, today you I will show how to order pizza through CSES. It is really cool!

The first step is to access the link. The link is : this

After you log in, you can select the flavor of pizza you want. However, it is in Finnish, so here is a translation of the menu:

Pizza selection: Bolognese: minced meat

Fruit: shrimp, mussel, tuna

Romeo: pineapple, blue cheese, shrimp, salami

Americano: pineapple, blue cheese, ham

Julia: pineapple, blue cheese, shrimp, ham

Quattro: pineapple, mushroom, shrimp, ham

Milan: champignon, caper, shrimp, tomato

Salami: champignon, salami, onion

Green Day: champignon, olive, paprika, onion, tomato

Empire: shrimp, ham, salami, onion, double cheese, garlic

Papa Special: blue cheese, olive, paprika, salami, onion

Opera Special: ham, salami, onion, tuna

Dillinger: ground beef, ham, salami, onion

Godfather: mushroom, shrimp, ham, asparagus, double cheese, garlic

Drivers Special: jalapeno, mozzarella cheese, pepperoni, garlic

Chicken Pizza: pineapple, blue cheese, chicken

Marco Polo Pizza: mushroom, minced meat, mozzarella cheese, paprika, onion

Mexicano: pineapple, jalapeno, pepperoni

Spicy Hot one: jalapeno, pepperoni, onion, tomato

Kebab Pizza: blue cheese, chili [green], kebab meat, onion, tomato

Calzone: kebab meat, onion, tomato

House Special: mushroom, kebab meat, pepperoni, onion, double cheese

Dello Chef: pineapple, feta cheese, olive, onion, tomato

Al Bacon: barbeque sauce, egg, bacon, onion

Formaggio pizza: four different cheeses, tomato

Al Taco: pineapple, barbeque sauce, jalapeno, chicken

Smetana Pizza: kebab meat, mozzarella cheese, onion, sour cream, jalapeno

Fantasy (4 fillings):

spice:

oregano

garlic

After you order, all you have to do is to enjoy the delicious pizza from CSES!

Hello guys, today I will do a tutorial on how to clean a vector, structure or something else in c++ really fast.

-A newbie may see this problem and try to solve it in linear time, for that we could just use the resources the C++ libraries offer us. In this particular case, the function `clear()`

would do it. However, it is an $$$ O(length) $$$ function and considering N can be very big, until $$$ 10^9 $$$, for an example, it cannot solve every problem of this type.

-A more experienced coder, like Errichto, will see this problem and immediately think about the * smart approach*. This approch consists of doing the following:

```
vector<vector<int>> auxiliary; //vector full of empty vectors
vector<int> v; //full of stuff (a lot) and we want to clear it fast
auxiliary.push_back({});
swap(auxiliary.back(),v);
```

**Boom!**, the complexity fell from ~$$$O(N)$$$ to ~$$$O(1)$$$. On my machine clearing vector of size $$$10⁸$$$ with the dumb approach took $$$0,789s$$$ and with the smart approach it took $$$0,438s$$$. Thus, in the next time you need to clear a lot of vectors, use the smart approach, your code will be much faster.**P.S**: this idea can easily be expanded for other structures, just substitute the 'vector' in the code for the structure you want and make the necessary changes to it.

As tourist's biggest fan, it was inevitable that I collected a substantial amount of tourist's pictures as the years went by. So now, I think I have enough of them and want to share them with the community.

**Very Young Tourist**

**Young Tourist**

**Happy Tourist**

**Very Happy Tourist**

**Awkward Tourist**

**Anime Antagonist Tourist**

**Impostor Tourist**(No fucking way that's him)

**Teenager Tourist**

**Anime MC Tourist**

**Pool Master Tourist**

**Rich Tourist**

**Relaxed Tourist**

**Tourist looking up Tourist**

**Model Tourist**

As you all know, I am very grateful for what tourist has inspired me to do and for what he has done to the community, inspiring not only me, but thousands of coders to go beyond what they previously thought they were capable of. So, lastly, my favorite version of tourist, and my way to show, as a member the Competitive Programming community, how important and grand this man is:

**Thank you Tourist**

I recently started my journey here on codeforces and today I did my first contest ( of many to come, hopefully ). The idea for the problems I did (A and B) are really cool, so I want to share it with whoever wants to see them.

**A** - The observation needed for this problem is that, given an optimal subarray, we have two cases. Let's assume you want to expand it to the right ( it's the same case if it's for the left ), if the next number is already on the array, **r-l-c(l,r)** increases by one, since **c(l,r)** stays the same and r increases by 1, so overall, the value increases by 1. If the next value is not on the array, **c(l,r)** increases by one and so does r, so overall, the value stays the same. That is, if you expand an optimal subarray, the value we want to maximize either stays the same or increases by 1. Then, all you need to do for a given test is to print 1 n.

**B** - I am still not sure how to prove that this idea is correct, but what I thought on this problem is that the optimal answer has all the multiples of the gcd of everyone.

Those are the ideas I had on this contest! The ideas, although simple, were not trivial to be seen, and that is where I think the beauty of CP and math problems are. I would like to thank the developers of the contest, Cocoly1990, waaitg and Imakf for the good time I had trying to solve it!

I am doing the ITMO course and the ideas are really cool. Glad I began doing CP!

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/10/2024 14:57:26 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|