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.