-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
691 lines (441 loc) · 148 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
<!DOCTYPE html>
<html>
<head>
<!-- hexo-inject:begin --><!-- hexo-inject:end --><meta charset="utf-8">
<title>Cao Li's blog</title>
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="Some study by interest, mainly on competitive programming, algorithm and developing.">
<meta name="keywords" content="Competitive programming, Algorithm, Software developing">
<meta property="og:type" content="website">
<meta property="og:title" content="Cao Li's blog">
<meta property="og:url" content="http://yoursite.com/index.html">
<meta property="og:site_name" content="Cao Li's blog">
<meta property="og:description" content="Some study by interest, mainly on competitive programming, algorithm and developing.">
<meta property="og:locale" content="default">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Cao Li's blog">
<meta name="twitter:description" content="Some study by interest, mainly on competitive programming, algorithm and developing.">
<link rel="alternate" href="/atom.xml" title="Cao Li's blog" type="application/atom+xml">
<link rel="icon" href="/favicon.png">
<link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
<link rel="stylesheet" href="/css/style.css"><!-- hexo-inject:begin --><!-- hexo-inject:end -->
</head>
<body>
<!-- hexo-inject:begin --><!-- hexo-inject:end --><div id="container">
<div id="wrap">
<header id="header">
<div id="banner"></div>
<div id="header-outer" class="outer">
<div id="header-title" class="inner">
<h1 id="logo-wrap">
<a href="/" id="logo">Cao Li's blog</a>
</h1>
</div>
<div id="header-inner" class="inner">
<nav id="main-nav">
<a id="main-nav-toggle" class="nav-icon"></a>
<a class="main-nav-link" href="/">Home</a>
<a class="main-nav-link" href="/archives">Archives</a>
</nav>
<nav id="sub-nav">
<a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
<a id="nav-search-btn" class="nav-icon" title="Search"></a>
</nav>
<div id="search-form-wrap">
<form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit"></button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
</div>
</div>
</div>
</header>
<div class="outer">
<section id="main">
<article id="post-something-about-bipartite-graph" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2018/11/04/something-about-bipartite-graph/" class="article-date">
<time datetime="2018-11-03T23:53:32.000Z" itemprop="datePublished">2018-11-04</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/competitive-programming/">competitive programming</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/11/04/something-about-bipartite-graph/">Something About Bipartite Graph</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>In this article, I will mention some concepts in graph theory. They usually appear in problems related to <strong>bipartite graph</strong>. To solve such problems, we need to know these things and some conclusions. </p>
<p>Let’s denote the graph $ G = (V, E) $, where $V$ is the set of vertices and $E$ is the set of edges in graph $G$. </p>
<ol>
<li>Match: A set of edges $ M \subseteq E $, where any two edges in $M$ do not have common endpoints. </li>
<li>Edge Cover: A set of edges $ F \subseteq E $, where any vertex in $V$ is an endpoint of some edge in $F$. </li>
<li>Independent Set: A set of vertices $ S \subseteq V $, where any vertices in $S$ are not connected with each other. </li>
<li>Vertex Cover: A set of vertices $ S \subseteq V $, where each edge in $E$ has at least one endpoint in $S$ .</li>
</ol>
<p>Now let’s see some important conclusions which help us solve problems about bipartite graph.<br><strong>Conclusion (1)</strong><br>$ | Maximum \ Match | + |Minimum \ Edge \ Cover | = |V| $.<br>Suppose there are $X$ edges in the Maximum Match, $2X$ vertices are covered by these edges. And Suppose there are $Y$ vertices remain uncovered by any edge. To get the Minimum Edge Cover, we can pick the $X$ edges in the Maximum Match and take extra $Y$ edges which connect all the remain vertices. So $ |Minimum \ Edge \ Cover| = X + Y $, as we defined, $ 2X + Y = |V| $.<br><strong>Conclusion (2)</strong><br>$ | Maximum \ Independent \ Set | + | Minimum \ Vertex \ Cover | = |V| $.<br>Let’s denote $V_{1}$ as the Maximum Independent Set. $V_{2} = V - V_{1}$. Since there are no edges between any two vertices in $V_{1}$ and such set is maximized, $V_{2}$ covers all the edges and $V_{2}$ is minimized. This means $V_{2}$ is the Minimum Vertex Cover.<br><strong>Conclusion(3)</strong><br>In a bipartite graph, $ |Maximum \ Match| = |Minimum \ Vertex \ Cover| $. </p>
<p>Actually, to get a <strong>Minimum Vertex Cover</strong> or a <strong>Maximum Independent Set</strong> is a <strong>NP-Hard</strong> problem. But in a bipartite graph, we get can them by using the above conclusions in linear time complexity.</p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2018/11/04/something-about-bipartite-graph/" data-id="cjo242g9j000tg8tsa4z00ujq" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/bipartite-graph/">bipartite graph</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/graph-theory/">graph theory</a></li></ul>
</footer>
</div>
</article>
<article id="post-fractional-programming-and-dinkelbach-theorem" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2018/10/14/fractional-programming-and-dinkelbach-theorem/" class="article-date">
<time datetime="2018-10-14T02:21:56.000Z" itemprop="datePublished">2018-10-14</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/10/14/fractional-programming-and-dinkelbach-theorem/">Fractional programming & Dinkelbach theorem</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>Let’s first consider such a problem: Given n objects, the i-th of them has value $v_i$ and has weight $w_i$. Now we want to pick some of them, say, the set of objects we pick is $S$. And we want to make $ f(S) = \frac{\sum_{i \in S} v_i}{\sum_{i \in S} w_i} $ maximized. How do we calculate that?<br>This is actually a fundamental example of <strong>fractional programming</strong>. Here is normal form of <strong>fractional programming</strong>:<br>$$ Minimize \ \ \lambda = f(x) = \frac{a(x)}{b(x)} \ (x \in S) $$<br>$x$ here is just an input among all the inputs in the whole space $S$, it can be anything, perhaps not only a simple variable. We can solve the problem by passing all $x$ from $S$ and get the result. But the size of $S$ could be usually very large or even infinite. So such solution is impractical. </p>
<p>Then we calls for the <strong>Dinkelbach</strong> theorem. Now let’s introduce a new function:<br>$$ g(\lambda) = \min_{x \in S}{ (a(x) - \lambda b(x)) } $$<br>Suppose $\lambda^{*}$ is the optimized value. The <strong>Dinkelbach algorithm</strong> says that:</p>
<ol>
<li>$ g(\lambda) = 0, \lambda = \lambda^{*} $</li>
<li>$ g(\lambda) < 0, \lambda > \lambda^{*} $</li>
<li>$ g(\lambda) > 0, \lambda < \lambda^{*} $ </li>
</ol>
<p>I won’t give detailed proof here, it’s actually easy to understand. $ g(\lambda) < 0 $ means that there exists some $x$ that satisfy $ a(x) - \lambda b(x) = 0$. So we can make $\lambda$ smaller. And $ g(\lambda) > 0 $ means that there is no such $x$, so this $\lambda$ is too small.<br>With this, we can get the answer by binary search. We can fix a $\lambda$ and calculate the value of $g(\lambda)$ and finally approach the answer. <strong>Dinkelbach</strong> also works when we want to get the maximized value instead of the minimized one. But this time the function changes in this way:<br>$$ g(\lambda) = \max_{ x \in S }{(a(x) - \lambda b(x))} $$</p>
<p>Let’s solve a sample problem of <strong>fractional programming</strong>: <a href="http://poj.org/problem?id=3111" target="_blank" rel="noopener">poj 3111 - K Best</a><br>My code:<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><algorithm></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><string.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><vector></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><math.h></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pb push_back</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> mp make_pair</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ull unsigned ll</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> db double</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INF 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MOD 1000000007</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> PII pair<span class="meta-string"><int, int></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">100010</span>;</span><br><span class="line"><span class="keyword">int</span> n,k;</span><br><span class="line"><span class="keyword">int</span> v[N],w[N];</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span> {</span></span><br><span class="line"> db val;</span><br><span class="line"> <span class="keyword">int</span> idx;</span><br><span class="line"> node(db a,<span class="keyword">int</span> b):val(a),idx(b){}</span><br><span class="line"> <span class="keyword">bool</span> <span class="keyword">operator</span><(<span class="keyword">const</span> node& rhs) <span class="keyword">const</span> {</span><br><span class="line"> <span class="keyword">return</span> val>rhs.val;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"><span class="built_in">vector</span><node> vec;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">check</span><span class="params">(db val)</span> </span>{</span><br><span class="line"> vec.clear();</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) {</span><br><span class="line"> vec.pb(node(v[i]-val*w[i],i));</span><br><span class="line"> }</span><br><span class="line"> sort(vec.begin(),vec.end());</span><br><span class="line"> db tot=<span class="number">0.0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<k;i++) tot+=vec[i].val;</span><br><span class="line"> <span class="keyword">return</span> tot><span class="number">0.0</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&n,&k);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,v+i,w+i);</span><br><span class="line"> }</span><br><span class="line"> db lo=<span class="number">0.0</span>,hi=<span class="number">1e11</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<<span class="number">50</span>;i++) {</span><br><span class="line"> db mid=(lo+hi)*<span class="number">0.5</span>;</span><br><span class="line"> <span class="keyword">if</span> (check(mid)) lo=mid;</span><br><span class="line"> <span class="keyword">else</span> hi=mid;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<k;i++) {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d "</span>,vec[i].idx);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"\n"</span>);</span><br><span class="line">}</span><br></pre></td></tr></table></figure><br>This is almost an direct application of <strong>Dinkelbach</strong>. When we fix $\lambda$, we can get $g(\lambda)$ by sorting all items of $ v_i - \lambda w_i $, and sum k biggest items up. And finally we got the answer. </p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2018/10/14/fractional-programming-and-dinkelbach-theorem/" data-id="cjo242g9g000qg8tswggvbl7i" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/binary-search/">binary search</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/dinkelbach-theorem/">dinkelbach theorem</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/fractional-programming/">fractional programming</a></li></ul>
</footer>
</div>
</article>
<article id="post-connectivity-and-tarjan-algorithm" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2018/09/27/connectivity-and-tarjan-algorithm/" class="article-date">
<time datetime="2018-09-27T14:51:21.000Z" itemprop="datePublished">2018-09-27</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/competitive-programming/">competitive programming</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/09/27/connectivity-and-tarjan-algorithm/">Connectivity & Tarjan Algorithm</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>Well, I think <strong>Tarjan</strong> algorithm is quite basic in graph theory. It’s only an simple application of <strong>dfs</strong>. Inspite of this, I usually refer to the internet or past code of it when I need to use it. So I try to figure out how it works in this blog and hope that I can learn it by heart.</p>
<p>As we all know, the <strong>Tarjan</strong> algorithm enables us to find all the <strong>articulation</strong> points in $O(|V| + |E|)$ time complexity. Actually it’s famous for find strongly connected components in DAG(directional acyclic graph). But here we only focus on using it to find articulation points in undirectional graph.</p>
<p>Articulation point, also called cut vertex, is any vertex whose removal increases the number of components.</p>
<p>Then we talk about how <strong>Tarjan</strong> algorithm works. It actually runs a depth-first-search and during the process it assigns two numbers to each vertex. Let’s call them <strong>dfn</strong> and <strong>low</strong>. <strong>dfn</strong> is the order in which the vertex is visited during the whole dfs process. And <strong>low</strong> is the smallest <strong>dfn</strong> of any vertex that can be visited by current vertex in the depth-first-search tree. So when we found two vertices where $low[v] \ge dfn[u]$, that means we have to visit <code>u</code> before reaching <code>v</code> in the dfs tree. As a result, <code>u</code> is a articulation point. But be careful that there is a special case: <code>u</code> is the root vertex in the dfs tree. Then for any vertex v the above condition holds. A root would be a cut vertex when it has more than one sub trees in dfs tree. Since its sub trees are not connected apparently, cutting the root will make the sub trees seperated. So this is the main idea.</p>
<p>Now let’s see how to calculate <strong>dfn</strong> and <strong>low</strong> and implement the algorithm. <strong>dfn</strong> is quite easy to get, we just maintain a counter and increase it by one in each step of the dfs and assign it to the current vertex.<br>For <strong>low</strong>, there are three cases:</p>
<ol>
<li>$low[u] = dfn[u]$, this is the base case.</li>
<li>$low[u] = dfn[v]$, this happens when Edge(u,v) is a back edge.</li>
<li>$low[u] = low[v]$, this happens when Edge(u,v) is a forward edge.</li>
</ol>
<p>Here is the code:<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">505</span>,M=<span class="number">50000</span>;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">edge</span> {</span></span><br><span class="line"> <span class="keyword">int</span> to,next;</span><br><span class="line">} e[M];</span><br><span class="line"><span class="keyword">int</span> head[N],tot;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add_edge</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> v)</span> </span>{</span><br><span class="line"> e[tot].to=v;</span><br><span class="line"> e[tot].next=head[u];</span><br><span class="line"> head[u]=tot++;</span><br><span class="line">}</span><br><span class="line"><span class="keyword">int</span> counter=<span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> dfn[N],low[N];</span><br><span class="line"><span class="keyword">bool</span> found=<span class="literal">false</span>;</span><br><span class="line"><span class="keyword">int</span> n,m;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> pa)</span> </span>{</span><br><span class="line"> dfn[u]=low[u]=++counter;</span><br><span class="line"> <span class="keyword">int</span> son=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=head[u];i!=<span class="number">-1</span>;i=e[i].next) {</span><br><span class="line"> <span class="keyword">int</span> to=e[i].to;</span><br><span class="line"> <span class="keyword">if</span> (!dfn[to]) {</span><br><span class="line"> dfs(to,u);</span><br><span class="line"> <span class="keyword">if</span> (pa!=<span class="number">-1</span>&&dfn[u]<=low[to]) {</span><br><span class="line"> found=<span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line"> low[u]=min(low[u],low[to]);</span><br><span class="line"> son++;</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (to!=pa) {</span><br><span class="line"> low[u]=min(low[u],dfn[to]);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (pa==<span class="number">-1</span>&&son><span class="number">1</span>) {</span><br><span class="line"> found=<span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure><br>It’s just a simple dfs. When <code>found</code> variable is set to true, we get a cut vertex.</p>
<p>A graph that doesn’t contain any cut vertex is called <strong>2-connected</strong>. Let’s go a little further. A <strong>3-connected</strong> graph is such a graph that, after we remove any vertex from it, it’s still <strong>2-connected</strong>. Then how to tell if a graph is <strong>3-connected</strong>? To check if a graph is 2-connected, we can simply run the <strong>Tarjan</strong> algorithm. If we find cut vertex, then it is not 2-connected. So for checking the property of <strong>3-connected</strong>, we can enumerate the vertices and remove it, and then run the <strong>Tarjan</strong> algorithm to find a cut vertex. If after the whole process, we can still not find a cut vertex, then the graph is <strong>3-connected</strong>.<br>Here is a sample question: <a href="http://poj.org/problem?id=3713" target="_blank" rel="noopener">POJ 3713 - Transferring Sylla</a><br>And this is my code:<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><algorithm></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><string></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><string.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><vector></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><math.h></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pb push_back</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> mp make_pair</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ull unsigned ll</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> db double</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INF 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MOD 1000000007</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> PII pair<span class="meta-string"><int, int></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">505</span>,M=<span class="number">50000</span>;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">edge</span> {</span></span><br><span class="line"> <span class="keyword">int</span> to,next;</span><br><span class="line">} e[M];</span><br><span class="line"><span class="keyword">int</span> head[N],tot;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add_edge</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> v)</span> </span>{</span><br><span class="line"> e[tot].to=v;</span><br><span class="line"> e[tot].next=head[u];</span><br><span class="line"> head[u]=tot++;</span><br><span class="line">}</span><br><span class="line"><span class="keyword">int</span> counter=<span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> dfn[N],low[N];</span><br><span class="line"><span class="keyword">bool</span> found=<span class="literal">false</span>;</span><br><span class="line"><span class="keyword">int</span> a[M],b[M],n,m;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> pa)</span> </span>{</span><br><span class="line"> dfn[u]=low[u]=++counter;</span><br><span class="line"> <span class="keyword">int</span> son=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=head[u];i!=<span class="number">-1</span>;i=e[i].next) {</span><br><span class="line"> <span class="keyword">int</span> to=e[i].to;</span><br><span class="line"> <span class="keyword">if</span> (!dfn[to]) {</span><br><span class="line"> dfs(to,u);</span><br><span class="line"> <span class="keyword">if</span> (pa!=<span class="number">-1</span>&&dfn[u]<=low[to]) {</span><br><span class="line"> found=<span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line"> low[u]=min(low[u],low[to]);</span><br><span class="line"> son++;</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (to!=pa) {</span><br><span class="line"> low[u]=min(low[u],dfn[to]);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (pa==<span class="number">-1</span>&&son><span class="number">1</span>) {</span><br><span class="line"> found=<span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">three_conn</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<n;i++) {</span><br><span class="line"> <span class="built_in">memset</span>(head,<span class="number">-1</span>,<span class="keyword">sizeof</span>(head));</span><br><span class="line"> tot=<span class="number">0</span>;</span><br><span class="line"> found=<span class="literal">false</span>;</span><br><span class="line"> counter=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j<m;j++) {</span><br><span class="line"> <span class="keyword">if</span> (a[j]!=i&&b[j]!=i) {</span><br><span class="line"> add_edge(a[j],b[j]);</span><br><span class="line"> add_edge(b[j],a[j]);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">memset</span>(dfn,<span class="number">0</span>,<span class="keyword">sizeof</span>(dfn));</span><br><span class="line"> <span class="built_in">memset</span>(low,<span class="number">0</span>,<span class="keyword">sizeof</span>(low));</span><br><span class="line"> <span class="keyword">if</span> (i==<span class="number">0</span>) {</span><br><span class="line"> dfs(<span class="number">1</span>,<span class="number">-1</span>);</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> dfs(<span class="number">0</span>,<span class="number">-1</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (counter!=n<span class="number">-1</span>||found) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">while</span> (<span class="literal">true</span>) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&n,&m);</span><br><span class="line"> <span class="keyword">if</span> (n==<span class="number">0</span>&&m==<span class="number">0</span>) <span class="keyword">break</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<m;i++) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,a+i,b+i);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (three_conn()) <span class="built_in">printf</span>(<span class="string">"YES\n"</span>);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"NO\n"</span>);</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2018/09/27/connectivity-and-tarjan-algorithm/" data-id="cjo242g98000jg8tscgk0q4yt" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/connectivity/">connectivity</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/dfs/">dfs</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/graph-theory/">graph theory</a></li></ul>
</footer>
</div>
</article>
<article id="post-minimum-cut-problems" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2018/07/15/minimum-cut-problems/" class="article-date">
<time datetime="2018-07-15T03:25:19.000Z" itemprop="datePublished">2018-07-15</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/competitive-programming/">competitive programming</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/07/15/minimum-cut-problems/">Minimum Cut Problems</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>I think these problems are difficult because they are obscure. I mean, we can hardly recognize them and adopt a minimum-cut solution, at least for me. Maybe solving a great many of these problems would help. One characteristic of these problems is that we need to <strong>divide some elements into two sets(source and sink) to get some optimal result</strong>.<br>Let’s see some problems:</p>
<h3 id="POJ-3469-Dual-Core-CPU"><a href="#POJ-3469-Dual-Core-CPU" class="headerlink" title="POJ 3469 - Dual Core CPU"></a>POJ 3469 - Dual Core CPU</h3><p>Problem: <a href="http://poj.org/problem?id=3469" target="_blank" rel="noopener">POJ 3469 - Dual Core CPU</a><br>There are 2 cores A, B and N tasks to be processed. The time cost for the i-th task on A, B are $a_{i}$, $b_{i}$ respectively. And for some tasks, when processed on two different cores, will exert an extra cost. For each task, decide which core should it be processed by to make the total cost minimized.<br>In this problem, we divide the tasks into two sets(processed on A, and on B). So we try to reduce it to a minimum-cut problem. Apparently, the minimized cost corresponds to the minimum cut.<br>For each task <code>i</code>, we add an edge from <code>source</code> to <code>i</code> whose weight equals to $b_{i}$. Then if this edge is among the cut set, task <code>i</code> is processed on core B. For the same reason, we add an edge from <code>i</code> to <code>sink</code> whose weight equals to $a_{i}$. Finally, for those tasks who effect each other, say <code>i</code> and <code>j</code>, we add two edges between <code>i</code> and <code>j</code>(in two directions), whose weight equals to the extra cost. Now the minumum cut of the graph is equal to the minimized cost we want to get.<br>Pseudo code:<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&a,&b);</span><br><span class="line"> add_edge(<span class="number">0</span>,i,b);</span><br><span class="line"> add_edge(i,<span class="number">0</span>,<span class="number">0</span>); <span class="comment">// reverse edge</span></span><br><span class="line"> add_edge(i,n+<span class="number">1</span>,a);</span><br><span class="line"> add_edge(n+<span class="number">1</span>,i,<span class="number">0</span>); <span class="comment">// reverse edge</span></span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i<=m;i++) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>,&a,&b,&w); <span class="comment">// extra cost</span></span><br><span class="line"> add_edge(a,b,w);</span><br><span class="line"> add_edge(b,a,<span class="number">0</span>); <span class="comment">// reverse edge</span></span><br><span class="line"> add_edge(b,a,w);</span><br><span class="line"> add_edge(a,b,<span class="number">0</span>); <span class="comment">// reverse edge</span></span><br><span class="line"> }</span><br><span class="line"> ll mx_flow=max_flow(); <span class="comment">// get the answer</span></span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<h3 id="Code-Jam-World-Finals-2009-Problem-D-Wi-fi-Towers"><a href="#Code-Jam-World-Finals-2009-Problem-D-Wi-fi-Towers" class="headerlink" title="Code Jam - World Finals 2009 - Problem D. Wi-fi Towers"></a>Code Jam - World Finals 2009 - Problem D. Wi-fi Towers</h3><p>Problem: <a href="https://code.google.com/codejam/contest/311101/dashboard#s=p3" target="_blank" rel="noopener">Wi-fi Towers</a><br>Given N wi-fi towers, the i-th is located at $x_{i}$, $y_{i}$, and has a range $r_{i}$. Now we want to upgrade the protocol of them. The score of upgrading the i-th tower is $s_{i}$. When the i-th tower is upgraded, all towers within its range have to be upgraded as well. Decide which towers to be upgraded to make the total score maximized.<br>Wow, world final problem!<br>It’s quite difficult to associate this with minimum-cut. The two sets are <strong>towers to be upgraded</strong> and <strong>towers not to be upgraded</strong>.<br>We want maximum score, so we calculate the minimum <strong>lost</strong>. If $s_{i}$ is negative, the absolute value of it is a lost. We add an edge from <code>source</code> to <code>i</code> whose weight is $|s_{i}|$. If $s_{i}$ is positive, we can imagine that tower i has already been upgraded at first, and “upgrading” it to the origin exerts a lost. We add an edge from <code>i</code> to <code>sink</code> whose weight is $|s_{i}|$. We need to add the positive values to the answer, of course.<br>Then consider the constraints. If <code>j</code> has to be upgraded if <code>i</code> is upgraded, we add an edge from j to i, whose weight is $\infty$. As a result, if we upgrade <code>i</code> without upgrading <code>j</code>, the cut value will be infinity.<br>Now we reduce the minimized lost from the answer, and we get the maximum score.<br>Pseudo code:<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> src=<span class="number">0</span>,sink=n+<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) {</span><br><span class="line"> <span class="keyword">if</span> (s[i]<<span class="number">0</span>) {</span><br><span class="line"> add_edge(<span class="number">0</span>,i,-s[i]);</span><br><span class="line"> add_edge(i,<span class="number">0</span>,<span class="number">0</span>); <span class="comment">// reverse edge</span></span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> add_edge(i,n+<span class="number">1</span>,s[i]);</span><br><span class="line"> add_edge(n+<span class="number">1</span>,i,<span class="number">0</span>); <span class="comment">// reverse edge</span></span><br><span class="line"> ans+=s[i];</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">1</span>;j<=n;j++) {</span><br><span class="line"> <span class="keyword">if</span> (i==j) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="keyword">if</span> (sqr(x[i]-x[j])+sqr(y[i]-y[j])<=sqr(r[i])) { <span class="comment">// within the range</span></span><br><span class="line"> add_edge(j,i,INF);</span><br><span class="line"> add_edge(i,j,<span class="number">0</span>); <span class="comment">// reverse edge</span></span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> mx_flow=max_flow();</span><br><span class="line"> ans-=mx_flow;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>Hope I will recognize the minimum-cut problem when I meet one next time…</p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2018/07/15/minimum-cut-problems/" data-id="cjo242g9d000mg8tsif5d4992" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/max-flow/">max-flow</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/minimum-cut/">minimum-cut</a></li></ul>
</footer>
</div>
</article>
<article id="post-cf-992E" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2018/07/08/cf-992E/" class="article-date">
<time datetime="2018-07-08T01:12:45.000Z" itemprop="datePublished">2018-07-08</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/competitive-programming/">competitive programming</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/07/08/cf-992E/">Codeforces 992E - Nastya and King-Shamans</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>Problem: <a href="http://codeforces.com/problemset/problem/992/E" target="_blank" rel="noopener">Codeforces 992E Nastya and King-Shamans</a><br>Given n intergers $ a_{1},a_{2},…a_{n} $ and q operations $(p_{i}, x_{i})$, $1 \le n,q \le 2 \cdot 10^{5} $. In each operation, change $a_{p_{i}}$ to $x_{i}$, and after that give any index k such that $ a_{k} = \sum_{i=1}^{k-1} a_{i} $ if there exists one.</p>
<h3 id="Segment-tree-solution"><a href="#Segment-tree-solution" class="headerlink" title="Segment tree solution"></a>Segment tree solution</h3><p>For each query, we search the answer from left to right. We maintain a <code>cur_sum</code>, which is the sum of $a_{i}$ we have passed, meaning that we haven’t found a answer till now. So we go on to find it in the right part. We need to find an <strong>leftmost</strong> element that is at least <code>cur_sum</code>. If we find one, then we are done. If we don’t find it, we add that element to <code>cur_sum</code>. As it is the leftmost one, we wouldn’t omit any answer. And since the <code>cur_sum</code> will be at least <strong>twice</strong> as big as it was, the count repeated search for one operation will be at most <strong>log(MAX)</strong>.<br>We can use segment tree to maintain the <strong>sum</strong> and <strong>max value</strong> to do the queries.<br>My code:<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><algorithm></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><string.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><math.h></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pb push_back</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> mp make_pair</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ull unsigned ll</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> db double</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INF 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MOD 1000000007</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> PII pair<span class="meta-string"><int, int></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">200010</span>;</span><br><span class="line">ll s[N*<span class="number">4</span>],mx[N*<span class="number">4</span>],a[N];</span><br><span class="line"><span class="keyword">int</span> n,q,p,x;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">build</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (l==r) {</span><br><span class="line"> mx[x]=s[x]=a[l];</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> m=(l+r)>><span class="number">1</span>;</span><br><span class="line"> build(<span class="number">2</span>*x,l,m);</span><br><span class="line"> build(<span class="number">2</span>*x+<span class="number">1</span>,m+<span class="number">1</span>,r);</span><br><span class="line"> mx[x]=max(mx[<span class="number">2</span>*x],mx[<span class="number">2</span>*x+<span class="number">1</span>]);</span><br><span class="line"> s[x]=s[<span class="number">2</span>*x]+s[<span class="number">2</span>*x+<span class="number">1</span>];</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">update</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> l,<span class="keyword">int</span> r,<span class="keyword">int</span> pos,ll val)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (l==r) {</span><br><span class="line"> mx[x]=s[x]=val;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> m=(l+r)>><span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span> (pos<=m) update(<span class="number">2</span>*x,l,m,pos,val);</span><br><span class="line"> <span class="keyword">else</span> update(<span class="number">2</span>*x+<span class="number">1</span>,m+<span class="number">1</span>,r,pos,val);</span><br><span class="line"> mx[x]=max(mx[<span class="number">2</span>*x],mx[<span class="number">2</span>*x+<span class="number">1</span>]);</span><br><span class="line"> s[x]=s[<span class="number">2</span>*x]+s[<span class="number">2</span>*x+<span class="number">1</span>];</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function">ll <span class="title">get_sum</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> l,<span class="keyword">int</span> r,<span class="keyword">int</span> lq,<span class="keyword">int</span> rq)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (lq<=l&&r<=rq) <span class="keyword">return</span> s[x];</span><br><span class="line"> <span class="keyword">if</span> (lq>r||rq<l) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">int</span> m=(l+r)>><span class="number">1</span>;</span><br><span class="line"> <span class="keyword">return</span> get_sum(<span class="number">2</span>*x,l,m,lq,rq)+get_sum(<span class="number">2</span>*x+<span class="number">1</span>,m+<span class="number">1</span>,r,lq,rq);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">down</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> l,<span class="keyword">int</span> r,ll val)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (l==r) {</span><br><span class="line"> <span class="keyword">if</span> (mx[x]>=val) <span class="keyword">return</span> l;</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">return</span> n+<span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> m=(l+r)>><span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span> (mx[<span class="number">2</span>*x]>=val) <span class="keyword">return</span> down(<span class="number">2</span>*x,l,m,val);</span><br><span class="line"> <span class="keyword">return</span> down(<span class="number">2</span>*x+<span class="number">1</span>,m+<span class="number">1</span>,r,val);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">get_left</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> l,<span class="keyword">int</span> r,<span class="keyword">int</span> lq,<span class="keyword">int</span> rq,ll val)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (l>rq||lq>r) <span class="keyword">return</span> n+<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span> (lq<=l&&r<=rq) {</span><br><span class="line"> <span class="keyword">if</span> (mx[x]<val) <span class="keyword">return</span> n+<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">return</span> down(x,l,r,val);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> m=(l+r)>><span class="number">1</span>;</span><br><span class="line"> <span class="keyword">int</span> res=get_left(<span class="number">2</span>*x,l,m,lq,rq,val);</span><br><span class="line"> <span class="keyword">if</span> (res!=n+<span class="number">1</span>) <span class="keyword">return</span> res;</span><br><span class="line"> <span class="keyword">return</span> get_left(<span class="number">2</span>*x+<span class="number">1</span>,m+<span class="number">1</span>,r,lq,rq,val);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">solve</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> idx=<span class="number">0</span>;</span><br><span class="line"> ll sum=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span> (idx<n+<span class="number">1</span>) {</span><br><span class="line"> <span class="keyword">int</span> new_idx=get_left(<span class="number">1</span>,<span class="number">1</span>,n,idx+<span class="number">1</span>,n,sum);</span><br><span class="line"> <span class="keyword">if</span> (new_idx==n+<span class="number">1</span>) <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line"> ll pre_sum=get_sum(<span class="number">1</span>,<span class="number">1</span>,n,<span class="number">1</span>,new_idx<span class="number">-1</span>);</span><br><span class="line"> ll ele=get_sum(<span class="number">1</span>,<span class="number">1</span>,n,new_idx,new_idx);</span><br><span class="line"> <span class="keyword">if</span> (pre_sum==ele) <span class="keyword">return</span> new_idx;</span><br><span class="line"> idx=new_idx;</span><br><span class="line"> sum=pre_sum+ele;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&n,&q);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) <span class="built_in">scanf</span>(<span class="string">"%lld"</span>,a+i);</span><br><span class="line"> build(<span class="number">1</span>,<span class="number">1</span>,n);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i<=q;i++) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&p,&x);</span><br><span class="line"> update(<span class="number">1</span>,<span class="number">1</span>,n,p,x);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>,solve());</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<h3 id="Square-decomposition"><a href="#Square-decomposition" class="headerlink" title="Square decomposition"></a>Square decomposition</h3><p>Let $p_{i}$ be the prefix sum of a, and $f_{i} = p_{i} - 2 \cdot a_{i}$. Then we only need to find an i such that $f_{i} = 0$. And each time we change $a_{i}$ to <code>val</code>, let $\delta = val - a_{i}$, $f_{i}$ should decrease by $\delta$ whereas $f_{k}(k>i)$ should increase by $\delta$.<br>Next we divide the sequence of groups of size M. For each change, we may change at most <strong>N\M</strong> groups as a whole and deal with all the elements in one group. And for query, we keep all elements in a group in order so that we can use binary search. To do with the single group which is not entirely coverd by the range, we can do something like merging sorted vectors.<br>Though the solution is still too slow to pass the tests, I think square decomposition is powerful in data structrue problems.<br>My code:<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><algorithm></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><string.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><math.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><vector></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pb push_back</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> mp make_pair</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ull unsigned ll</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> db double</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INF 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MOD 1000000007</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> PII pair<span class="meta-string"><int, int></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">200010</span>;</span><br><span class="line"><span class="keyword">int</span> M=<span class="number">500</span>;</span><br><span class="line"><span class="keyword">int</span> n,p,q,x,a[N],s[N];</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span> {</span></span><br><span class="line"> ll val;</span><br><span class="line"> <span class="keyword">int</span> idx;</span><br><span class="line"> <span class="keyword">bool</span> <span class="keyword">operator</span><(<span class="keyword">const</span> node& rhs) <span class="keyword">const</span> {</span><br><span class="line"> <span class="keyword">return</span> val<rhs.val;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">bool</span> <span class="keyword">operator</span>==(<span class="keyword">const</span> node& rhs) <span class="keyword">const</span> {</span><br><span class="line"> <span class="keyword">return</span> val==rhs.val;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"><span class="built_in">vector</span><node> aim[<span class="number">1000</span>];</span><br><span class="line">ll acc[<span class="number">1000</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">modify_group</span><span class="params">(<span class="keyword">int</span> idx,ll delta)</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> gid=idx/M;</span><br><span class="line"> <span class="built_in">vector</span><node> v1,v2;</span><br><span class="line"> ll pivot=<span class="number">-1</span>;</span><br><span class="line"> <span class="keyword">bool</span> added=<span class="literal">false</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<aim[gid].size();i++) {</span><br><span class="line"> <span class="keyword">if</span> (aim[gid][i].idx==idx) {</span><br><span class="line"> pivot=aim[gid][i].val-delta;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<aim[gid].size();i++) {</span><br><span class="line"> <span class="keyword">if</span> (aim[gid][i].idx<idx) {</span><br><span class="line"> <span class="keyword">if</span> (!added&&pivot<=aim[gid][i].val) {</span><br><span class="line"> v1.pb({pivot,idx});</span><br><span class="line"> added=<span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line"> v1.pb(aim[gid][i]);</span><br><span class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> (aim[gid][i].idx>idx) {</span><br><span class="line"> v2.pb(aim[gid][i]);</span><br><span class="line"> v2.back().val+=delta;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (!added) { v1.pb({pivot,idx}); }</span><br><span class="line"> aim[gid].clear();</span><br><span class="line"> merge(v1.begin(),v1.end(),v2.begin(),v2.end(),back_inserter(aim[gid]));</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&n,&q);</span><br><span class="line"> M=<span class="built_in">sqrt</span>(n)+<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<n;i++) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,a+i);</span><br><span class="line"> s[i]=a[i];</span><br><span class="line"> <span class="keyword">if</span> (i><span class="number">0</span>) s[i]+=s[i<span class="number">-1</span>];</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<n;i++) {</span><br><span class="line"> aim[i/M].pb({s[i]<span class="number">-2</span>*a[i],i});</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> g=n/M+<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<g;i++) sort(aim[i].begin(),aim[i].end());</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<q;i++) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&p,&x);</span><br><span class="line"> p--;</span><br><span class="line"> <span class="keyword">int</span> id=p/M+<span class="number">1</span>;</span><br><span class="line"> ll delta=x-a[p];</span><br><span class="line"> a[p]=x;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j=id;j<g;j++) acc[j]+=delta;</span><br><span class="line"> modify_group(p,delta);</span><br><span class="line"> <span class="keyword">bool</span> found=<span class="literal">false</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j<g;j++) {</span><br><span class="line"> node nd={-acc[j],<span class="number">-1</span>};</span><br><span class="line"> <span class="keyword">auto</span> iter=lower_bound(aim[j].begin(),aim[j].end(),nd);</span><br><span class="line"> <span class="keyword">if</span> (iter!=aim[j].end()&&(*iter).val==-acc[j]) {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>,(*iter).idx+<span class="number">1</span>);</span><br><span class="line"> found=<span class="literal">true</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (!found) <span class="built_in">printf</span>(<span class="string">"-1\n"</span>);</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2018/07/08/cf-992E/" data-id="cjo242g8v0005g8tsyn2a6r1p" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/data-structure/">data structure</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/segment-tree/">segment tree</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/square-decomposition/">square decomposition</a></li></ul>
</footer>
</div>
</article>
<article id="post-cf-995C" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2018/07/07/cf-995C/" class="article-date">
<time datetime="2018-07-07T13:44:57.000Z" itemprop="datePublished">2018-07-07</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/competitive-programming/">competitive programming</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/07/07/cf-995C/">Codeforces 995C Leaving the Bar</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>Problem: <a href="http://codeforces.com/contest/995/problem/C" target="_blank" rel="noopener">Codeforces 995C Leaving the Bar</a><br>Given n two-dimensional vectors $\vec v_{i}$ and n intergers $ c_{1},c_{2},…c_{n} $. It’s guaranteed that $ |v| \le 1e6 $ and $ c_{i} = 1 or -1 $. Let $\vec p = \sum_{i=1}^{n} c_{i}\vec v_{i}$. Determine the value of $c_{i}$ to satisfy $|p| \le 1.5 \cdot 1e6$.</p>
<p>As n is at most $10^{5}$, it is impossible to enumerate all the cases.<br>The key to solve this problem is such a conclusion:<br><strong>Given 3 vectors $\vec v$, $|v| \le R$, we can always get some $\vec v_{i} + \vec v_{j}$ or $\vec v_{i} - \vec v_{j}$ that has length at least R.</strong><br>With the opposite vectors of the 3 vectors, there are 6 vectors altogether now. So if we divide the plane into 6 60-degree sectors, there is at least one sector that contains two vectors(they are not the opposite for sure). Pretty good.</p>
<p>So we can merge vectors until there are only 2 vectors.<br>We always pick 3 vectors and merge 2 of them if the length of the result vector is less equal than 1e6.<br>And we can ensure that length of the sum or difference of the last 2 vectors is less equal than $\sqrt{2} \cdot 1e6 \le 1.5 \cdot 1e6$.</p>
<p>My Code:<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><algorithm></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><string.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><math.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><queue></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pb push_back</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> mp make_pair</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ull unsigned ll</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> db double</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INF 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MOD 1000000007</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> PII pair<span class="meta-string"><int, int></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">100010</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> R=<span class="number">1000000</span>;</span><br><span class="line"><span class="keyword">const</span> db eps=<span class="number">1e-8</span>;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">P</span> {</span></span><br><span class="line"> db x,y;</span><br><span class="line"> P(){}</span><br><span class="line"> P(db xx,db yy):x(xx),y(yy){}</span><br><span class="line"> P <span class="keyword">operator</span>+(P rhs) {</span><br><span class="line"> <span class="keyword">return</span> P(x+rhs.x,y+rhs.y);</span><br><span class="line"> }</span><br><span class="line"> P <span class="keyword">operator</span>-(P rhs) {</span><br><span class="line"> <span class="keyword">return</span> P(x-rhs.x,y-rhs.y);</span><br><span class="line"> }</span><br><span class="line"> P <span class="keyword">operator</span>*(db k) {</span><br><span class="line"> <span class="keyword">return</span> P(k*x,k*y);</span><br><span class="line"> }</span><br><span class="line"> <span class="function">db <span class="title">dot</span><span class="params">(P rhs)</span> </span>{</span><br><span class="line"> <span class="keyword">return</span> x*rhs.x+y*rhs.y;</span><br><span class="line"> }</span><br><span class="line"> <span class="function">db <span class="title">det</span><span class="params">(P rhs)</span> </span>{</span><br><span class="line"> <span class="keyword">return</span> x*rhs.y-y*rhs.x;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span> {</span></span><br><span class="line"> <span class="keyword">int</span> ls,rs,type;</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n,tot=<span class="number">0</span>;</span><br><span class="line">P vec[<span class="number">2</span>*N];</span><br><span class="line">node nd[<span class="number">2</span>*N];</span><br><span class="line"><span class="keyword">int</span> ans[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> id,<span class="keyword">int</span> type)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (nd[id].ls==<span class="number">-1</span>) {</span><br><span class="line"> ans[id]=type;</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> dfs(nd[id].ls,type);</span><br><span class="line"> dfs(nd[id].rs,type*nd[id].type);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&n);</span><br><span class="line"> <span class="built_in">queue</span><<span class="keyword">int</span>> q;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<n;i++) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%lf%lf"</span>,&vec[tot].x,&vec[tot].y);</span><br><span class="line"> nd[tot++]={<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">1</span>};</span><br><span class="line"> q.push(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">while</span> (q.size()><span class="number">2</span>) {</span><br><span class="line"> <span class="keyword">int</span> a[<span class="number">3</span>]={<span class="number">-1</span>};</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<<span class="number">3</span>;i++) {</span><br><span class="line"> a[i]=q.front();</span><br><span class="line"> q.pop();</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> x=<span class="number">-1</span>,y=<span class="number">-1</span>,type=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<<span class="number">3</span>&&x==<span class="number">-1</span>;i++) {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j=i+<span class="number">1</span>;j<<span class="number">3</span>&&x==<span class="number">-1</span>;j++) {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">sqrt</span>((vec[a[i]]+vec[a[j]]).dot(vec[a[i]]+vec[a[j]]))<R+eps) {</span><br><span class="line"> x=a[i],y=a[j];</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">sqrt</span>((vec[a[i]]-vec[a[j]]).dot(vec[a[i]]-vec[a[j]]))<R+eps) {</span><br><span class="line"> x=a[i],y=a[j],type=<span class="number">-1</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<<span class="number">3</span>;i++) {</span><br><span class="line"> <span class="keyword">if</span> (a[i]!=x&&a[i]!=y) q.push(a[i]);</span><br><span class="line"> }</span><br><span class="line"> nd[tot]={x,y,type};</span><br><span class="line"> vec[tot]=vec[x]+(vec[y]*type);</span><br><span class="line"> q.push(tot++);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (q.size()<<span class="number">2</span>) {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"1\n"</span>);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> x=q.front();q.pop();</span><br><span class="line"> <span class="keyword">int</span> y=q.front();q.pop();</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">sqrt</span>((vec[x]+vec[y]).dot(vec[x]+vec[y]))<<span class="built_in">sqrt</span>(<span class="number">2</span>)*R+eps) {</span><br><span class="line"> nd[tot++]={x,y,<span class="number">1</span>};</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> nd[tot++]={x,y,<span class="number">-1</span>};</span><br><span class="line"> }</span><br><span class="line"> dfs(tot<span class="number">-1</span>,<span class="number">1</span>);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<n;i++) <span class="built_in">printf</span>(<span class="string">"%d "</span>,ans[i]);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"\n"</span>);</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2018/07/07/cf-995C/" data-id="cjo242g900009g8ts9f6iq2yi" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/brute-force/">brute force</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/codeforces/">codeforces</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/geometry/">geometry</a></li></ul>
</footer>
</div>
</article>
<article id="post-subsets-property-merge" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2018/07/07/subsets-property-merge/" class="article-date">
<time datetime="2018-07-07T02:47:37.000Z" itemprop="datePublished">2018-07-07</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/competitive-programming/">competitive programming</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/07/07/subsets-property-merge/">Subsets Property Merge</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>Given such a problem:<br>There is a sequence of length N: $ A_{0} $, $ A_{1} $,…, $ A_{N} $. For every integer K satisfying $ 1 \le K \le N $, find the maximum value of $A_{i}+A_{j}$ where $i\subseteq K$ and $j \subseteq K$. Here, <strong>$a \subseteq b$</strong> means that, in binary representation, the set of positions of a is a subset of that of b.<br>This problem is actually a subproblem of <a href="https://beta.atcoder.jp/contests/arc100/tasks/arc100_c" target="_blank" rel="noopener">ARC 100 E</a>. The solution to such problem is very similar to dynamic programming and I think it could be used in many cases.<br>Code:<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><algorithm></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><string.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><math.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><vector></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pb push_back</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> mp make_pair</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ull unsigned ll</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> db double</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INF 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MOD 1000000007</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> PII pair<span class="meta-string"><int, int></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">1</span><<<span class="number">18</span>;</span><br><span class="line"><span class="keyword">int</span> a[N];</span><br><span class="line">PII mx[N];</span><br><span class="line"><span class="keyword">int</span> n; <span class="comment">// n is the count of digits</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">cmp</span><span class="params">(<span class="keyword">int</span> i,<span class="keyword">int</span> j)</span> </span>{</span><br><span class="line"> <span class="keyword">return</span> a[i]<a[j];</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="built_in">vector</span><<span class="keyword">int</span>> cur;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<(<span class="number">1</span><<n);i++) {</span><br><span class="line"> cur.clear();</span><br><span class="line"> cur.pb(i);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j<n;j++) {</span><br><span class="line"> <span class="keyword">if</span> ((i>>j)&<span class="number">1</span>) {</span><br><span class="line"> <span class="keyword">int</span> x=i^(<span class="number">1</span><<j);</span><br><span class="line"> cur.pb(mx[x].first);</span><br><span class="line"> <span class="keyword">if</span> (mx[i].second!=<span class="number">-1</span>) cur.pb(mx[x].second);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> sort(cur.begin(),cur.end());</span><br><span class="line"> cur.resize(unique(cur.begin(),cur.end())-cur.begin());</span><br><span class="line"> <span class="keyword">if</span> (cur.size()==<span class="number">1</span>) {</span><br><span class="line"> mx[i]=mp(cur[<span class="number">0</span>],<span class="number">-1</span>);</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> mx[i]=mp(cur[<span class="number">0</span>],cur[<span class="number">1</span>]);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure><br>The two elements of <code>mx[k]</code> are the two largest elements satisfying $i \subseteq k$ and $j \subseteq k$. So we can get the maximum value of $A_{i} + A_{j}$.<br>Here we compute the result of k from the result of its <em>subsets</em>(has only one bit different).</p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2018/07/07/subsets-property-merge/" data-id="cjo242g9m000yg8tsd3abl1st" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/dynamic-programming/">dynamic programming</a></li></ul>
</footer>
</div>
</article>
<article id="post-geometry-basics" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2018/07/02/geometry-basics/" class="article-date">
<time datetime="2018-07-02T15:00:08.000Z" itemprop="datePublished">2018-07-02</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/competitive-programming/">competitive programming</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/07/02/geometry-basics/">Geometry Basics</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>Geometry is a important part in competitive programming. However, it doesn’t appear much in small races. That’s why I’m quite unfamiliar with it. But I’m convinced that I will have to handle these problems sooner or later.</p>
<p>This blog is just a very start of geometry. I collect some very basic things in geometry and we only talk about two-dimensional. All the vectors mentioned below are two-dimensional.</p>
<p>I would introduce:</p>
<ol start="0">
<li>Common data structure for geometry problems</li>
<li>Dot product</li>
<li>Cross product</li>
<li>Are the two vectors parallel</li>
<li>Is the point on the line or the segment</li>
<li>Get the cross point of two lines</li>
<li>Do the two segments touch each other</li>
</ol>
<h3 id="Common-data-structure"><a href="#Common-data-structure" class="headerlink" title="Common data structure"></a>Common data structure</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">P</span> {</span></span><br><span class="line"> db x,y;</span><br><span class="line"> P(){}</span><br><span class="line"> P(db xx,db yy):x(xx),y(yy){}</span><br><span class="line"> P <span class="keyword">operator</span>+(P rhs) {</span><br><span class="line"> <span class="keyword">return</span> P(x+rhs.x,y+rhs.y);</span><br><span class="line"> }</span><br><span class="line"> P <span class="keyword">operator</span>-(P rhs) {</span><br><span class="line"> <span class="keyword">return</span> P(x-rhs.x,y-rhs.y);</span><br><span class="line"> }</span><br><span class="line"> P <span class="keyword">operator</span>*(db k) {</span><br><span class="line"> <span class="keyword">return</span> P(k*x,k*y);</span><br><span class="line"> }</span><br><span class="line"> <span class="function">db <span class="title">dot</span><span class="params">(P rhs)</span> </span>{</span><br><span class="line"> <span class="keyword">return</span> x*rhs.x+y*rhs.y;</span><br><span class="line"> }</span><br><span class="line"> <span class="function">db <span class="title">det</span><span class="params">(P rhs)</span> </span>{</span><br><span class="line"> <span class="keyword">return</span> x*rhs.y-y*rhs.x;</span><br><span class="line"> }</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
<p>This is a really simple struct, but it is quite powerful. It enables us to implement geometry algorithm elegantly. One of the good parts of it is that it can be taken as both a <code>Point</code> as well as a <code>Two-dimensional vector</code>.</p>
<h3 id="Dot-product"><a href="#Dot-product" class="headerlink" title="Dot product"></a>Dot product</h3><p>$$ \overrightarrow{AB} \cdot \overrightarrow{AC} = a $$<br>The geometric meaning of dot product is the length(maybe negative) of the projection of one vector onto the other. The result of dot product is a <strong>value</strong>.</p>
<h3 id="Cross-product"><a href="#Cross-product" class="headerlink" title="Cross product"></a>Cross product</h3><p>$$ \overrightarrow{AB} \times \overrightarrow{AC} = \overrightarrow{AD} $$<br>The result of cross product is actually a <strong>vector</strong> which is perpendicular to the plane which is deterimined by the two vectors. But in two dimension, we can take the result as a <strong>value</strong> which is equal to the area of the parallelogram determined by the two vectors.</p>
<h3 id="Are-the-two-vectors-parallel"><a href="#Are-the-two-vectors-parallel" class="headerlink" title="Are the two vectors parallel"></a>Are the two vectors parallel</h3><p>This is quite simple. When two vectors are parallel, the area of the parallelogram formed by them is <strong>0</strong>. So we can use cross product to get the area of the parallelogram and tell if the two vectors are parallel.</p>
<h3 id="Is-the-point-on-the-line-or-the-segment"><a href="#Is-the-point-on-the-line-or-the-segment" class="headerlink" title="Is the point on the line or the segment"></a>Is the point on the line or the segment</h3><p>Let’s start with line. Call the point to be judged <code>A</code>, and find any two points <code>B</code>,<code>C</code> on the line.<br>Obviously, if <code>A</code> is on the line, then we have:<br>$$ \overrightarrow{AB} \times \overrightarrow{AC} = 0 $$<br>Now let’s go with segment. We call the two endpoints of the segment <code>B</code>, <code>C</code> now.<br>If <code>A</code> is on the segment, <code>A</code> has to be on the line first. Then <code>B</code> and <code>C</code> should be on different sides of <code>A</code>. We can check this simply by:<br>$$ \overrightarrow{AB} \cdot \overrightarrow{AC} <= 0 $$</p>
<h3 id="Get-the-cross-point-of-two-lines"><a href="#Get-the-cross-point-of-two-lines" class="headerlink" title="Get the cross point of two lines"></a>Get the cross point of two lines</h3><p>We need pay attention to whether the two lines are <strong>exactly the same line</strong> and whether they are <strong>parallel</strong> at first.<br>Say, <code>p1</code> and <code>p2</code> are two points one line 1.<br>Then we can represent any point on line 1 as: $ p_{1} + t \cdot (p_{2} - p_{1}) $.<br>And what we need to do is to calculate <code>t</code> to make the point on line 2.<br>We can calculate <code>t</code> as :<br>$$<br>t = \frac<br>{(q_{2} - q_{1}) \times (q_{1} - p_{1})}<br>{(q_{2} - q_{1}) \times (p_{2} - p_{1})}<br>$$<br>So the cross point is:<br>$$<br>p_{1} +<br>\frac<br>{(q_{2} - q_{1}) \times (q_{1} - p_{1})}<br>{(q_{2} - q_{1}) \times (p_{2} - p_{1})}<br>\cdot<br>(p_{2} - p_{1})<br>$$<br>I cannot explain clearly why it works. We can simply think the proportion of area of two parallelograms.</p>
<h3 id="Do-the-two-segments-touch-each-other"><a href="#Do-the-two-segments-touch-each-other" class="headerlink" title="Do the two segments touch each other"></a>Do the two segments touch each other</h3><p>Since we have <strong>4</strong> and <strong>5</strong>, we can do tell this easily. First, we get the cross point of the two lines where the two segments lie. Next, we judge if the cross point is on both segments. Really simple, right?</p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2018/07/02/geometry-basics/" data-id="cjo242g94000eg8tsiijhzi2d" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/geometry/">geometry</a></li></ul>
</footer>
</div>
</article>
<article id="post-max-flow-algorithm" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2018/06/30/max-flow-algorithm/" class="article-date">
<time datetime="2018-06-30T01:16:14.000Z" itemprop="datePublished">2018-06-30</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/competitive-programming/">competitive programming</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/06/30/max-flow-algorithm/">Max Flow Algorithm</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p><strong>Maximum</strong> flow is a important part of graph theory in competitive programming. There have been already thousands of articles and blogs teaching people the principle and the implementation of max flow. So I’m not going to elaborate these things again. This blog is just written to help me implement the max flow algorithm faster in a competition with less mistakes.</p>
<h2 id="Ford-Fulkson"><a href="#Ford-Fulkson" class="headerlink" title="Ford-Fulkson"></a>Ford-Fulkson</h2><p>The main idea of max flow algorithm is to find <strong>augmented path</strong> until there is no one. When we find an augmented path, we need to change the residual graph. We should reduce the capcity of each edge on the path and increase it on each reverse edge on it by the flow we found. So in the implementation we don’t need to store the current flow of each edge, we just need to store the capcity of them.<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">20005</span>,M=<span class="number">2000005</span>;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">edge</span> {</span></span><br><span class="line"> <span class="keyword">int</span> to,next,cap;</span><br><span class="line">} e[N];</span><br><span class="line"><span class="keyword">int</span> head[N],tot;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add_edge</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> v,<span class="keyword">int</span> cap)</span> </span>{</span><br><span class="line"> e[tot].to=v;</span><br><span class="line"> e[tot].cap=cap;</span><br><span class="line"> e[tot].next=head[u];</span><br><span class="line"> head[u]=tot++;</span><br><span class="line">}</span><br><span class="line"><span class="keyword">bool</span> vis[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> sink,<span class="keyword">int</span> f)</span> </span>{</span><br><span class="line"> vis[u]=<span class="literal">true</span>;</span><br><span class="line"> <span class="keyword">if</span> (u==sink) <span class="keyword">return</span> f;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=head[u];i!=<span class="number">-1</span>;i=e[i].next) {</span><br><span class="line"> <span class="keyword">int</span> to=e[i].to;</span><br><span class="line"> <span class="keyword">if</span> (!vis[to]&&e[i].cap><span class="number">0</span>) {</span><br><span class="line"> <span class="keyword">int</span> ff=dfs(to,min(f,e[i].cap));</span><br><span class="line"> <span class="keyword">if</span> (ff><span class="number">0</span>) {</span><br><span class="line"> e[i].cap-=cap;</span><br><span class="line"> e[i^<span class="number">1</span>].cap+=cap;</span><br><span class="line"> <span class="keyword">return</span> ff;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="comment">// Get input</span></span><br><span class="line"> <span class="built_in">memset</span>(head,<span class="number">-1</span>,<span class="keyword">sizeof</span>(head));</span><br><span class="line"> <span class="comment">// Build graph here</span></span><br><span class="line"> <span class="keyword">int</span> max_flow=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span> (<span class="literal">true</span>) {</span><br><span class="line"> <span class="built_in">memset</span>(vis,<span class="number">0</span>,<span class="keyword">sizeof</span>(vis));</span><br><span class="line"> <span class="keyword">int</span> ff=dfs(src,sink,INF);</span><br><span class="line"> <span class="keyword">if</span> (ff><span class="number">0</span>) max_flow+=ff;</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"max_flow:%d\n"</span>,max_flow);</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p><strong>Ford-Fulkson</strong> is fast enough in most cases. But sometime it cannot meet our requirements. That’s why we need <strong>Dinic</strong>.</p>
<h2 id="Dinic"><a href="#Dinic" class="headerlink" title="Dinic"></a>Dinic</h2><p>Two optimizations are used in <strong>Dinic</strong> which make it faster. One is<code>level</code> array and the other is <code>arc optimization</code>. I’m not going to elaborate how they work here. Different from <strong>Ford-Fulkson</strong>, it runs a <code>bfs</code> to build the <code>level graph</code> and then run <code>dfs</code> a couple of times(without initializing).<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">20005</span>,M=<span class="number">2000005</span>;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">edge</span> {</span></span><br><span class="line"> <span class="keyword">int</span> to,next,cap;</span><br><span class="line">} e[N];</span><br><span class="line"><span class="keyword">int</span> head[N],tot;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add_edge</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> v,<span class="keyword">int</span> cap)</span> </span>{</span><br><span class="line"> e[tot].to=v;</span><br><span class="line"> e[tot].cap=cap;</span><br><span class="line"> e[tot].next=head[u];</span><br><span class="line"> head[u]=tot++;</span><br><span class="line">}</span><br><span class="line"><span class="keyword">int</span> level[N],iter[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">bfs</span><span class="params">(<span class="keyword">int</span> src)</span> </span>{</span><br><span class="line"> <span class="built_in">queue</span><<span class="keyword">int</span>> q;</span><br><span class="line"> <span class="built_in">memset</span>(level,<span class="number">-1</span>,<span class="keyword">sizeof</span>(level));</span><br><span class="line"> level[src]=<span class="number">0</span>;</span><br><span class="line"> q.push(src);</span><br><span class="line"> <span class="keyword">while</span> (!q.empty()) {</span><br><span class="line"> <span class="keyword">int</span> cur=q.front();</span><br><span class="line"> q.pop();</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=head[cur];i!=<span class="number">-1</span>;i=e[i].next) {</span><br><span class="line"> <span class="keyword">int</span> to=e[i].to;</span><br><span class="line"> <span class="keyword">if</span> (e[i].cap><span class="number">0</span>&&level[to]==<span class="number">-1</span>) {</span><br><span class="line"> level[to]=level[cur]+<span class="number">1</span>;</span><br><span class="line"> q.push(to);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> sink,<span class="keyword">int</span> f)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (u==sink) <span class="keyword">return</span> f;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span>& i=iter[u];i!=<span class="number">-1</span>;i=e[i].next) {</span><br><span class="line"> <span class="keyword">int</span> to=e[i].to;</span><br><span class="line"> <span class="keyword">if</span> (e[i].cap><span class="number">0</span>&&level[u]<level[to]) {</span><br><span class="line"> <span class="keyword">int</span> ff=dfs(to,sink,min(f,e[i].cap));</span><br><span class="line"> <span class="keyword">if</span> (ff><span class="number">0</span>) {</span><br><span class="line"> e[i].cap-=ff;</span><br><span class="line"> e[i^<span class="number">1</span>].cap+=ff;</span><br><span class="line"> <span class="keyword">return</span> ff;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="comment">// Get input</span></span><br><span class="line"> <span class="built_in">memset</span>(head,<span class="number">-1</span>,<span class="keyword">sizeof</span>(head));</span><br><span class="line"> <span class="comment">// Build graph here</span></span><br><span class="line"> <span class="keyword">int</span> mx_flow=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span> (<span class="literal">true</span>) {</span><br><span class="line"> bfs(src);</span><br><span class="line"> <span class="keyword">if</span> (level[sink]==<span class="number">-1</span>) <span class="keyword">break</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) iter[i]=head[i];</span><br><span class="line"> <span class="keyword">int</span> ff;</span><br><span class="line"> <span class="keyword">while</span> ((ff=dfs(src,sink,INF)><span class="number">0</span>)) {</span><br><span class="line"> mx_flow+=ff;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>,mx_flow);</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2018/06/30/max-flow-algorithm/" data-id="cjo242g96000gg8tsd9seitor" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/max-flow/">max-flow</a></li></ul>
</footer>
</div>
</article>
<article id="post-cf-984E" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2018/06/10/cf-984E/" class="article-date">
<time datetime="2018-06-10T14:24:38.000Z" itemprop="datePublished">2018-06-10</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/competitive-programming/">competitive programming</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/06/10/cf-984E/">Codeforces 984E Elevator</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<p>The problem: <a href="http://codeforces.com/problemset/problem/984/E" target="_blank" rel="noopener">Codeforces 984E Elevator</a><br>I failed to solve the problem by myself although I believed it should be solved by dp immediately after I read the problem. The difficult and interesting part of this problem is how to arrange the <strong>state</strong> of the whole process so that the total number of <strong>state</strong> is as small as possible.<br>Let’s think about it. For a state transition, we need to know:</p>
<ol>
<li>How many people have got in the elevator(may have got out).</li>
<li>Current floor.</li>
<li>Which floors do people currently in the elevator want to go.</li>
</ol>
<p>The only problem is third one. There are at most 4 people in the elevator and each person may go to each of the 9 floors. So there would be<br>$$ 10^4=10000 $$<br>states in total in the 3rd dimension of dp.<br>However, it is a little bit more than we can afford. Actually some of the states in the above are repeated. Say, <code>person 1 goes to floor 3 and person 2 goes to floor 4</code> is the same as <code>person 1 goes to floor 4 and person 2 goes to 3</code>. So we only care about how many people go to each floor, with no need to know who. Hence the total number of state is:<br>$$ \binom{9}{0} + \binom{9}{1} + \binom{9}{2} + \binom{9}{3} + \binom{9}{4} = 256 $$</p>
<p>This enable us to get accepted.<br>And some technique should be adopted to represent the state. Instead of using integers, we use a 4-char-long string to represent a state. With the help of map, we can implement it nicely:<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><algorithm></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><string.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><math.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><map></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> int_ int64_t</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pb push_back</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> mp make_pair</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ull unsigned ll</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> db double</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INF 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MOD 1000003</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> PII pair<span class="meta-string"><int, int></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">2010</span>;</span><br><span class="line"><span class="keyword">int</span> n,a[N],b[N];</span><br><span class="line"><span class="built_in">map</span><<span class="built_in">string</span>,<span class="keyword">int</span>> dp[N][<span class="number">10</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> idx,<span class="keyword">int</span> cur,<span class="keyword">const</span> <span class="built_in">string</span>& s)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (idx>n&&s==<span class="string">"0000"</span>) { <span class="keyword">return</span> <span class="number">0</span>; }</span><br><span class="line"> <span class="keyword">int</span>& res=dp[idx][cur][s];</span><br><span class="line"> <span class="keyword">if</span> (res) <span class="keyword">return</span> res;</span><br><span class="line"> res=INF;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">char</span> c=<span class="string">'1'</span>;c<=<span class="string">'9'</span>;c++) {</span><br><span class="line"> <span class="built_in">string</span> t=s;</span><br><span class="line"> <span class="keyword">int</span> x=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<<span class="number">4</span>;i++) {</span><br><span class="line"> <span class="keyword">if</span> (t[i]==c) t[i]=<span class="string">'0'</span>,x++;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> now=idx;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i<<span class="number">4</span>;i++) {</span><br><span class="line"> <span class="keyword">if</span> (t[i]==<span class="string">'0'</span>&&now<=n&&a[now]+<span class="string">'0'</span>==c) {</span><br><span class="line"> t[i]=b[now++]+<span class="string">'0'</span>;</span><br><span class="line"> x++;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> sort(t.begin(),t.end());</span><br><span class="line"> <span class="keyword">if</span> (idx==now&&t==s) <span class="keyword">continue</span>;</span><br><span class="line"> res=min(res,<span class="built_in">abs</span>(cur-(c-<span class="string">'0'</span>))+x+dfs(now,c-<span class="string">'0'</span>,t));</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> res;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&n);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,a+i,b+i);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>,dfs(<span class="number">1</span>,<span class="number">1</span>,<span class="string">"0000"</span>));</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
</div>
<footer class="article-footer">
<a data-url="http://yoursite.com/2018/06/10/cf-984E/" data-id="cjo242g8w0006g8tsqgirv6t3" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/codeforces/">codeforces</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/dynamic-programming/">dynamic programming</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/state-compression/">state compression</a></li></ul>
</footer>
</div>
</article>
<nav id="page-nav">
<span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><a class="extend next" rel="next" href="/page/2/">Next »</a>
</nav>
</section>
<aside id="sidebar">
<div class="widget-wrap">
<h3 class="widget-title">Categories</h3>
<div class="widget">
<ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/competitive-programming/">competitive programming</a></li></ul>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">Tags</h3>
<div class="widget">
<ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/ad-hoc/">ad-hoc</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/binary-search/">binary search</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/bipartite-graph/">bipartite graph</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/brute-force/">brute force</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/cmake/">cmake</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/codeforces/">codeforces</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/combinatorics/">combinatorics</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/connectivity/">connectivity</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/cpp/">cpp</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/data-structure/">data structure</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/dfs/">dfs</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/dinkelbach-theorem/">dinkelbach theorem</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/dynamic-programming/">dynamic programming</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/fractional-programming/">fractional programming</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/geometry/">geometry</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/graph-theory/">graph theory</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/maths/">maths</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/max-flow/">max-flow</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/minimum-cut/">minimum-cut</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/net/">net</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/segment-tree/">segment tree</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/square-decomposition/">square decomposition</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/state-compression/">state compression</a></li></ul>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">Tag Cloud</h3>
<div class="widget tagcloud">
<a href="/tags/ad-hoc/" style="font-size: 10px;">ad-hoc</a> <a href="/tags/algorithm/" style="font-size: 20px;">algorithm</a> <a href="/tags/binary-search/" style="font-size: 10px;">binary search</a> <a href="/tags/bipartite-graph/" style="font-size: 10px;">bipartite graph</a> <a href="/tags/brute-force/" style="font-size: 10px;">brute force</a> <a href="/tags/cmake/" style="font-size: 10px;">cmake</a> <a href="/tags/codeforces/" style="font-size: 17.5px;">codeforces</a> <a href="/tags/combinatorics/" style="font-size: 10px;">combinatorics</a> <a href="/tags/connectivity/" style="font-size: 10px;">connectivity</a> <a href="/tags/cpp/" style="font-size: 10px;">cpp</a> <a href="/tags/data-structure/" style="font-size: 10px;">data structure</a> <a href="/tags/dfs/" style="font-size: 10px;">dfs</a> <a href="/tags/dinkelbach-theorem/" style="font-size: 10px;">dinkelbach theorem</a> <a href="/tags/dynamic-programming/" style="font-size: 15px;">dynamic programming</a> <a href="/tags/fractional-programming/" style="font-size: 10px;">fractional programming</a> <a href="/tags/geometry/" style="font-size: 12.5px;">geometry</a> <a href="/tags/graph-theory/" style="font-size: 12.5px;">graph theory</a> <a href="/tags/maths/" style="font-size: 10px;">maths</a> <a href="/tags/max-flow/" style="font-size: 12.5px;">max-flow</a> <a href="/tags/minimum-cut/" style="font-size: 10px;">minimum-cut</a> <a href="/tags/net/" style="font-size: 10px;">net</a> <a href="/tags/segment-tree/" style="font-size: 10px;">segment tree</a> <a href="/tags/square-decomposition/" style="font-size: 10px;">square decomposition</a> <a href="/tags/state-compression/" style="font-size: 10px;">state compression</a>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">Archives</h3>
<div class="widget">
<ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/11/">November 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/10/">October 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/09/">September 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/07/">July 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/06/">June 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/11/">November 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/10/">October 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/09/">September 2017</a></li></ul>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">Recent Posts</h3>
<div class="widget">
<ul>
<li>
<a href="/2018/11/04/something-about-bipartite-graph/">Something About Bipartite Graph</a>
</li>
<li>
<a href="/2018/10/14/fractional-programming-and-dinkelbach-theorem/">Fractional programming & Dinkelbach theorem</a>
</li>
<li>
<a href="/2018/09/27/connectivity-and-tarjan-algorithm/">Connectivity & Tarjan Algorithm</a>
</li>
<li>
<a href="/2018/07/15/minimum-cut-problems/">Minimum Cut Problems</a>
</li>
<li>
<a href="/2018/07/08/cf-992E/">Codeforces 992E - Nastya and King-Shamans</a>
</li>
</ul>
</div>
</div>
</aside>
</div>
<footer id="footer">
<div class="outer">
<div id="footer-info" class="inner">
© 2018 Cao Li<br>
Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
</div>
</div>
</footer>
</div>
<nav id="mobile-nav">
<a href="/" class="mobile-nav-link">Home</a>
<a href="/archives" class="mobile-nav-link">Archives</a>
</nav>
<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>
<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
<script src="/fancybox/jquery.fancybox.pack.js"></script>
<script src="/js/script.js"></script>
</div>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
inlineMath: [ ["$","$"], ["\\(","\\)"] ],
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
processEscapes: true
}
});
MathJax.Hub.Queue(function() {
var all = MathJax.Hub.getAllJax();
for (var i = 0; i < all.length; ++i)
all[i].SourceElement().parentNode.className += ' has-jax';
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script src="/node_modules/live2d-widget/node_modules/live2d-widget/lib/L2Dwidget.min.js?0c58a1486de42ac6cc1c59c7d98ae887"></script><script>L2Dwidget.init({"pluginRootPath":"node_modules/live2d-widget/","pluginJsPath":"node_modules/live2d-widget/lib/","pluginModelPath":"node_modules/live2d-widget-model-hijiki/assets","model":{"scale":1,"hHeadPos":0.5,"vHeadPos":0.618,"jsonPath":"/node_modules/live2d-widget/node_modules/live2d-widget-model-hijiki/hijiki.model.json"},"display":{"superSample":2,"width":150,"height":300,"position":"right","hOffset":0,"vOffset":-20},"mobile":{"show":true,"scale":0.5},"react":{"opacityDefault":0.7,"opacityOnHover":0.2}});</script><!-- hexo-inject:begin --><!-- hexo-inject:end --></body>
</html>