1474.md (3853B)
1 Source: https://codeforces.com/blog/entry/86933 2 3 Thank you for participating in the contest! I hope you enjoyed the tasks. Here is an editorial with hints. 4 5 [1474A - Puzzle From the Future](/contest/1474/problem/A "Codeforces Round 696 (Div. 2)") 6 7 **Hint 1** 8 9 Hint $1$: Should we always make first digit of $d$ not equal to $0$? How can we do it? 10 11 **Hint 2** 12 13 Hint $2$: Try to choose such $a$ that $d$ will have $n$ digits. 14 15 **Editorial** 16 17 Tutorial is loading... 18 19 **Solution** 20 21 [104840922](https://codeforces.com/contest/1474/submission/104840922) 22 23 [1474B - Different Divisors](/contest/1474/problem/B "Codeforces Round 696 (Div. 2)") 24 25 **Hint 1** 26 27 Hint $1$: Integer have exactly $4$ divisors, if it is of form $pq$ or $p^3$ for some primes $p$ and $q$. In the first case it have divisors $1$, $p$, $q$, $pq$. In the second case it have divisors $1$, $p$, $p^2$, $p^3$. 28 29 **Hint 2** 30 31 Hint $2$: Instead of finding integer with at least $4$ divisors, find integer with exactly $4$ divisors. 32 33 **Hint 3** 34 35 Hint $3$: Let $p$ be the smallest prime factor of $a$. Then, $p \geq d + 1$. 36 37 **Editorial** 38 39 Tutorial is loading... 40 41 **Solution** 42 43 [104840809](https://codeforces.com/contest/1474/submission/104840809) 44 45 [1474C - Array Destruction](/contest/1474/problem/C "Codeforces Round 696 (Div. 2)") 46 47 **Hint 1** 48 49 Hint $1$: How does $x$ changes after each operation? 50 51 **Hint 2** 52 53 Hint $2$: Suppose, that you know $x$. What pairs of elements can you throw out now? 54 55 **Hint 3** 56 57 Hint $3$: Suppose, that you did some operations. Note, that if you have integer $b$ that is greater or equal to $x$ and $b$ is still in array $a$, you can't remove $b$ from $a$, thus you can't throw out all elements of $a$. 58 59 **Hint 4** 60 61 Hint $4$: You don't know $x$ only before the first operation and $n \leq 1000$. 62 63 **Editorial** 64 65 Tutorial is loading... 66 67 **Solution** 68 69 [Solution with set](https://codeforces.com/contest/1474/submission/104840760) 70 71 [Solution without set](https://codeforces.com/contest/1474/submission/104845408) 72 73 [1474D - Cleaning](/contest/1474/problem/D "Codeforces Round 696 (Div. 2)") 74 75 **Hint 1** 76 77 Hint $1$: How to solve the promblem if we are not allowed to use a superabilty (in linear time)? 78 79 **Hint 2** 80 81 Hint $2$: Look at the first pile. There is only one way to remove stone from the first pile. 82 83 **Hint 3** 84 85 Hint $3$: If you swap $i$-th and $(i + 1)$-th piles of stones, nothing changes in way you remove stones from $1$-st, $2$-nd, $\ldots$, $(i - 2)$-th piles. 86 87 **Hint 4** 88 89 Hint $4$: Look at the problem from the both sides: from the beginning of $a$ and from the end of $a$. 90 91 **Editorial** 92 93 Tutorial is loading... 94 95 **Solution** 96 97 [104840665](https://codeforces.com/contest/1474/submission/104840665) 98 99 [1474E - What Is It?](/contest/1474/problem/E "Codeforces Round 696 (Div. 2)") 100 101 **Hint 1** 102 103 Hint $1$: How many operations will robot make in the worst case? 104 105 **Hint 2** 106 107 Hint $2$: How many times can robot spend $(n - 1)^2$ time on $1$ operation? 108 109 **Hint 3** 110 111 Hint $3$: How many times can robot spend $(n - 2)^2$ time on $1$ operation? It is easyer to think about number of operations with time greater or equal to $(n - 2)^2$. 112 113 **Hint 4** 114 115 Hint $4$: Instead of operation from the statement we can apply the following operation to $q$ which is initially an identity permutation: 116 117 * Select $i$ such that $q_i = i$ and any $j$ and swap $q_i$ and $q_j$ in $(j - i) ^ 2$ seconds. 118 119 Then we make $p$ = $q$ and do operations in reversed order. 120 121 **Editorial** 122 123 Tutorial is loading... 124 125 **Solution** 126 127 [104840536](https://codeforces.com/contest/1474/submission/104840536) 128 129 [1474F - 1 2 3 4 ...](/contest/1474/problem/F "Codeforces Round 696 (Div. 2)") 130 131 **Bonus** 132 133 Can you solve this problem with a bigger $n$? 134 135 **Editorial** 136 137 Tutorial is loading... 138 139 **Solution** 140 141 [104840452](https://codeforces.com/contest/1474/submission/104840452) 142 143 Good luck in your future contests!