Comments
On askd → My thoughts on 2138D1B, 13 months ago
0

i suggest after AI code double check it by human.

AI sometimes not able write hard bruteforce(like dfs game tree) correctly, and make very stupid mistake. I have seen it 998244353 times.
0

since error check is done by random sqrt(n), is it possible to gen a hack test, make the error maximum that over 1?
On Christine- → Cheating statistics, 14 months ago
0

can u add σ for every country rate? like if you test 100 country, there's ~1 country have a +3σ rate just because unluky.
On RyenCF → CP Language Tierlist, 14 months ago
-55

Ranking all programming languages on Codeforces from the bestto the absolute garbage:

  • PHP — trash tier (the logo is an elephant, so it’s beyond garbage).
  • Python — also trash tier (snake logo = instant L).
  • Java — straight garbage.
  • Ruby — complete trash.
  • C — absolute garbage. ...
  • Last place: C++ — Good taste. my friend.

Spoiler
+13

why sammyuri is a link but yuri isn't? .r
0

Srinivasa Jinglong told me this string in dream, after i wake up i checked it with C++
+22

use this string can get $$$\frac{n}{14} + O(\log)$$$ querys in div1C, better than offical solution $$$\frac{n}{13} + O(\log)$$$

Spoiler

after some optimization, can reach 80 queries limit.
+3

the formula is so simple so many people can guess it.

it's not on oeis, but discover that it is close to n! then you can find the pattern after check the different.
+19

Egocentric?
0

thanks for fast edtior
0

bravo work! My favorite time to read these types of blogs is in my free time.
0

kool, should i start farming rating reach red? codeforces community can see a red rtoll
+8

no one asked me

Spoiler

Since it seems that nobody has answered the question about FFT being used to solve catalan-like self convolutions in $$$O(n \log n)$$$: Yes, it can!

Basically you have to find the generating function then use FFT to compute it fast.

Let's say $$$H = \sum\limits_i \text{C}_i \cdot x^i$$$. We know that $$$\text{C}_n= \sum\limits_{ i \lt n} \text{C}_i \cdot \text{C}_{n-i-1}$$$.

$$$H^2 \cdot x = \sum\limits_{1 \le i} \sum\limits_ {j \lt i} \text{C}_j \cdot \text{C}_{i-j-1} \cdot x^i$$$ which is close to $$$H$$$.

$$$H^2 \cdot x = \sum\limits_{1 \le i} \text{C}_i \cdot x^i$$$. Thus $$$H^2 \cdot x + 1 = H$$$.

From here it's a matter of simplifying it: $$$H^2 \cdot x - H + 1 = 0$$$ ==> $$$ H = \frac{1 ± \sqrt{1 - 4x}}{2x}$$$. We chose the solution that satisfies our conditions. Since $$$\lim\limits_{x→0} \frac{1 -\sqrt{1 - 4x}}{2x}$$$ is $$$0$$$ and $$$\lim\limits_{x→0} \frac{1 + \sqrt{1 — 4}}{2x} = 1$$$, we take the second solution. Reminder that when we evaluate something at $$$0$$$ we take the value of the coeficient of $$$x^0$$$ of its power series which in this case should be $$$C_0$$$ which is $$$1$$$.

After this, you can compute $$$\sqrt{F(x)}$$$ in $$$O(n\log n)$$$ using FFT as explained in the editorial of the problem I linked below. You can read more details on https://cp-algorithms.com/algebra/polynomial.html#newtons-method although it doesn't explain exactly how to do it for sqrt.

This result is well known, it's even in wikipedia https://en.wikipedia.org/wiki/Catalan_number#First_proof and if you want a similar but harder/more dynamic exercise then solve https://codeforces.me/problemset/problem/438/E
On soullless → Mass cheating using AI, 19 months ago
-10

what do you think using weak sample and pretest?
-37

I asked
+14

https://en.wikipedia.org/wiki/3SUM

i think it's related (or i guess check "is answer = 0" is equal hard than 3SUM)
+1

reasonable, he solves much more problem than u. If both of u guys cheated, you shouldn't solve so less.
On run2wice → Sqrt-tree implementation, 21 month(s) ago
0

If someone invented support (even single-point update) for the sqrt-tree, he'd win a Turing Award.
-8

too boring
0

= perfix of A(n)
+71

AK costs 2700$ in CSGO

“Powerful and reliable, the AK-47 is one of the most popular assault rifles in the world. It is most deadly in short, controlled bursts of fire.”
0

link to flyer is 404
0

If you did not solve, did try a lot of ideas, and did not use the editorial: you did not improve.

why
+3

prob G seems like to :

https://www.facebook.com/codingcompetitions/hacker-cup/2024/practice-round/problems/C

and actually passable by this method
On OneBased → Blocked on Codeforces, 2 years ago
0

https://codeforces.me/blog/entry/133113
+10

so what, he is already 8 months offline
+65

We would like to thank:

  • Thanks to my cat for touch.
  • Thanks to earth don't kill me.
  • Thanks to the mouse keyboard monitor power cord.
  • Thanks to catGPT trying to replace human.
  • Thanks to me though it did nothing

.. wait to list more
+91

Best recent blog about AI.
0

https://codeforces.me/blog/entry/133941?#comment-1198316
-30

use asm instead of C++ then
0

It's me generate logic and key solution. not AI.
0

You may not input the problem statement, its summary, any excerpt, or a sub-problem into an AI-based system to receive ready-made code or natural language descriptions of the solution.

Can I do this: feed the solution(from me) into the AI and ask the AI to come up with the code.
+60

yes, i'm one of them
+18

Practice more
-25

不知道这个回答为啥被踩这么多，codeforces 人都他妈瞎的？一群屁都不懂废物在这瞎骂，换个红名号来评论就老实了。

随机数据下随便两个零一矢量在某一维度不正交概率是 (1/2)^2=1/4，正交概率为 3/4，那么总共 w 位每一位正交概率就是 (3/4)^w，于此期望在找 (4/3)^w 个随机矢量对之后找到一个正交的矢量对。

然后暴力查找所有的是 n^2 的，然后因为找到第一个矢量对之后就直接弹出了，所以是和 (4/3)^w 取 min（不过这里是期望）。

然后你这个 n=O(2^w) 算是我不严谨？不过计算机也不太会允许你放 2^64 个数字进去吧，稍微改一下的话就是 O(max(n log n,min(n^2,(4/3)^w))?

和 trie 没啥关系，直接全存到 vector 里然后跑 n^2 暴力和你这个差不多快。

#include "bits/stdc++.h"
using namespace std;
#define int long long
signed main() {
   mt19937_64 rng(random_device{}());
   vector<int> Q;
   int n;cin >> n;
   for(int i=1;i<=n;++i) Q.push_back(rng());
   for(int i:Q)
      for(int j:Q)
         if((i&j)==0) {
            cout << "YES" << endl;
            return 0;
         }
   cout << "NO" << endl;
}
+80

clang diag when back
+2

It's something $$$O(\min((\frac{4}{3})^w,n^2))$$$ under random data, nothing new.
0

After writing a brute force, it is found that if f(x) represents a first player playing on x, lose is 1 and win is 0.

$$$f(x)=[1\le x\%(n+n^2)\le n]$$$.

It's easy to prove this by induction.
On nyavim → Another Graph Editor!, 2 years ago
0

Can we make all solid lines disjoint, under the tree mod?
On nyavim → Another Graph Editor!, 2 years ago
+37

brilliant, it's 100% better than csacademy's graph editor!
+14

infact, up solved till F.
0

too classic
0

aren't doing everything useless? He could simply jump to another alt and come back, all anonymously. More importantly, he's making a profit. We simply couldn't stop him.
0

your rating is lower than me until you become a LGM...
+1

i dont know why but seems lf in codeforces is for long double, and f is for double.
On Utsavcc → Stuck on an XOR Question, 2 years ago
0

Yes, here we can enumerate the minimum and then use O(2^k·n) to solve. When an element no longer qualifies for the minimum value, we replace it with an element in the array that is just larger than it.
On Utsavcc → Stuck on an XOR Question, 2 years ago
0

Making each element as close to a1 as possible doesn't guarantee the greatest gap is the least, right? ​

For example, a2 = (a1-1 or a1+5). a3 = (a1+5 or a1+7).

​ You would choose "a1-1" versus "a1+5" with a difference of 6.

​ The correct choice is "a1+5" and "a1+5", the difference is 5.

And you can't handle the case if you have two closest values at the same time.
On weily → A Question about Miller-Rabin, 2 years ago
+3

https://miller-rabin.appspot.com/#

this website seems unstable, https://web.archive.org/web/20240709103303/https://miller-rabin.appspot.com/ here is
+16

this is what chaotic evil doing.
0

Do you have any point what EndlessDreams is doing? He didn't farming rating, but he is helping cheating. Sounds weird for me.
0

Is there any way to find him other than manually? codeforces needs to update its plagiarism checking system.
-93

Psychotic_D vs Geothermal

pertty sure cheated.
0

yes, you are right, I apologize for that.

but check my comment, i provide another two great pair.
0

i found another one of fourth pair.

https://codeforces.me/contest/1868/submission/222741630

https://codeforces.me/blog/entry/119512 he is a tester of their contest. it 100% a huge cheat group.

upd. another GM found, this time is even closer!!!

https://codeforces.me/contest/1868/submission/222742968
+5

i found another one of fourth pair.

https://codeforces.me/contest/1868/submission/222741630

https://codeforces.me/blog/entry/119512 he is a tester of their contest. it 100% a huge cheat group.

upd. another GM found, this time is even closer!!!

https://codeforces.me/contest/1868/submission/222742968
+16

check amenotiomoi , It's alt, obviously.

With a 2800 alt, what is the rating of the main account? maybe even LGM. I'm asking the blogger to find him.

he has 3space tab, maybe he is dxqwq?
+46

EndlessDreams also playing contest weird.

https://codeforces.me/contest/1844/standings/participant/158762330#p158762330 (pointless WA)

https://codeforces.me/contest/1891/standings/participant/166868017#p166868017 (hack -17)

https://codeforces.me/contest/1876/standings/participant/165140928#p165140928 (hack -24)

https://codeforces.me/contest/1895/standings/participant/167014741#p167014741 (WA then leave)

https://codeforces.me/contest/1806/standings/participant/151899002#p151899002 (even can't solve B, but solved E)

https://codeforces.me/contest/1876/submission/227137689 also skipped sub

seems cheated.
+19

wuhudsm
0

from a l of cp.
+5

3h hack = kills hacking function around UCT+8
+19

I asked
+8

best D i have seen, orz!!
+11

same here Damn_Its_Me
On aropan → CLIST News, 2 years ago
0

sorry disturb but cutting game is 2800* rated for clist rating?
+31

any random things like selling solutions can happen. We shouldn't presume guilt, but he had already cheated.
-39

I checked few contest you did, you are just too slow.

try be faster like guess without prove
0

https://en.cppreference.com/w/cpp/algorithm/sort

comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is less than (i.e. is ordered before) the second.

Just because the standard says so. There is no guarantee what will happen if you return less or equal.

0

in sort, you should use return a<b;, but not return a<=b, which give RTE or TLE or MLE or somethingelse except AC.
+64

i live on sun
+6

There is nothing stopping you from just choosing p1= random_int(33,1e8); to avoid any possible hacker
+6

The number of candidates for p is too small. switch to larger
+16

For a hash with 1e9 candidate random values, just only one modulus is very difficult to hack. But be careful how you choose random numbers, things like srand(time(0)) are hackable
+3

downvote who?
+22

For candidate hash quantities at the 1e18 level (which is actually quite common, for example, when the moduli are 998244353 and 1e9+7), because a collision at the 1e9 level is required for a birthday attack, the memory requirement becomes too large. It can be considered to degrade this into a process of checking 4e8 at a time until a collision is found (expecting around 15 iterations). For the 4e8 level check, radix sort can be employed. If duplicates are found, only one O(n log n) sorting operation is needed to locate their specific positions, and then the entire program can be terminated.

Because in reality, sorting at the 4e8 level with unsigned long long (ull) is very fast. In an educational 12-hour hack or even in regular contest(if someone has pre-written programs and distributed them), finding a collision is expected.

Code

If you want to use this code, don't forget to adjust maxn (lower or higher) to suit your computer.

The larger maxn brings higher unit efficiency, so it should be large as much as possible if there is enough memory.

If there is no length requirement for the attack string, here are more
0

B2

https://qr.ae/pswyHC
0

https://stackoverflow.com/questions/16740739/shortest-path-between-three-points

not sure is it best, ILP isn't in poly time.
+10

It is obvious that the number of paths is exponential
+26

minecraft is useable to create edtiorial picture of D1E.
+17

The summary is a failure. It has nothing related with char int count, it is completely caused by other issues.
On darkahmed → C++ BigInt and BigFloat., 3 years ago
+5

division and gcd can be faster than square also.
+14

If I can calculate a billion times a second, I can get IMO gold medal also.
On tbquan08hanoi → Substring Reversal, 3 years ago
0

prefix sum
-13

yea it seems true, but what happend on these weird comments?
-12

who asked
0

Reverse an N-bit quantity in parallel in 5 * lg(N) operations:

unsigned int v; // 32-bit word to reverse bit order
// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = ( v >> 16             ) | ( v               << 16);

Use this to flip all 32 integers in O(length*log w/w), then do a brute force flip with O(length/w).
0

Congrats there's no prize because it's april fools contest.
+14

bitmask operation is a weird limited 64 parallelism, start solving bitmask problem.
0

why you really care about him, are you his father or son?
On orz → C++20 is back, 3 years ago
+6

where did clang go, i really need it to check my codes ub
+6

For people who not interested in this blog, here's a more generalized spam method.

struct restart_integer {
  int value, time;
  static int gtime;
  void set(int x) {
    time = gtime;
    value = x;
  }
  int get(int x) {
    if (time < node::gtime)
      return 0;
    return value;
  }
  static void clear_all_node() { node::gtime++; }
};
int node::gtime = 0;

It uses less memory than the ds mentioned in the blog and is faster and easier to understand.

It's really hard for me to understand why invented this spread set.
+11

ok but i perfer std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
+4

u should stop trolling on me and get life
+45

after i wake up, i found my solution in dream just logicless shit.
+19

maybe alphacode should beat me first then tourist.
+41

is it div3?
+19

who setted this problem G and why
0

we can deduce easily by 3SUM-hard that if $$$a_i \le 10^9$$$, there's no(or very hard to find) a algo which is $$$\tilde{O}(n^2)$$$.
+37

as a tester, problems are fun.
+7

you killed contest.
+21

Actually, everyone in the comment section is on jiangly 's alternative account. If you don't believe it, I can change my account and make the same comments.