codeforces-scrape

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

1369.md (14164B)


      1 Source: https://codeforces.com/blog/entry/79235
      2 
      3 #### [A. FashionabLee :](https://codeforces.com/contest/1369/problem/A)
      4 
      5 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic").
      6 
      7 **Brief Solution**
      8 
      9 $\mathcal Brief\;\mathcal Solution :$
     10 
     11 A $n$-regular convex polygon is beautiful if and only if $n \% 4 = 0$. ($\%$ is the modular arithmetic symbol)
     12 
     13 **Complete Proof**
     14 
     15 Tutorial is loading...
     16 
     17 **Python solution**
     18 
     19 ```
     20 t = int(input())
     21 for testcase in range(t):
     22     n = int(input())
     23     if(n%4 == 0) :
     24         print("Yes")
     25     else :
     26         print("No")
     27 ```
     28 
     29 **C++ solution**
     30 
     31 ```
     32 #include <iostream>
     33  
     34 using namespace std;
     35  
     36 int main(){
     37     int t;
     38     cin >> t;
     39     while(t--){
     40         int n;
     41         cin >> n;
     42         if(n % 4 == 0){
     43             cout << "YES\n";
     44         }
     45         else cout << "NO\n";
     46     }
     47 }
     48 ```
     49 
     50 #### [B. AccurateLee :](https://codeforces.com/contest/1369/problem/B)
     51 
     52 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic").
     53 
     54 **Brief Solution**
     55 
     56 $\mathcal Brief\;\mathcal Solution :$
     57 
     58 If the string $s$ is non-decreasing, then the answer is $s$ itself, otherwise the answer is $x+1$ zeroes and $y$ ones, where $x$ is the number of leading zeroes of the string $s$, and $y$ is the number of trailing ones of the string $s$.
     59 
     60 **Complete Proof**
     61 
     62 Tutorial is loading...
     63 
     64 **Python solution**
     65 
     66 ```
     67 t = int(input())
     68 for testcase in range(t):
     69     n = int(input())
     70     s = input()
     71     lef, rig, sw = 1, 1, 0
     72     for i in range(n-1):
     73         if(s[i] > s[i+1]):
     74             sw = 1
     75             break
     76     if(sw == 0):
     77         print(s)
     78         continue
     79     for i in range(n):
     80         if (s[i] == '1'):
     81             lef = i
     82             break
     83     for i in range(n-1, 0, -1):
     84         if (s[i] == '0'):
     85             rig = i
     86             break
     87     st = s[:lef] + '0' + s[rig+1:]
     88     print(st)
     89 ```
     90 
     91 **C++ solution**
     92 
     93 ```
     94 #include <iostream>
     95 #include <string>
     96  
     97 using namespace std;
     98  
     99 int main(){
    100     
    101     int t;
    102     cin >> t;
    103     while(t--){
    104         int n;
    105         cin >> n;
    106         string s;
    107         cin >> s;
    108         int sw = 1;
    109         for(int i = 1; i < s.size(); i++){
    110             if(s[i] < s[i-1])sw = 0;
    111         }
    112         if(sw){
    113             cout << s << '\n';
    114             continue;
    115         }
    116         string ans;
    117         for(int i = 0; i < s.size(); i++){
    118             if(s[i] == '1')break;
    119             ans.push_back('0');
    120         }
    121         ans.push_back('0');
    122         for(int i = s.size()-1; i >= 0; i--){
    123             if(s[i] == '0')break;
    124             ans.push_back('1');
    125         }
    126         cout << ans << '\n';
    127     }
    128 }
    129 ```
    130 
    131 #### [C. RationalLee :](https://codeforces.com/contest/1369/problem/C)
    132 
    133 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic") and [adedalic](/profile/adedalic "International Master adedalic").
    134 
    135 **Brief Solution**
    136 
    137 $\mathcal Brief\; \mathcal Solution$ :
    138 
    139 Give greatest elements to friends with $w_i = 1$. For the rest sort the elements in non-descending order of $a_i$ and sort the friends in non-ascending order of $w_i$ then give first $w_1-1$ elements to friend $1$, next $w_2-1$ elements to friend $2$ and so on, also give $k-i+1$-th greatest element to friend $i$ $(1 \le i \le k)$.
    140 
    141 **Complete Proof**
    142 
    143 Tutorial is loading...
    144 
    145 **Python solution**
    146 
    147 ```
    148 t = int(input())
    149 for tc in range(t):
    150     n, k = map(int, input().split())
    151     a = list(map(int, input().split()))
    152     w = list(map(int, input().split()))
    153     a.sort(reverse = True)
    154     w.sort()
    155     ii, l, r = k, 0, n-1
    156     ans = 0
    157     for i in range(k):
    158         if(w[i] > 1):
    159             ii = i
    160             break
    161         ans = ans+a[l]*2
    162         l = l+1
    163     for u in range(k-1, ii-1, -1):
    164         i = w[u]
    165         ans = ans + a[l] + a[r]
    166         r = r-i+1
    167         l = l+1
    168     print(ans)
    169 ```
    170 
    171 **C++ solution**
    172 
    173 ```
    174 #include <bits/stdc++.h>
    175 #define ll long long
    176 #define fr first
    177 #define sc second
    178 #define int ll
    179 
    180 using namespace std;
    181 const int MN = 2e5+7;
    182 
    183 vector<int> v[MN];
    184 
    185 signed main(){
    186     ios::sync_with_stdio(false);
    187     cin.tie();
    188     cout.tie();
    189 
    190     int t;
    191     cin >> t;
    192     while(t--){
    193         int n, k;
    194         cin >> n >> k;
    195         for(int i = 0; i <= n; i++)v[i].clear();
    196         ll a[n], w[k];
    197         for(int i = 0; i < n; i++){
    198             cin >> a[i];
    199         }
    200         for(int i = 0; i < k; i++){
    201             cin >> w[i];
    202         }
    203         sort(w, w+k);
    204         sort(a, a+n);
    205         for(int i = 0; i < k/2; i++)swap(w[i], w[k-i-1]);
    206         int po = 0;
    207         for(int i = 0; i < n-k; i++){
    208             while(w[po] == v[po].size()+1)po++;
    209             v[po].push_back(a[i]);
    210         }
    211         ll ans = 0;
    212         int qf = 1;
    213         for(int i = 0; i < k; i++){
    214             ans += a[n-i-1];
    215             if(v[i].size())ans += v[i][0];
    216             else ans += a[n-qf], qf++;
    217         }
    218         
    219         cout << ans << '\n';
    220     }
    221 }
    222 ```
    223 
    224 #### [D. TediousLee :](https://codeforces.com/contest/1369/problem/D)
    225 
    226 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic").
    227 
    228 **Brief Solution**
    229 
    230 $\mathcal Brief \mathcal Solution$ :
    231 
    232 Realize that a RDB of level $i$ is consisted of a vertex (the root of the RDB of level $i$) connected to the roots of two RDBs of level $i-2$ and a RDB of level $i-1$.
    233 
    234 Run a DP and calculate the answer for each level $i$ ($ 3 \le i \le 2 \cdot 10^6$), then $dp_i = 2 \cdot dp_{i-2} + dp_{i-1} + (i \% 3 == 0?4:0)$.
    235 
    236 **Complete Proof**
    237 
    238 Tutorial is loading...
    239 
    240 **Python solution**
    241 
    242 ```
    243 v = []
    244 v.append(0)
    245 v.append(0)
    246 v.append(0)
    247 v.append(4)
    248 v.append(4)
    249 mod = int(1e9+7)
    250 for i in range (5, 2000010):
    251     v.append(max(((2*v[i-2])+v[i-1])%mod,((4*v[i-4])+4*v[i-3]+v[i-2]+4)%mod))
    252 t = int(input())
    253 for _ in range(t):
    254     print(v[int(input())])
    255 ```
    256 
    257 **C++ solution**
    258 
    259 ```
    260 #include <bits/stdc++.h>
    261 #define ll long long
    262 using namespace std;
    263 
    264 const int mod = int(1e9+7);
    265 const int MN = int(2e6+7);
    266 
    267 int dp[MN];
    268 
    269 signed main(){
    270     ios::sync_with_stdio(false);
    271     cin.tie();
    272     cout.tie();
    273     dp[0] = dp[1] = 0;
    274     dp[2] = 4;
    275     for(int i = 3; i < MN; i++){
    276         long long w = dp[i-1];
    277         w += 2*dp[i-2] + (i % 3 == 2)*4;
    278         w %= mod;
    279         dp[i] = w;
    280     }
    281 
    282     int t;
    283     cin >> t;
    284     while(t--){
    285         int n;
    286         cin >> n;
    287         n--;
    288         cout << dp[n]%mod << '\n';
    289     }
    290 }
    291 ```
    292 
    293 Challenge : Try solving problem D for $n \le 10^{18}$. (no matrix-multiplication)
    294 
    295 #### [E. DeadLee :](https://codeforces.com/contest/1369/problem/E)
    296 
    297 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic").
    298 
    299 **Hints**
    300 
    301 $\mathcal Hints$ :
    302 
    303 1. Find some greedy approaches. Its guessable that the problem is greedy.
    304 2. Define $s_i$ for food $i$ equal to the number of guys who likes food $i$. Then find some condition which is enough to be sure that no answer exist.
    305 3. See the last friend in a suitable permutation. What food will he eat?
    306 4. Its easy to see that if $\forall 1 \le i \le m \Rightarrow s_i \gt w_i$, then no answer exist.
    307 5. If a food $i$ exist such that $s_i \le w_i$, then what will happen to the friends who like this food? They can always eat this food no matter what happens, so lets call them as late as possible(so its less likely for them to eat more than one plate). Now continue the process with rest of the friends and foods.
    308 
    309 **Brief Solution**
    310 
    311 $\mathcal Brief\;\mathcal Solution$ :
    312 
    313 Define $s_i$ equal to the number of friends who likes food $i$. If for some $i$, $s_i \le w_i$ then place all the friends who likes food $i$ in the end of the permutation and erase them and continue doing the same thing for the rest of the friends and foods
    314 
    315 It's easy to see that if the set of friends became empty then the permutation we constructed is suitable(and no one would eat Lee), otherwise Lee has to buy more food!!
    316 
    317 **Complete Proof**
    318 
    319 Tutorial is loading...
    320 
    321 **Python solution**
    322 
    323 ```
    324 import sys
    325 import heapq
    326 
    327 inputarray = [int(x) for x in sys.stdin.read().split()]
    328 
    329 n, m = inputarray[0], inputarray[1]
    330 
    331 s, w = [], []
    332 for i in range(2, n+2):
    333     w.append(inputarray[i])
    334 
    335 g, eg, foodm, friendm, x, y = [], [], [], [], [], []
    336 
    337 for i in range(n):
    338     s.append(0)
    339     foodm.append(0)
    340     g.append([])
    341 
    342 for i in range(m):
    343     friendm.append(0)
    344     x.append(0)
    345     y.append(0)
    346     
    347 inppo = n+2
    348 for i in range(m):
    349     x[i], y[i] = inputarray[inppo], inputarray[inppo+1]
    350     inppo = inppo+2
    351     x[i] = x[i]-1
    352     y[i] = y[i]-1
    353     u = x[i]
    354     v = y[i]
    355     s[u] = s[u]+1
    356     s[v] = s[v]+1
    357     g[u].append(i)
    358     g[v].append(i)
    359     eg.append((v, u))
    360 
    361 myq = []
    362 
    363 ans = []
    364 
    365 for i in range(n):
    366     heapq.heappush(myq, (-w[i]+s[i], i))
    367 
    368 while len(myq): 
    369     u = myq[0]
    370     heapq.heappop(myq)
    371     if u[0] != -w[u[1]]+s[u[1]]:
    372         continue
    373     if(u[0] > 0):
    374         print("DEAD")
    375         sys.exit()
    376     foodm[u[1]] = 1
    377     sw = 1
    378     for i in g[u[1]]:
    379         if friendm[i] == 0:
    380             friendm[i] = 1
    381             if y[i] == u[1]:
    382                 x[i], y[i] = y[i], x[i]
    383             s[x[i]] = s[x[i]]-1
    384             s[y[i]] = s[y[i]]-1
    385             heapq.heappush(myq, (-w[y[i]]+s[y[i]], y[i]))
    386             ans.append(i)
    387             if(len(ans) == m):
    388                 sw = 0
    389                 break;
    390     if(sw == 0):
    391         break
    392 print("ALIVE")
    393 for i in ans[::-1]:
    394     print(i+1, end=" ")
    395 ```
    396 
    397 **C++ solution**
    398 
    399 ```
    400 #include <bits/stdc++.h>
    401 
    402 #define ll long long
    403 #define fr first
    404 #define sc second
    405 #define pii pair<int, int>
    406 #define all(v) v.begin(), v.end()
    407 
    408 using namespace std;
    409 const int MN = 2e5+7;
    410 
    411 int x[MN], y[MN], s[MN], w[MN], mark[MN], colmark[MN];
    412 
    413 vector<int> v[MN], a;
    414 vector<pii> f;
    415 
    416 priority_queue<pii, vector<pii>, greater<pii>> pq;
    417 
    418 signed main(){
    419     ios::sync_with_stdio(false);
    420     cin.tie();
    421     cout.tie();
    422     int n, m;
    423     cin >> n >> m;
    424     for(int i = 1; i <= n; i++)cin >> w[i];
    425     for(int i = 0; i < m; i++){
    426         cin >> x[i] >> y[i];
    427         s[x[i]]++;
    428         s[y[i]]++;
    429         v[x[i]].push_back(i);
    430         v[y[i]].push_back(i);
    431     }
    432     for(int i = 1; i <= n; i++){
    433         if(s[i])pq.push({max(0, s[i]-w[i]), i});
    434         else colmark[i] = 1;
    435     }
    436 
    437     while(pq.size()){
    438         auto q = pq.top();
    439         pq.pop();
    440         if(q.fr != max(0, s[q.sc]-w[q.sc]))continue;
    441         if(q.fr > 0){
    442             cout << "DEAD\n";
    443             exit(0);
    444         }
    445         int id = q.sc;
    446         vector<int> wt;
    447         for(auto u : v[id]){
    448             if(mark[u])continue;
    449             a.push_back(u);
    450             if(x[u] == id)
    451                 swap(x[u], y[u]);
    452             if(!colmark[x[u]])wt.push_back(x[u]);
    453             mark[u] = 1;
    454         }
    455         sort(all(wt));
    456         for(int i = 0; i < wt.size(); i++){
    457             s[wt[i]]--;
    458             if(i == wt.size()-1 || wt[i+1] != wt[i]){
    459                 if(s[wt[i]]){
    460                     if(max(0, s[wt[i]]-w[wt[i]]) == 0)colmark[wt[i]] = 1;
    461                     pq.push({max(0, s[wt[i]]-w[wt[i]]), wt[i]});
    462                 }
    463             }
    464         }
    465     }
    466     cout << "ALIVE\n";
    467     for(int i = 0; i < a.size()/2; i++)swap(a[i], a[a.size()-i-1]);
    468     for(auto u : a){
    469         cout << u+1 << ' ';
    470     }
    471     cout << '\n';
    472 }
    473 ```
    474 
    475 #### [F. BareLee :](https://codeforces.com/contest/1369/problem/F)
    476 
    477 Invented by [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic") and [AS.82](/profile/AS.82 "Candidate Master AS.82").
    478 
    479 **Brief Solution**
    480 
    481 $\mathcal Brief\; \mathcal Solution$ :
    482 
    483 Define $win_{s,\,e}$ ($s \le e$) equal to $1$ if Lee can win the game when $s$ is written on the board, and equal to $0$ otherwise, also define $lose_{s,\,e}$ the same way.
    484 
    485 Win :
    486 
    487 If $e$ is odd then if $s$ is odd Lee loses otherwise Lee wins. So if $e$ is even then :
    488 
    489 * if $\frac e 2 \lt s \le e$ then if $s$ is odd then Lee wins, otherwise Lee loses;
    490 * if $\frac e 4 \lt s \le \frac e 2$ then Lee wins;
    491 * if $s \le \frac e 4$ then the answer is equal to $win_{s,\, \lfloor \frac e 4 \rfloor}$.
    492 
    493 Lose :
    494 
    495 If $e \lt 2 \cdot s$, then Lee can immediately lose, otherwise the answer is equal to $\displaystyle win_{s,\, \lfloor \frac e 2 \rfloor}$.
    496 
    497 **Complete Proof**
    498 
    499 Tutorial is loading...
    500 
    501 **Python solution**
    502 
    503 ```
    504 import sys
    505 
    506 inpy = [int(x) for x in sys.stdin.read().split()]
    507 
    508 def win(s, e) :
    509     if e == s :
    510         return False
    511     if e == s+1 :
    512         return True
    513     if e % 2 == 1 :
    514         if s % 2 == 1 :
    515             return False
    516         return True
    517     q = e//4
    518     
    519     if s <= q :
    520         return win(s, q)
    521     q = e//2
    522     if(s > q) :
    523         return (e-s) % 2 == 1
    524     return True
    525 
    526 def lose(s, e) :
    527     q = e//2
    528     if(s > q) :
    529         return True
    530     else :
    531         return win(s, q)
    532 
    533 t = inpy[0]
    534 start = (True, False)
    535 inpo = 1
    536 v = (True, True)
    537 
    538 for tc in range(t):
    539     if(inpo+1 >= len(inpy)) :
    540         print('wtf')
    541     s, e = inpy[inpo], inpy[inpo+1]
    542     inpo = inpo+2
    543     v = ((win(s, e), lose(s, e)))
    544     if start[0] and start[1] :
    545         break
    546     if (not start[0]) and (not start[1]) :
    547         break
    548     if start[1] :
    549         v = (not v[0], not v[1])
    550     start = (v[1], v[0])
    551 
    552 if((start[0] != True and start[0] != False) or (start[1] != True and start[1] != False)) :
    553     print('wtf')
    554 sw = 2
    555 if start[1] :
    556     sw = sw-1
    557     print(1, end = ' ')
    558 else :
    559     sw = sw-1
    560     print(0, end = ' ')
    561 if start[0] :
    562     print(1)
    563     sw = sw-1
    564 else :
    565     print(0)
    566     sw = sw-1
    567 if sw :
    568     print(wtf)
    569 ```
    570 
    571 **C++ solution**
    572 
    573 ```
    574 #include <iostream>
    575 #include <vector>
    576 #include <string>
    577 #define fr first
    578 #define sc second
    579 #define ll long long
    580 #define int ll
    581 
    582 using namespace std;
    583 
    584 const int MN = 1e5+7;
    585 
    586 pair<int, int> c[MN];
    587 
    588 int chk(ll s, ll e){
    589     if(e == s)return 0;
    590     if(e == s+1)return 1;
    591     if(e & 1){
    592         if(s & 1)return 0;
    593         return 1;
    594     }
    595     if(s <= e/4)
    596         return chk(s, e/4);
    597     if(s > (e/4)*2)return ((e-s)&1);
    598     else return 1;
    599 }
    600 
    601 int lck(ll s, ll e){
    602     if(s*2 > e)return 1;
    603     int w = e/2 + 3;
    604     while(w*2 > e)w--;
    605     return chk(s, w);
    606 }
    607 
    608 signed main(){
    609     ios::sync_with_stdio(false);
    610     cin.tie();
    611     cout.tie();
    612 
    613     int n;
    614     cin >> n;
    615 
    616     for(int i = 0; i < n; i++){
    617         ll x, y;
    618         cin >> x >> y;
    619         c[i] = {chk(x, y), lck(x, y)};
    620     }
    621 
    622     int f = 1;
    623     int s = 0;
    624     for(int i = 0; i < n; i++){
    625         if(f == 1 && s == 1)break;
    626         if(f == 0 && s == 0)break;
    627         if(s == 1) c[i].fr^=1, c[i].sc^=1;
    628         f = c[i].sc;
    629         s = c[i].fr;
    630     }
    631     cout << s << ' ' << f << '\n';
    632 }
    633 ```