skywalkert's blog

By skywalkert, 9 months ago, ,

Hi, I'm here again requesting your help. _(xз」∠)_

This time it is a problem I encountered five years ago, and I still don't know its source.

Here is the problem:

We call a square grid of non-negative integers beautiful if no matter how we pick elements such that there is exactly one element picked in each row and each column, the sum of these elements is always the same.

You are asked to count the number of different $n \times n$ beautiful grids of non-negative integers, given the values of some places in the grid.

$1 \leq n \leq 50$, each given value is in $[0, 9]$ and it is guaranteed that the answer is not infinite.

For example, the number of beautiful grids with the following restriction is $24$.

0 ? ? ?
? 1 ? ?
? ? 2 ?
? ? ? 3

Tips: It can be reduced to counting the number of integer solutions $(x_1, x_2, \ldots, x_n)$ such that $0 \leq x_i \leq a_i$ ($a_i \leq 18$) for each $i$, and $x_i \leq x_j + w_{i, j}$ ($0 \leq w_{i, j} \leq 9$) for each $i, j$ ($i \neq j$).

• +49

By skywalkert, 9 months ago, ,

This is a problem I met on a Chinese online judge six years ago.

I'm not sure if it is a problem from another place.

Here's the problem:

Two different positive integers are considered similar if the numbers of their digits are the same, and the multisets of their digits are the same as well.

Given integers $l$ and $r$, count the number of integers $x$ ($l \leq x \leq r$) such that there is exactly one integer $y$ ($l \leq y \leq r$, $x \neq y$) satisfying that $x$ and $y$ are similar.

$1 \leq l \leq r \leq 10^{15}$

A few random examples of similar numbers:

• 6892, 6928, 6982, 8269 are similar
• 5986656, 5986665, 6556689, 6556698 are similar
• 2983321011, 2983321101, 2983321110, 3011122389 are similar
• 797776555322101, 797776555322110, 901122355567777, 901122355576777 are similar

UPD: I've solved this problem. I'll soon elaborate my solution in the comment.

• +20

By skywalkert, history, 9 months ago, ,

This editorial corresponds to 2017 Chinese Multi-University Training, BeihangU Contest (stage 1), which was held on Jun 25th, 2017.

There are 12 problems in total. You can solve them as a team member or an individual in a 5-hour contest. By the time you join as virtual participants, 770 teams, or even more, will compete with you virtually.

Editorial in the English version has been completed, which is a bit different from its Chinese version (mostly because I don't want bad editorials to ruin the contest, lol). However, for the sake of hiding spoilers, editorials are locked and will be shown as the following conditions are met:

• Editorials for the easiest 4 problems will be revealed after the replay (all unlocked);
• Each for the hardest 5 will be released if the corresponding problem has been solved by at least 5 users or teams on Codeforces::Gym (3 unlocked);
• Each for the others will be published when the relevant problem has been solved by at least 10 users or teams in virtual participation (including the replay) on Codeforces::Gym (all unlocked).

Or you can find solutions in comments?

Idea: skywalkert

solution

102253B - Balala Power!

Idea: sd0061

solution

102253C - Colorful Tree

Idea: sd0061

solution

102253F - Function

Idea: chitanda

solution

102253G - Gear Up

Idea: constroy

solution

102253H - Hints of sd0061

Idea: constroy

solution

102253I - I Curse Myself

Idea: sd0061

solution

102253J - Journey with Knapsack

Idea: skywalkert

solution

102253K - KazaQ's Socks

Idea: chitanda

solution

102253L - Limited Permutation

Idea: skywalkert

solution

Hope you can enjoy it. Any comments, as well as downvotes, would be appreciated.

• +49

By skywalkert, history, 10 months ago, ,

This editorial corresponds to 2018 Chinese Multi-University Training, BeihangU Contest (stage 5), which was held on Aug 6th, 2018. Moreover, this problem set was also used as Jingzhe Tang Contest 1 in Petrozavodsk Winter Camp on Jan 30th, 2019.

This post is now finished, in which I try to elaborate on notes, solutions and maybe some data generating. Alternatively, you can refer to an old published material, though I think the old English version did not explain something clearly.

102114A - Always Online

This problem requires to calculate $s$-$t$ min cut between any two vertices on a weighted cactus graph having $n$ vertices, denoted by $\mathrm{flow}(s, t)$. You need to report $\sum_{s < t}{(s \oplus t \oplus \mathrm{flow}(s, t))}$.

$n \leq 10^5$, $\sum{n} \leq 10^6$, weights are $\leq 10^9$.

Try to find some features of this graph.

solution
note

102114B - Beautiful Now

Given an integer $n$, you are asked to swap digits of $n$ in exactly $k$ turns. In each turn, you can swap two digits, which can be the same digit, but after this turn, $n$ must not have any leading zero. Calculate the maximal and the minimal values you can get in the end.

$100$ tests, $n, k \leq 10^9$.

This problem is yet another problem related to swapping. Can you solve it simply and elegantly?

solution 1
solution 2
note

Wait, wait, wait... Does it seem like a notorious coincidence with this problem? What? This problem has an incredible data range... ($n < 10^{1000}$) Does it really solvable??? Oh, I can't believe that!!! >_<

102114C - Call It What You Want

This problem asks you to factorize polynomial $(x^n - 1)$ over the field of integer polynomials. Besides, the statement contains some mathematical formulas you may need to apply.

$n \leq 10^5$, $\sum{n} \leq 5 \times 10^6$.

Maybe you just need some observation to solve.

solution
note

102114D - Daylight

Given an unweighted tree having $n$ vertices, you need to determine the union of two sets and report its size for $m$ queries, where each set is a set of vertices whose distances to a given vertice are no more than a fixed value, and the values for two sets are the same. However, queries are encrypted so you need to handle them one by one (online).

$10$ large tests, $n, m \leq 10^5$.

Emmm... A typical data structure problem, right?

Certainly I've found it on CodeChef. What? Why TLE???

solution

102114E - Everything Has Changed

A geometry problem to ensure you have checked in this contest. Read the statement for more details.

solution
note

102114F - Fireflies

Consider all the lattice points in a hypercube $\lbrace (x_1, x_2, \ldots, x_n) | 1 \leq x_i \leq p_i \rbrace$. Find a maximal subset such that there are no two points $(x_1, x_2, \ldots, x_n)$, $(y_1, y_2, \ldots, y_n)$ meeting the condition $x_i \leq y_i$ for all $i$. Report its size modulo $(10^9 + 7)$.

$n \leq 32$, $p_i \leq 10^9$.

How fast can you achieve to solve it?

solution

Here is an old problem with smaller data range. If anyone can tell me who the author is, I will add the credit soon.

There are $m$ operations over an array $a_1, a_2, \ldots, a_n$, each operation of which is to update $a_i$ $(l \leq i \leq r)$ by $\max(a_i, v)$. You need to determine the array after all the operations.

$n \leq 10^5$, $\sum{n} \leq 10^6$, $m \leq 5 \times 10^6$, $\sum{m} \leq 5 \times 10^7$. Besides, $l, r, v$ are randomly selected.

solution 1
solution 2
solution 3

102114H - Hills And Valleys

Given an array of length $n$, consisting of $0, 1, \ldots, 9$, your task is to reverse exactly one interval and then make the longest non-decreasing subsequence of the whole array as long as possible. The reversed interval is also required to report.

$n \leq 10^5$, $\sum{n} \leq 2 \times 10^5$.

solution

102114I - Innocence

Count the number of solutions for the equation $x_1 \oplus x_2 \oplus \cdots \oplus x_N = K$, where $x_i$ can be any integer in $[L, R]$. There are $Q$ queries with the same $N, L, R$ but different $K$.

$100$ large tests, $N \leq 10^9$, $0 \leq L, R, K < 2^{30}$, $Q \leq 100$.

solution
note

102114J - Just So You Know

A non-empty substring $B$ is selected from a given string $A$ of length $n$ with equal probability among all the possible substrings. You are given the string $A$ and asked to determine which the substring $B$ is. More precisely, you need to guess out what it looks like, instead of where it is in the string.

You can claim conjectures and then the jury will prove that it is true or false. You need to find a strategy to minimize the expected number of claiming and report the expected number as an irreducible fraction.

$n \leq 10^6$, $\sum{n} \leq 10^7$, character set size $\Sigma \leq 100$.

solution
note

102114K - Kaleidoscope

Count the number of non-isomorphic colored rhombic hexecontahedrons such that each face of each polyhedron are colored by one of $n$ given colors and the $i$-th color occurs on at least $c_i$ faces of each polyhedron. Report the number modulo $p$.

Two states are isomorphic if and only if one can transform into another by 3D space rotation.

In geometry, a rhombic hexecontahedron is nonconvex with $60$ golden rhombic faces with icosahedral symmetry.

$100$ large tests, $n \leq 60$, $1 \leq p < 2^{30}$.

solution
note

102114L - Lost In The Echo

Calculate the $n$-th term of the sequence A140606 in modulo $(10^9 + 7)$.

This term means the number of inequivalent expressions having $n$ distinct variables where each variable occurs exactly once, and only binary operators $+$, $-$, $*$, $/$ (and with parentheses) are permitted, which means unary minus or plus is forbidden. Two expressions are equivalent if and only if they can be simplified as the same rational expression.

$n = 1, 2, \ldots, 6 \times 10^4$.

solution
note

Which problem do you prefer or hate most? Feel free to share your thoughts in comments! ^_^

• +79

By skywalkert, history, 13 months ago, ,

Hi, all!

This year GP of China is scheduled on Sunday, March 10, 2019 at 11:00 (UTC+3). Writers have spent several days and nights creating and developing these problems. Hope you enjoy the contest!

UPD: Thanks to zimpha, Claris, quailty and me, here is editorial.

• +61

By skywalkert, history, 16 months ago, ,

SPOILER ALERT: Please do not read these hints if you want to solve some problems in this contest but haven't attempted yet.

DO NOT open if you want to solve them by yourself

• +62

By skywalkert, 16 months ago, ,

Greetings!

Ugh! That guy comes with another online-mirror and ruins my timeline again.

Here is the last one this year I could share with you, 2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest. It will start on Saturday, December 8, 2018 at 17:00 (UTC+8) and last for 5 hours. You are able to register 6 hours before the contest starts. However, before the registration starts, you may not view this contest on Gym. By the way, other Asia east continent regional contests shared by my friends and I could be found at Nanjing, Shenyang, Qingdao, Beijing and Xuzhou.

This onsite contest was held by Henan Polytechnic University on November 25th. It is the first time one regional contest was held on HPU, but it is quite memorable. Among the above 6 regional contest, I could definitely say Jiaozuo is the second easiest one. Though it may contain a few hard problems, several problems are solvable for beginners.

The problems are prepared by AHdoc, Claris, quailty and me. Thanks to zscc for discussing ideas, yefllower and niike0goood for testing, and MikeMirzayanov for developing wonderful platforms and kindly answering technical issues.

There is one thing we need to point out again. For everybody who has already read the problems, please do not to participate in this online-mirror contest or discuss solutions before the contest has ended. We have shared solution sketches (in simplified Chinese) in this site, so if needed, we would share some hints (in English) after online-mirror.

At the end of my post, I sincerely recommend authors of Asia-Hongkong (was held on Nov. 18) and Asia-East Continent Final (will be held on Dec. 16) would share problems with the public at any website. Your efforts should be rewarded!

UPD1: As a kindly reminder, our sponsor Jisuanke will hold another online-mirror contest soon after the contest on Gym, which will start on Sunday, December 9, 2018 at 12:00 (UTC+8) without the onsite board.

UPD2: Contest will start 1 hour in advance, as there is a CodeChef SnackDown contest soon after.

UPD4: Hints for this contest are published.

• +211

By skywalkert, 16 months ago, ,

Hello!

This weekend we would like to share an online-mirror of 2018-2019 ACM-ICPC, Asia Xuzhou Regional Contest with you. Please notice its start time is Saturday, December 1, 2018 at 18:00 (UTC+8) and we will be there for answering your questions. You are able to register 6 hours before the contest starts. However, before the registration starts, you may not view this contest on Gym. After the online-mirror contest, you can virtually participate at any time you want.

The 2018 ACM-ICPC Asia Xuzhou Regional Contest has been finished at China University of Mining and Technology, on October 28. Although 288 teams participated in the onsite contest, only 195 of them (including invited teams) finally solved at least one of 13 problems in 5 hours. Is the contest too hard? Or is the difficulty only applied to Chinese participants? We cannot get a conclusion clearly... Anyway, we hope these problems will benefit people who want to gain great results in ICPC.

The problems are prepared by AHdoc, Claris, quailty and me. Thanks to niike0goood and zscc for discussing ideas, yefllower and niike0goood for testing, Syloviaely for playing a crucial role in the contest, and MikeMirzayanov for developing Codeforces and Polygon.

Also, as a kindly reminder, Jisuanke will hold another online-mirror contest that will start on Sunday, December 2, 2018 at 12:00 (UTC+8).

We kindly ask everybody who has already read the problems not to participate this online-mirror contest or discuss any solution in public before the contest has ended. Your cooperation will be greatly appreciated.

• +121

By skywalkert, history, 17 months ago, ,

Hi all!

The 2018 ACM-ICPC Asia Shenyang Regional Contest has ended on October 21. At this site, 186 official teams and 6 guest teams selected from the preliminary online contest have competed in 5 hours, trying to solve 13 problems.

We are glad to invite you all from Codeforces, one of the greatest programming communities, to participate in its online-mirror contest, 2018-2019 ACM-ICPC, Asia Shenyang Regional Contest!

Please notice the online-mirror contest will start at an unusual time, Saturday, November 24, 2018 at 18:00 (UTC+8), when we are able to answer your questions during the online contest. By the way, we have added the onsite board, so when you are participating (during the mirror contest or virtual participation), you may take advantage of it!

This contest follows the ACM-ICPC rule and it will be unrated. Both personal registration and team registration are recommended. You may register for this contest 6 hours before it starts, but it is temporarily inaccessible before registration starts.

Also, many thanks to:

Besides, we kindly ask everybody who has already read the problems not to participate or discuss solutions in public before the contest has ended. Please keep the sportsmanship all the time!

Hope you enjoy the problems!

UPD1: Our sponsor Jisuanke will hold another online-mirror contest soon after the contest on Gym. If you missed this one, you could participate the other one, which will start on Sunday, November 25, 2018 at 12:00 (UTC+8) without the onsite board.

UPD3: Contest has ended. Any discussion will be greatly appreciated. If needed, we will discuss solutions after tomorrow.

• +145

By skywalkert, 17 months ago, ,

Hello, Codeforces!

We intend to share some ACM-ICPC regional contests with you! Here is one of them.

An online-mirror contest of 2018-2019 ACM-ICPC, Asia Nanjing Regional Contest will start on Saturday, November 17, 2018 at 18:00 (UTC+8). You may register for this contest 6 hours before it starts, but it is temporarily inaccessible before registration starts.

By the way, this contest will consist of 13 problems and you can solve them within 5 hours.

Wish you will learn great experience through that time!

Waaaaait!

There is another online-mirror contest, The 2018 ACM-ICPC Asia Qingdao Regional Contest (Mirror), which will be held at acm.zju.edu.cn on Saturday, November 10, 2018 at 12:00 (UTC+8), a week before the contest on Gym!

This contest is prepared by our friends from Zhejiang University and indeed a very interesting contest. If you are eager to participate, please do not hesitate to register a handle on it and take part in time!

P.S. Please do not discuss any solution before contests are finished. Thanks for your cooperation.

UPD1: Ranking that suits for Gym has been parsed from data provided by the host school (Nanjing University of Aeronautics and Astronautics). Enjoy it.