Author: crackersamdjam
Author: Dormi
Author: Ninjaclasher
Author: Plasmatic
Author: Plasmatic
1534F1 - Falling Sand (Easy Version)
Author: Dormi
1534F2 - Falling Sand (Hard Version)
Author: Dormi
Author: Aaeria
Author: Ninjaclasher
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | adamant | 157 |
6 | awoo | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | djm03178 | 153 |
Author: crackersamdjam
Let's say you know the colour of the first square, what colours can you figure out next?
Colour it like a chessboard, but there's more than one possible chessboard!
Brute force the color of the first square!
Author: Dormi
Consider the contribution of each pillar to the answer.
How does doing the operation on a pillar change the contribution to the answer?
You only want to do an operation on a pillar if the top cell contributes 2 to the answer.
Author: Ninjaclasher
Let's say you know whether you flipped the first cell or not, which new columns must be flipped?
Create a graph of $$$n$$$ nodes, draw an edge between two values if they both exist in the same column, what structure does this graph have?
It is a bunch of disjoint cycles (since each node has an in-degree of $$$2$$$).
Each cycle is independent, and there are $$$2$$$ ways to flip each cycle.
Author: Plasmatic
All trees are bipartite.
Find a $$$2$$$-coloring of a tree in one query.
You can find all nodes adjacent to one node in one query.
The min(number of black, number of white) nodes is $$$\leq \left \lfloor{\frac{n}{2}}\right \rfloor$$$.
Author: Plasmatic
Try to solve this problem for $$$n \leq 15$$$.
Try BFSing on the bitmasks.
Do we really care about what elements are in the bitmask?
Only the number of nodes in each mask matters.
1534F1 - Falling Sand (Easy Version)
Author: Dormi
Make a directed graph on the sand.
The graph should satisfy the following property: if a node $$$a$$$ can reach another node $$$b$$$ by a sequence of edges, disturbing $$$a$$$ will disturb $$$b$$$.
Compress scc's in the graph.
You must disturb all nodes with in-degree $$$0$$$ in the new graph.
1534F2 - Falling Sand (Hard Version)
Author: Dormi
Continued from $$$F1$$$, read that first.
The $$$a_i^\texttt{th}$$$ nodes from the bottom of each column must eventually be disturbed (call them special).
If a special node can reach another special node, you can delete that node.
Each node will remove some contiguous subsegment of the remaining special nodes' columns.
Find a greedy strategy to cover all of the columns.
Author: Aaeria
Author: Ninjaclasher
Hello, Codeforces!
Welcome to the Codeforces LATOKEN Round 1 (Div. 1 + Div. 2) supported by LATOKEN, that will start on Jun/13/2021 18:35 (Moscow time). It will be a combined rated round for both divisions (and div 3). Please, note the unusual start time.
All problems were created by Aaeria, crackersamdjam, Dormi, Ninjaclasher, and Plasmatic.
We would like to thank:
You will be given 8 problems and 180 minutes to solve them. This contest features at least one interactive problem, so we recommend reading the guide of interactive problems before the contest.
We hope that statements are short and pretests are strong and that you find the problems interesting! Good luck, have fun, and we wish everyone high ratings!
The scoring distribution will be announced closer to the beginning of the round.
Thanks to LATOKEN, winners will get awesome swag:
Random 10 participants outside of top-55, who solved at least one problem and participated in rated Codeforces rounds before, will get a t-shirt!
A few words from the LATOKEN team:
We welcome you to the intellectual battle between the best coders from around the world! LATOKEN strives to make trading crypto as easy as having a social media account. We are always looking for the best of the best to join our team. As a result, LATOKEN is currently in Coingecko’s Top 15 with over 600 000 app installs within just one year from its launch and 1m+ users in total. The emerging blockchain based financial systems will open exciting opportunities, because crypto is fully global and mostly independent of conservative banks.
If you want to become a part of something bigger, work remotely with a team of international professionals and change the world, contact our recruiters for internships and employment opportunities in the LATOKEN team. Use our bot or fill out the form below and tell us a little about yourself.
UPD: The scoring distribution is 500 — 1000 — 1250 — 1500 — 2250 — (1750 — 1250) — 3250 — 3500.
UPD: Editorial
Congratulations to the winners:
The prizes will be distributed in the next few days after we remove cheaters.
Name |
---|