codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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!