codeforces-scrape

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

1327.md (11157B)


      1 Source: https://codeforces.com/blog/entry/75147
      2 
      3 [1327A - Sum of Odd Integers](/contest/1327/problem/A "Educational Codeforces Round 84 (Rated for Div. 2)")
      4 
      5 Idea: [vovuh](/profile/vovuh "Master vovuh")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (vovuh)**
     12 
     13 ```
     14 for i in range(int(input())):
     15     n, k = map(int, input().split())
     16     print('YES' if k * k <= n and n % 2 == k % 2 else 'NO')
     17 ```
     18 
     19 [1327B - Princesses and Princes](/contest/1327/problem/B "Educational Codeforces Round 84 (Rated for Div. 2)")
     20 
     21 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     22 
     23 **Tutorial**
     24 
     25 Tutorial is loading...
     26 
     27 **Solution (pikmike)**
     28 
     29 ```
     30 from sys import stdin, stdout
     31 
     32 t = int(stdin.readline())
     33 for _ in range(t):
     34     n = int(stdin.readline())
     35     used = [False for i in range(n)]
     36     v = -1
     37     for i in range(n):
     38         l = [int(x) - 1 for x in stdin.readline().split()][1:]
     39         for j in l:
     40             if not used[j]:
     41                 used[j] = True
     42                 break
     43         else:
     44             v = i
     45     if v == -1:
     46         stdout.write("OPTIMAL\n")
     47     else:
     48         u = used.index(False)
     49         stdout.write("IMPROVE\n" + str(v + 1) + " " + str(u + 1) + "\n")
     50 ```
     51 
     52 [1327C - Game with Chips](/contest/1327/problem/C "Educational Codeforces Round 84 (Rated for Div. 2)")
     53 
     54 Idea: [Neon](/profile/Neon "Candidate Master Neon")
     55 
     56 **Tutorial**
     57 
     58 Tutorial is loading...
     59 
     60 **Solution (Ne0n25)**
     61 
     62 ```
     63 n, m, _ = map(int, input().split())
     64 
     65 print(2 * (n - 1) + (n + 1) * (m - 1))
     66 print("U" * (n - 1) + "L" * (m - 1), end="")
     67 for i in range(n):
     68     if i != 0:
     69         print("D", end="")
     70     if i % 2 == 0:
     71         print("R" * (m - 1), end="")
     72     else:
     73         print("L" * (m - 1), end="")
     74 ```
     75 
     76 [1327D - Infinite Path](/contest/1327/problem/D "Educational Codeforces Round 84 (Rated for Div. 2)")
     77 
     78 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     79 
     80 **Tutorial**
     81 
     82 Tutorial is loading...
     83 
     84 **Solution (adedalic)**
     85 
     86 ```
     87 #include<bits/stdc++.h>
     88 
     89 using namespace std;
     90 
     91 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
     92 #define sz(a) int((a).size())
     93 
     94 #define x first
     95 #define y second
     96 
     97 typedef long long li;
     98 typedef pair<int, int> pt;
     99 
    100 const int INF = int(1e9);
    101 const li INF64 = li(1e18);
    102 
    103 int n;
    104 vector<int> p, c;
    105 
    106 inline bool read() {
    107     if(!(cin >> n))
    108         return false;
    109     p.resize(n);
    110     c.resize(n);
    111     
    112     fore(i, 0, n) {
    113         cin >> p[i];
    114         p[i]--;
    115     }
    116     fore(i, 0, n)
    117         cin >> c[i];
    118     return true;
    119 }
    120 
    121 inline void solve() {
    122     vector<int> used(n, 0);
    123     
    124     int ans = INF;
    125     fore(st, 0, n) {
    126         if(used[st])
    127             continue;
    128         
    129         vector<int> cycle;
    130         int v = st;
    131         while(!used[v]) {
    132             used[v] = 1;
    133             cycle.push_back(v);
    134             v = p[v];
    135         }
    136         
    137         fore(step, 1, sz(cycle) + 1) {
    138             if(sz(cycle) % step != 0)
    139                 continue;
    140             
    141             fore(s, 0, step) {
    142                 bool eq = true;
    143                 for(int pos = s; pos + step < sz(cycle); pos += step) {
    144                     if(c[cycle[pos]] != c[cycle[pos + step]])
    145                         eq = false;
    146                 }
    147                 if(eq) {
    148                     ans = min(ans, step);
    149                     break;
    150                 }
    151             }
    152         }
    153     }
    154     cout << ans << endl;
    155 }
    156 
    157 int main() {
    158 #ifdef _DEBUG
    159     freopen("input.txt", "r", stdin);
    160     int tt = clock();
    161 #endif
    162     ios_base::sync_with_stdio(false);
    163     cin.tie(0), cout.tie(0);
    164     cout << fixed << setprecision(15);
    165     
    166     int tc; cin >> tc;
    167     
    168     while(tc--) {
    169         read();
    170         solve();
    171         
    172 #ifdef _DEBUG
    173         cerr << "TIME = " << clock() - tt << endl;
    174         tt = clock();
    175 #endif
    176     }
    177     return 0;
    178 }
    179 ```
    180 
    181 [1327E - Count The Blocks](/contest/1327/problem/E "Educational Codeforces Round 84 (Rated for Div. 2)")
    182 
    183 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    184 
    185 **Tutorial**
    186 
    187 Tutorial is loading...
    188 
    189 **Solution (Roms)**
    190 
    191 ```
    192 MOD = 998244353
    193 p = [1] * 200005
    194 for i in range(1, 200005):
    195     p[i] = (p[i - 1] * 10) % MOD
    196 
    197 n = int(input())
    198 for i in range(1, n):
    199     res = 2 * 10 * 9 * p[n - i - 1]
    200     res += (n - 1 - i) * 10 * 9 * 9 * p[n - i - 2]
    201     print(res % MOD, end = ' ')
    202 print(10)
    203 ```
    204 
    205 [1327F - AND Segments](/contest/1327/problem/F "Educational Codeforces Round 84 (Rated for Div. 2)")
    206 
    207 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    208 
    209 **Tutorial**
    210 
    211 Tutorial is loading...
    212 
    213 **Solution (Ne0n25)**
    214 
    215 ```
    216 #include <bits/stdc++.h>
    217 
    218 using namespace std;
    219 
    220 #define x first
    221 #define y second
    222 #define sz(a) int((a).size())
    223 #define all(a) (a).begin(), (a).end()
    224 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    225 
    226 typedef pair<int, int> pt;
    227 
    228 const int MOD = 998244353;
    229 const int N = 500 * 1000 + 13;
    230 
    231 int n, k, m;
    232 pair<pt, int> q[N];
    233 
    234 int ones[N];
    235 int mx[N], sum[N];
    236 
    237 int add(int x, int y) {
    238     x += y;
    239     if (x >= MOD) x -= MOD;
    240     if (x < 0) x += MOD;
    241     return x;
    242 }
    243 
    244 int calc(int t) {
    245     memset(ones, 0, sizeof(ones));
    246     memset(mx, -1, sizeof(mx));
    247     
    248     forn(i, m) {
    249         int l = q[i].x.x, r = q[i].x.y;
    250         if (q[i].y & (1 << t)) {
    251             ones[l]++;
    252             ones[r + 1]--;
    253         } else {
    254             mx[r] = max(mx[r], l);
    255         }
    256     }
    257     
    258     int j = -1;
    259     forn(i, n) {
    260         int cur = 0;
    261         if (!ones[i]) {
    262             cur = sum[i];
    263             if (j == -1) cur = add(cur, 1);
    264             else cur = add(cur, -sum[j]);
    265         }
    266         
    267         sum[i + 1] = add(sum[i], cur);
    268         ones[i + 1] += ones[i];
    269         j = max(j, mx[i]);
    270     }
    271     
    272     return add(sum[n], j != -1 ? -sum[j] : 1);
    273 }
    274 
    275 int main() {
    276     scanf("%d%d%d", &n, &k, &m);
    277     forn(i, m) {
    278         scanf("%d%d%d", &q[i].x.x, &q[i].x.y, &q[i].y);
    279         --q[i].x.x; --q[i].x.y;
    280     }
    281     
    282     int ans = 1;
    283     forn(i, k) ans = (ans * 1ll * calc(i)) % MOD;
    284     printf("%d\n", ans);
    285 }
    286 ```
    287 
    288 [1327G - Letters and Question Marks](/contest/1327/problem/G "Educational Codeforces Round 84 (Rated for Div. 2)")
    289 
    290 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    291 
    292 **Tutorial**
    293 
    294 Tutorial is loading...
    295 
    296 **Solution (BledDest)**
    297 
    298 ```
    299 #include<bits/stdc++.h>
    300 
    301 using namespace std;
    302 
    303 const int N = 8000043;
    304 const int K = 15;
    305 const int M = 1043;
    306 
    307 int k;
    308 char buf[N], buf2[M];
    309 vector<string> t;
    310 vector<int> c;
    311 string s;
    312 
    313 map<char, int> nxt[M];
    314 int lnk[M];
    315 int p[M];
    316 char pchar[M];
    317 map<char, int> go[M];
    318 int term[M];
    319 int ts = 1;
    320 int A[M][K];
    321 int F[M][K];
    322 int dp[M];
    323 
    324 int get_nxt(int x, char c)
    325 {
    326     if(!nxt[x].count(c))
    327     {
    328         p[ts] = x;
    329         pchar[ts] = c;
    330         nxt[x][c] = ts++;
    331     }
    332     return nxt[x][c];
    333 }
    334 
    335 void add_string(int i)
    336 {
    337     int cur = 0;
    338     for(auto x : t[i])
    339     {
    340         cur = get_nxt(cur, x);
    341     }
    342     term[cur] += c[i];
    343 }
    344 
    345 int get_go(int x, char c);
    346 
    347 int get_lnk(int x)
    348 {
    349     if(lnk[x] != -1)
    350         return lnk[x];
    351     if(x == 0 || p[x] == 0)
    352         return lnk[x] = 0;
    353     return lnk[x] = get_go(get_lnk(p[x]), pchar[x]);
    354 }
    355 
    356 int get_dp(int x)
    357 {
    358     if(dp[x] != -1)
    359         return dp[x];
    360     dp[x] = term[x];
    361     if(get_lnk(x) != x)
    362         dp[x] += get_dp(get_lnk(x));
    363     return dp[x];
    364 }
    365 
    366 int get_go(int x, char c)
    367 {
    368     if(go[x].count(c))
    369         return go[x][c];
    370     if(nxt[x].count(c))
    371         return go[x][c] = nxt[x][c];
    372     if(x == 0)
    373         return go[x][c] = 0;
    374     return go[x][c] = get_go(get_lnk(x), c);
    375 }
    376 
    377 void build_skip(const string& s, vector<int>& sA, vector<long long>& sF)
    378 {                     
    379     sA = vector<int>(ts);
    380     for(int i = 0; i < ts; i++)
    381         sA[i] = i;
    382     sF = vector<long long>(ts);
    383     for(auto c : s)
    384     {
    385         int ci = int(c - 'a');
    386         for(int i = 0; i < ts; i++)
    387         {
    388             sF[i] += F[sA[i]][ci];
    389             sA[i] = A[sA[i]][ci];
    390         }
    391     }
    392 }
    393 
    394 long long solve(const string& s)
    395 {
    396     long long BAD = (long long)(-1e18);
    397 
    398     vector<int> pos;
    399     for(int i = 0; i < s.size(); i++)
    400         if(s[i] == '?')
    401             pos.push_back(i);
    402     int cntQ = pos.size();
    403     vector<vector<int> > skip_A(cntQ + 1);
    404     vector<vector<long long> > skip_F(cntQ + 1);
    405     build_skip(s.substr(0, pos[0]), skip_A[0], skip_F[0]);
    406     for(int i = 1; i < cntQ; i++)
    407         build_skip(s.substr(pos[i - 1] + 1, pos[i] - pos[i - 1] - 1), skip_A[i], skip_F[i]);
    408     build_skip(s.substr(pos.back() + 1, s.size() - pos.back() - 1), skip_A[cntQ], skip_F[cntQ]);
    409 
    410     vector<vector<long long> > dp(1 << (K - 1), vector<long long>(ts, BAD));
    411     vector<int> used(1 << K);
    412     dp[0][skip_A[0][0]] = skip_F[0][0];
    413     queue<int> q;
    414     q.push(0);
    415     used[0] = 1;
    416     long long ans = BAD;
    417     while(!q.empty())
    418     {
    419         int k = q.front();
    420         q.pop();
    421         int step = __builtin_popcount(k);
    422         if(step == cntQ)
    423         {
    424             for(int i = 0; i < ts; i++)
    425                 ans = max(ans, dp[k][i]);
    426             continue;
    427         }
    428         for(int i = 0; i < K - 1; i++)
    429         {
    430             if(k & (1 << i)) continue;
    431             int nk = (k ^ (1 << i));
    432             if(used[nk] == 0)
    433             {
    434                 used[nk] = 1;
    435                 q.push(nk);
    436             }
    437             for(int j = 0; j < ts; j++)
    438             {
    439                 if(dp[k][j] == BAD)
    440                     continue;
    441                 int nj = get_go(j, char('a' + i));
    442                 int newSt = skip_A[step + 1][nj];
    443                 long long add = get_dp(nj) + skip_F[step + 1][nj];
    444                 dp[nk][newSt] = max(dp[nk][newSt], dp[k][j] + add);
    445             }
    446         }
    447     }
    448     return ans;
    449 }
    450 
    451 int main()
    452 {
    453     scanf("%d", &k);
    454     t.resize(k);
    455     c.resize(k);
    456     for(int i = 0; i < k; i++)
    457     {
    458         scanf("%s %d", buf2, &c[i]);
    459         t[i] = buf2;
    460     }    
    461     scanf("%s", buf);
    462     s = buf;
    463 
    464     for(int i = 0; i < k; i++)
    465         add_string(i);
    466     for(int i = 0; i < ts; i++)
    467     {
    468         lnk[i] = -1;
    469         dp[i] = -1;
    470     }
    471     for(int i = 0; i < ts; i++)
    472     {
    473         get_lnk(i);
    474         for(char c = 'a'; c <= 'o'; c++)
    475             get_go(i, c);
    476     }
    477     for(int i = 0; i < ts; i++)
    478         get_dp(i);                               
    479     for(int i = 0; i < ts; i++)
    480     {
    481         for(int j = 0; j < K; j++)
    482         {
    483             A[i][j] = get_go(i, char('a' + j));
    484             F[i][j] = dp[A[i][j]];
    485         }
    486     }   
    487     int n = s.size();
    488     vector<int> leftQ(n, -1);
    489     vector<int> rightQ(n, -1);
    490     for(int i = 0; i < n; i++)
    491     {
    492         if(i != 0)
    493             leftQ[i] = leftQ[i - 1];
    494         if(s[i] == '?')
    495             leftQ[i] = i;
    496     }
    497     for(int i = n - 1; i >= 0; i--)
    498     {
    499         if(i != n - 1)
    500             rightQ[i] = rightQ[i + 1];
    501         if(s[i] == '?')
    502             rightQ[i] = i;
    503     }
    504     vector<int> bad(n, 0);
    505     
    506     if(leftQ.back() == -1)
    507         bad = vector<int>(n, 1);
    508 
    509     long long ans = 0;
    510     int curSt = 0;
    511     string news = "";
    512     for(int i = 0; i < n; i++)
    513     {
    514         int ci = (s[i] == '?' ? 14 : int(s[i] - 'a'));
    515         if(bad[i])
    516             ans += F[curSt][ci];
    517         curSt = A[curSt][ci];
    518         if(!bad[i])
    519             news.push_back(s[i]);
    520         else if(i != 0 && !bad[i - 1])
    521             news.push_back('o');
    522     }                    
    523     if(!news.empty())
    524         ans += solve(news);
    525     printf("%lld\n", ans);
    526 }
    527 ```