codeforces-scrape

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

1163.md (12098B)


      1 Source: https://codeforces.com/blog/entry/66943
      2 
      3 Hello everyone, this is the editorial for [Codeforces Round 558 (Div. 2)](/contest/1163 "Codeforces Round 558 (Div. 2)"). I hope you enjoy the problem as well as I did!
      4 
      5 [1163A - Eating Soup](/contest/1163/problem/A "Codeforces Round 558 (Div. 2)")
      6 
      7 Author: [xuandadenbenem](/profile/xuandadenbenem "Expert xuandadenbenem")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Implementation**
     14 
     15 ```
     16 #include <iostream>
     17 
     18 using namespace std;
     19 
     20 int main ()
     21 {
     22     int n, m;
     23 	cin >> n >> m;
     24 	cout << (m ? min(m, n - m) : 1) << endl;
     25 	return 0;
     26 }
     27 ```
     28 
     29 [1163B2 - Cat Party (Hard Edition)](/contest/1163/problem/B2 "Codeforces Round 558 (Div. 2)")
     30 
     31 Author: [Shirone](/profile/Shirone "Specialist Shirone")
     32 
     33 **Tutorial**
     34 
     35 Tutorial is loading...
     36 
     37 **Implementation**
     38 
     39 ```
     40 #include <iostream>
     41 #include <stdio.h>
     42 using namespace std;
     43 
     44 const int N = 1e5 + 10;
     45 
     46 int n, color, ans, mx, f[N], cnt[N];
     47 
     48 int main()
     49 {
     50 	scanf("%d", &n);
     51 	for (int i = 1; i <= n; i++)
     52     {
     53         scanf("%d", &color);
     54         cnt[f[color]]--;
     55         f[color]++;
     56         cnt[f[color]]++;
     57         mx = max(mx, f[color]);
     58         bool ok = false;
     59         if (cnt[1] == i) // every color has occurence of 1
     60             ok = true;
     61         else if (cnt[i] == 1) // only one color has the maximum occurence and the occurence is i
     62             ok = true;
     63         else if (cnt[1] == 1 && cnt[mx] * mx == i - 1) // one color has occurence of 1 and other colors have the same occurence
     64             ok = true;
     65         else if (cnt[mx - 1] * (mx - 1) == i - mx && cnt[mx] == 1) // one color has the occurence 1 more than any other color
     66             ok = true;
     67         if (ok)
     68             ans = i;
     69     }
     70     printf("%d", ans);
     71 	return 0;
     72 }
     73 ```
     74 
     75 [1163C2 - Power Transmission (Hard Edition)](/contest/1163/problem/C2 "Codeforces Round 558 (Div. 2)")
     76 
     77 Author: [GreymaneSilverfang](/profile/GreymaneSilverfang "Candidate Master GreymaneSilverfang")
     78 
     79 **Tutorial**
     80 
     81 Tutorial is loading...
     82 
     83 **Implementation**
     84 
     85 ```
     86 #include <cstdio>
     87 #include <map>
     88 #include <set>
     89 #include <utility>
     90 const int N = 1001;
     91 int x[N], y[N];
     92 std::map<std::pair<int,int>,std::set<long long>> slope_map;
     93 
     94 int gcd(int a, int b) 
     95 {
     96 	if (a == 0)
     97 		return b;
     98 	return gcd(b % a, a);
     99 }
    100 
    101 int main()
    102 {
    103 	int n; scanf("%d", &n);
    104 	for (int i = 1; i <= n; ++i)
    105 		scanf("%d%d", &x[i], &y[i]);
    106 	long long total = 0, res = 0;
    107 	for (int i = 1; i <= n - 1; ++i)
    108 		for (int j = i + 1; j <= n; ++j)
    109 		{
    110 			int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j];
    111 			// construct a line passing through (x1, y1) and (x2, y2)
    112 			// line is expressed as equation ax - by = c with constant a, b, c 
    113 			int a = y1 - y2, b = x1 - x2;
    114 			// simplify equation
    115 			int d = gcd(a, b); a /= d, b /= d;
    116 			if (a < 0 || (a == 0 && b < 0))
    117 			{
    118 			    a = -a;
    119 			    b = -b;
    120 			}
    121 			// lines with the same slope (same a, b) are stored in a map
    122 			std::pair<int,int> slope(a, b);
    123 			long long c = 1LL * a * x1 - 1LL * b * y1;
    124 			if (!slope_map[slope].count(c))
    125 			{
    126 				++total;
    127 				slope_map[slope].insert(c);
    128 				// if this line is new, it intersects every line with different slope
    129 				res += total - slope_map[slope].size();
    130 			}
    131 		}
    132 	printf("%lld\n", res);
    133 }
    134 ```
    135 
    136 [1163D - Mysterious Code](/contest/1163/problem/D "Codeforces Round 558 (Div. 2)")
    137 
    138 Author: [Kuroni](/profile/Kuroni "International Master Kuroni")
    139 
    140 **Tutorial**
    141 
    142 Tutorial is loading...
    143 
    144 **Implementation**
    145 
    146 ```
    147 #include <iostream>
    148 #include <cstdio>
    149 #include <cstring>
    150 using namespace std;
    151 
    152 const int K = 1005, N = 55, M = 55, INF = 1E9 + 7;
    153 
    154 int k, n, m;
    155 int kmp_s[N], nxt_s[N][26], kmp_t[M], nxt_t[M][26];
    156 int dp[K][N][M];
    157 char code[K], s[N], t[M];
    158 
    159 void init(char s[], int n, int kmp[], int nxt[][26])
    160 {
    161     kmp[1] = 0;
    162     for (int i = 2; i <= n; i++)
    163     {
    164         int cur = kmp[i - 1];
    165         while (cur > 0 && s[cur + 1] != s[i])
    166             cur = kmp[cur];
    167         if (s[cur + 1] == s[i])
    168             ++cur;
    169         kmp[i] = cur;
    170     }
    171 
    172     for (int i = 0; i <= n; i++)
    173         for (char c = 'a'; c <= 'z'; c++)
    174         {
    175             int cur = i;
    176             while (cur > 0 && s[cur + 1] != c)
    177                 cur = kmp[cur];
    178             if (s[cur + 1] == c)
    179                 ++cur;
    180             nxt[i][c - 'a'] = cur;
    181         }
    182 }
    183 
    184 int main()
    185 {
    186     scanf("%s%s%s", code + 1, s + 1, t + 1);
    187     k = strlen(code + 1); n = strlen(s + 1); m = strlen(t + 1);
    188     init(s, n, kmp_s, nxt_s); init(t, m, kmp_t, nxt_t);
    189     for (int i = 0; i <= k; i++)
    190         for (int ks = 0; ks <= n; ks++)
    191             for (int kt = 0; kt <= m; kt++)
    192                 dp[i][ks][kt] = -INF;
    193     dp[0][0][0] = 0;
    194     for (int i = 0; i < k; i++)
    195         for (int ks = 0; ks <= n; ks++)
    196             for (int kt = 0; kt <= m; kt++)
    197                 for (char c = 'a'; c <= 'z'; c++)
    198                     if (code[i + 1] == '*' || code[i + 1] == c) // we now add/replace the (i + 1)-th character
    199                     {
    200                         int ns = nxt_s[ks][c - 'a'], nt = nxt_t[kt][c - 'a'];
    201                         int tmp = dp[i][ks][kt] + (ns == n) - (nt == m); // add the new occurrences if any
    202                         dp[i + 1][ns][nt] = max(dp[i + 1][ns][nt], tmp);
    203                     }
    204     int ma = -INF;
    205     for (int ks = 0; ks <= n; ks++)
    206         for (int kt = 0; kt <= m; kt++)
    207             ma = max(ma, dp[k][ks][kt]);
    208     printf("%d\n", ma);
    209 }
    210 ```
    211 
    212 [1163E - Magical Permutation](/contest/1163/problem/E "Codeforces Round 558 (Div. 2)")
    213 
    214 Author: [Kuroni](/profile/Kuroni "International Master Kuroni")
    215 
    216 **Tutorial**
    217 
    218 Tutorial is loading...
    219 
    220 **Implementation**
    221 
    222 ```
    223 #include <iostream>
    224 #include <cstdio>
    225 #include <vector>
    226 #include <algorithm>
    227 using namespace std;
    228 
    229 const int N = 200005;
    230 
    231 int n, a[N];
    232 vector<int> basis, vec;
    233 
    234 void add(int u)
    235 {
    236     int tmp = u;
    237     // we keep the basis sorted in decreasing order
    238     for (int &v : basis)
    239         u = min(u, u ^ v);
    240     if (u > 0) // u is a new element in the basis
    241     {
    242         basis.push_back(u);
    243         vec.push_back(tmp);
    244         // now we move u up until the basis is decreasingly sorted again
    245         for (int i = basis.size() - 1; i > 0; i--)
    246             if (basis[i] > basis[i - 1])
    247                 swap(basis[i], basis[i - 1]);
    248             else
    249                 break;
    250     }
    251 }
    252 
    253 void gray_code(int size)
    254 {
    255     vector<int> ans = {0};
    256     for (int i = 0; i < size; i++)
    257         for (int j = (1 << i) - 1; j >= 0; j--)
    258             ans.push_back(ans[j] ^ vec[i]);
    259     for (int &v : ans)
    260         printf("%d ", v);
    261 }
    262 
    263 int main()
    264 {
    265     scanf("%d", &n);
    266     for (int i = 0; i < n; i++)
    267         scanf("%d", a + i);
    268     sort(a, a + n);
    269     int pt = 0, x = 0;
    270     for (int i = 1; i < 20; i++)
    271     {
    272         for (; pt < n && a[pt] < (1 << i); pt++)
    273             add(a[pt]);
    274         if (basis.size() == i)
    275             x = i;
    276     }
    277     basis.clear();
    278     vec.clear();
    279     for (int i = 0; i < n && a[i] < (1 << x); i++)
    280         add(a[i]);
    281     printf("%d\n", x);
    282     gray_code(x);
    283 }
    284 ```
    285 
    286 **Implementation with DFS**
    287 
    288 ```
    289 #include <iostream>
    290 #include <cstdio>
    291 #include <vector>
    292 #include <algorithm>
    293 using namespace std;
    294 
    295 const int N = 200005, MX = 1E6 + 5;
    296 
    297 int n, x = 0, a[N];
    298 bool vis[MX];
    299 vector<int> basis, vec, ans;
    300 
    301 void add(int u)
    302 {
    303     int tmp = u;
    304     for (int &v : basis)
    305         u = min(u, u ^ v);
    306     if (u > 0)
    307     {
    308         basis.push_back(u);
    309         vec.push_back(tmp);
    310         for (int i = basis.size() - 1; i > 0; i--)
    311             if (basis[i] > basis[i - 1])
    312                 swap(basis[i], basis[i - 1]);
    313             else
    314                 break;
    315     }
    316 }
    317 
    318 void DFS(int u, int it = 0)
    319 {
    320     ans.push_back(u);
    321     vis[u] = true;
    322     if (it == (1 << x) - 1)
    323         return;
    324     for (int &v : vec)
    325         if (!vis[u ^ v])
    326         {
    327             DFS(u ^ v, it + 1);
    328             return;
    329         }
    330 }
    331 
    332 int main()
    333 {
    334     scanf("%d", &n);
    335     for (int i = 0; i < n; i++)
    336         scanf("%d", a + i);
    337     sort(a, a + n);
    338     int pt = 0;
    339     for (int i = 1; i < 20; i++)
    340     {
    341         for (; pt < n && a[pt] < (1 << i); pt++)
    342             add(a[pt]);
    343         if (basis.size() == i)
    344             x = i;
    345     }
    346     basis.clear();
    347     vec.clear();
    348     for (int i = 0; i < n && a[i] < (1 << x); i++)
    349         add(a[i]);
    350     printf("%d\n", x);
    351     DFS(0);
    352     for (int &v : ans)
    353         printf("%d ", v);
    354 }
    355 ```
    356 
    357 [1163F - Indecisive Taxi Fee](/contest/1163/problem/F "Codeforces Round 558 (Div. 2)")
    358 
    359 Author: [Kuroni](/profile/Kuroni "International Master Kuroni")
    360 
    361 **Tutorial**
    362 
    363 Tutorial is loading...
    364 
    365 **Implementation**
    366 
    367 ```
    368 #include <iostream>
    369 #include <cstdio>
    370 #include <vector>
    371 #include <queue>
    372 using namespace std;
    373 
    374 const int N = 2E5 + 5, M = 2E5 + 5;
    375 const long long INF = 1E18 + 7;
    376 
    377 int n, m, q, ed, nw, mx, u[M], v[M], w[M], ind[M];
    378 int tr[N], le[N], ri[N];
    379 bool on_path[N];
    380 long long dis[2][N];
    381 
    382 struct TNode
    383 {
    384     int u;
    385     long long val;
    386 
    387     TNode(int _u, long long _val)
    388     {
    389         u = _u;
    390         val = _val;
    391     }
    392 
    393     inline bool operator>(const TNode &oth) const
    394     {
    395         return val > oth.val;
    396     }
    397 };
    398 priority_queue<TNode, vector<TNode>, greater<TNode>> pq;
    399 
    400 struct TEdge
    401 {
    402     int v, w, ind;
    403 
    404     TEdge(int _v, int _w, int _ind)
    405     {
    406         v = _v;
    407         w = _w;
    408         ind = _ind;
    409     }
    410 };
    411 vector<TEdge> adj[N];
    412 
    413 struct TTree
    414 {
    415 #define m (l + r) / 2
    416 #define lc i * 2
    417 #define rc i * 2 + 1
    418 
    419     long long tr[4 * M];
    420 
    421     void build(int l, int r, int i)
    422     {
    423         tr[i] = INF;
    424         if (l == r)
    425             return;
    426         build(l, m, lc);
    427         build(m + 1, r, rc);
    428     }
    429 
    430     void upd(int l, int r, int i, int L, int R, long long v)
    431     {
    432         if (l > R || r < L || L > R)
    433             return;
    434         if (L <= l && r <= R)
    435         {
    436             tr[i] = min(tr[i], v);
    437             return;
    438         }
    439         upd(l, m, lc, L, R, v);
    440         upd(m + 1, r, rc, L, R, v);
    441     }
    442 
    443     long long que(int l, int r, int i, int u)
    444     {
    445         if (l == r)
    446             return tr[i];
    447         return min(tr[i], u <= m ? que(l, m, lc, u) : que(m + 1, r, rc, u));
    448     }
    449 
    450 #undef m
    451 #undef lc
    452 #undef rc
    453 } seg;
    454 
    455 void dijkstra(int st, long long dis[], int get = 0)
    456 {
    457     fill(dis + 1, dis + n + 1, INF);
    458     pq.push(TNode(st, dis[st] = 0));
    459     while (!pq.empty())
    460     {
    461         TNode u = pq.top(); pq.pop();
    462         if (u.val > dis[u.u])
    463             continue;
    464         for (TEdge &v : adj[u.u])
    465             if (dis[v.v] > u.val + v.w)
    466             {
    467                 tr[v.v] = v.ind;
    468                 if (get == 1 && !on_path[v.v])
    469                     le[v.v] = le[u.u];
    470                 else if (get == 2 && !on_path[v.v])
    471                     ri[v.v] = ri[u.u];
    472                 pq.push(TNode(v.v, dis[v.v] = u.val + v.w));
    473             }
    474     }
    475 }
    476 
    477 void trace()
    478 {
    479     on_path[1] = true; le[1] = ri[1] = 0;
    480     for (int i = 1, cur = 1; cur != n; i++)
    481     {
    482         int edge = tr[cur];
    483         ind[edge] = mx = i;
    484         cur = u[edge] ^ v[edge] ^ cur;
    485         on_path[cur] = true;
    486         le[cur] = ri[cur] = i;
    487     }
    488 }
    489 
    490 int main()
    491 {
    492     scanf("%d%d%d", &n, &m, &q);
    493     for (int i = 1; i <= m; i++)
    494     {
    495         scanf("%d%d%d", u + i, v + i, w + i);
    496         ind[i] = -1;
    497         adj[u[i]].push_back(TEdge(v[i], w[i], i));
    498         adj[v[i]].push_back(TEdge(u[i], w[i], i));
    499     }
    500     dijkstra(n, dis[1]); // reverse the initial dijkstra for the trace to increase from 1 -> n
    501     trace();
    502     dijkstra(1, dis[0], 1);
    503     dijkstra(n, dis[1], 2);
    504     seg.build(1, mx, 1);
    505     for (int i = 1; i <= m; i++)
    506         if (ind[i] == -1)
    507         {
    508             seg.upd(1, mx, 1, le[u[i]] + 1, ri[v[i]], dis[0][u[i]] + w[i] + dis[1][v[i]]);
    509             seg.upd(1, mx, 1, le[v[i]] + 1, ri[u[i]], dis[0][v[i]] + w[i] + dis[1][u[i]]);
    510         }
    511     while (q--)
    512     {
    513         scanf("%d%d", &ed, &nw);
    514         long long ans;
    515         if (ind[ed] > 0)
    516         {
    517             ans = dis[0][n] - w[ed] + nw;
    518             if (nw > w[ed])
    519                 ans = min(ans, seg.que(1, mx, 1, ind[ed]));
    520         }
    521         else
    522         {
    523             ans = dis[0][n];
    524             if (nw < w[ed])
    525             {
    526                 ans = min(ans, dis[0][u[ed]] + nw + dis[1][v[ed]]);
    527                 ans = min(ans, dis[0][v[ed]] + nw + dis[1][u[ed]]);
    528             }
    529         }
    530         printf("%lld\n", ans);
    531     }
    532 }
    533 ```