There are some seemingly strange English abbreviations in our China’s CP circle, which seem not to be used by English speakers. I suspect that these names are created by Chinese people. For example:

• We often call the ICPC and the CCPC (China Collegiate Programming Contest) “ACM”, and call an ICPC or CCPC participant an “ACMer”. Now in spoken language, “ACM” is more like a symbol of competitive programming in ICPC style (≈ CP), like in “my ACM career” (我的 ACM 生涯), “school ACM training team” (学校 ACM 集训队), and “we ACMers are like this” (我们 ACMer 是这样的).
• We often call the contests NOI (National Olympiad in Informatics, China) and the NOIP (National Olympiad in Informatics in Provinces, China) “OI”, and call an NOI or NOIP participant an “OIer”.
• Some programming problem may accept multiple answers, and in China, we say that this problem uses “special judge”, even abbreviated as “SPJ”. Usually, a “special judge” is a special program written by the problem setter to check if the output content is correct. (Note that in Codeforces, each problem uses the so-called “special judge”, which is called “checker”. Even a problem that accepts a single answer uses the checker to compare the output content with the answer.)
• We often call AtCoder “AT” or “ATC”, but not “AC”, although “AC” is the official abbreviation of AtCoder (like in “AC Library”). Maybe they do not call AtCoder “AC” to not confuse “AtCoder” with “Accepted”, since the verdict “Accepted” is also abbreviated as “AC”.
• The largest ICPC regional contest to include China, the ICPC Asia East Continent Final Contest, is often called “(ICPC) EC Final” by many Chinese people.

However:

• When I search Microsoft Bing for “ACMer”, “OIer”, “special judge” and “EC Final”, I cannot find any search results other than Chinese, or English written by Chinese people (for “special judge”, I can only find the results about a special judge on the court …)
• ACM is the name of an association in the USA, not of a contest. ACM used to hold the ICPC (once named “ACM-ICPC”), but not now. So I think it is inappropriate to use the word “ACM”.
• In a blog about “special judge”, a comment asks what “special judge” means.
• If “EC Final” is widely used among English speakers, then “WC Final” (Asia West Continent Final Contest) must exist on the Internet, but I cannot find anything about it. And I do not know why “Asia East Continent” can be abbreviated as “EC” instead of “AEC” or “Asia EC”.

So my questions are:

• Do English speakers actually say the above terms?
• If the term “special judge” is not used by English speakers, what do they call the so-called “special judge”?
• How do you think about these English abbreviations in China?

In Polygon, when I name my solution file with substring “update”, it warned me of the “bad substring”. What does it mean? Why is it “bad”?

Another earlier blog about the same issue was posted here: Weird naming limitations for checkers in Polygon, but there is no answer.

Given a positive integer $$$n$$$, how many integers $$$z$$$ are there such that there exist two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$) such that $$$z = x \cdot y$$$?

For example, for $$$n = 5$$$, there are $$$14$$$ integers that can be legal values of $$$z$$$, which are: $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$8$$$, $$$9$$$, $$$10$$$, $$$12$$$, $$$15$$$, $$$16$$$, $$$20$$$, and $$$25$$$.

Is there any fast algorithm to solve this problem? At least, it should be much faster than the brute force solution (time complexity: $$$O(n^2)$$$).

Assume two integers $$$a$$$ and $$$b$$$ ($$$1 \le b < a$$$) that form an ordered integer pair $$$(a, b)$$$. We can perform a Euclidean division on it, which will make it $$$(b, a \bmod b)$$$. If we keep performing this division, then $$$b$$$ will eventually be $$$0$$$. We define $$$k$$$ as the number of Euclidean divisions needed to make $$$b$$$ equal $$$0$$$.

Example: $$$(19, 8)$$$ → $$$(8, 3)$$$ → $$$(3, 2)$$$ → $$$(2, 1)$$$ → $$$(1, 0)$$$. We perform $$$4$$$ divisions until $$$b$$$ equals $$$0$$$, so $$$k = 4$$$.

With the value of $$$k$$$ specified ($$$1 \le k \le 10^9$$$), how to find any ordered integer pair $$$(a, b)$$$ ($$$1 \le b < a \le 10^{18}$$$) that needs exactly $$$k$$$ Euclidean division to make $$$b$$$ equal $$$0$$$? If there does not exist such a pair, report it.

I am also curious about one question: it is all known that the Euclidean algorithm is fast, but the speed of the algorithm is determined by $$$k$$$, so may $$$k$$$ be infinitely large?

A binary array is an array where all elements are either $$$0$$$ or $$$1$$$.

For any binary array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, we can figure out the corresponding unique array $$$b_1, b_2, \ldots, b_n$$$ of length $$$n$$$ that satisfies $$$b_1 = a_1$$$ and $$$b_i = a_i \oplus a_{i - 1}$$$ for any $$$2 \le i \le n$$$, where $$$\oplus$$$ denotes XOR operation. Then count the number of $$$1$$$-s in array $$$a$$$, count the number of $$$1$$$-s in array $$$b$$$, and find the minimum of them as the “score” of array $$$a$$$.

For example, provided $$$a = [1, 0, 1, 1, 0, 0]$$$, then $$$b = [1, 1, 1, 0, 1, 0]$$$. The number of $$$1$$$-s in array $$$a$$$ is $$$3$$$, the number of $$$1$$$-s in array $$$b$$$ is $$$4$$$, and the minimum of them is $$$3$$$, so the “score” of array $$$a = [1, 0, 1, 1, 0, 0]$$$ is $$$3$$$.

For any given $$$n$$$, what is the maximum “score” of array $$$a$$$ among all possible arrays $$$a$$$? And how to construct a possible array $$$a$$$?

Does Polygon crash?

UPD: Fixed.

Is there any algorithm to solve the following problem within several seconds? If not, what if $$$1 \le a_i \le 10^9$$$, $$$1 \le b \le 10^9$$$?

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$. Then you should process $$$q$$$ queries. In each query, you are given an integer $$$b$$$. How many elements of the array $$$a$$$ are the factors of $$$b$$$?

We say $$$a$$$ is a factor of $$$b$$$, if and only if there exists an integer $$$c$$$ such that $$$a \cdot c = b$$$.

Constraints: $$$1 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$, $$$1 \le a_i \le 10^{18}$$$, $$$1 \le b \le 10^{18}$$$.

For example, $$$n = 3$$$, $$$a = \{ 4, 6, 17 \}$$$, $$$q = 4$$$:

• $$$b = 12$$$, answer is $$$2$$$.
• $$$b = 34$$$, answer is $$$1$$$.
• $$$b = 102$$$, answer is $$$2$$$.
• $$$b = 40800$$$, answer is $$$3$$$.

Mashup editing interface contains a misspelled word “virtaul” (virtual). Looking forward to a correction.

I’m Chinese. Sorry if my English had some grammar mistakes.

In a recent contest: Codeforces Round 871 (Div. 4), I saw a “Successful hacking attempt” in the “Hacks” list. But I think this hacking might involve cheating.

Look at this hacked submission: 204925830.

The source code of the defender contained a “landmine”, which means that for some corner case (unlikely contained in test data), the code wouldn’t be accepted, which was intentionally designed for hackers.

Following was the source code (GNU C++14). Note the corner case in the code that would make it wrong.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;

string s1,s2;
int t;

int main(){
	scanf("%d",&t);
	s1 = "codeforces";
	int ans;
	while(t --){
		cin >> s2;
		if(s2 == "xxxxxxxxxx"){ // Here! The corner case
			puts("-1"); // Wrong output
			return 0;
		}
		ans = 0;
		for(unsigned int i = 0 ; i < s1.size() ; ++i){
			if(s1[i] != s2[i])
				++ans;
		}
		printf("%d\n",ans);
	}
	return 0;
}

Therefore, for the case “xxxxxxxxxx”, the code would definitely get “Wrong answer”. Unluckily (or luckily, for the hacker), this corner case wasn’t contained in test data.

Then view the hacking test.

1
xxxxxxxxxx

What a “coincidence”!

But do you think someone may intentionally leave a “landmine” for others to hack, and give himself/herself a chance to lose $$$50$$$ points? Anyone knows it’s impossible.

And see the rating of the defender: Newbie. I’m not discriminating against Newbies (since so am I), but this is one of the typical features of an alt account. In addition, he/she participated in few contests so far.

So, most likely, the contestant created an alt account, used his/her alt account to submit a “landmine code”, used his/her main account to hack it, to let the main account get extra $$$100$$$ points. Or maybe, it’s his/her friend, not his/her alt account. But that doesn’t matter.

This is why I suspect that this hacking may involve cheating.

I’m not targeting any user. This example is just one of all. Actually I saw at least three such examples of “landmine code” hackings only in this contest (where some of the defenders are even Unrated).

Cheating is shameful, but a flawed rule may also become a breeding ground for cheating behaviors. I think this phenomenon should be controlled.