-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathusaco.html
206 lines (169 loc) · 15.7 KB
/
usaco.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
<!DOCTYPE html>
<head>
<meta charset="utf-8" />
<!-- Set the viewport width to device width for mobile -->
<meta name="viewport" content="width=device-width" />
<title>Programming Journey - USACO</title>
<link rel="stylesheet" href="http://hsiangholin.github.io/blog/theme/css/normalize.css" />
<link rel="stylesheet" href="http://hsiangholin.github.io/blog/theme/css/foundation.min.css" />
<link rel="stylesheet" href="http://hsiangholin.github.io/blog/theme/css/style.css" />
<link rel="stylesheet" href="http://hsiangholin.github.io/blog/theme/css/pygments.css" />
<script src="http://hsiangholin.github.io/blog/theme/js/custom.modernizr.js"></script>
</head>
<body>
<!-- Nav Bar -->
<nav>
<div class="top-bar">
<div class="row">
<div class="large-9 large-centered columns">
<h1><a href="http://hsiangholin.github.io/blog">Programming Journey</a></h1>
</div>
</div>
</div>
<!-- Show menu items and pages -->
<div class="row">
<div class="large-9 columns">
<ul class="button-group navigation">
</ul>
</div>
</div>
</nav>
<!-- End Nav -->
<!-- Main Page Content and Sidebar -->
<div class="row">
<!-- Main Blog Content -->
<div class="large-9 columns">
<article>
<a href="http://hsiangholin.github.io/blog/posts/2013/11/usaco-broken-necklace.html"><h3 class="article-title">USACO Section 1.1 Broken Necklace</h3></a>
<h6 class="subheader" title="2013-11-30T14:42:00">Sat 30 November 2013
</h6>
<h3>The Problem</h3>
<p>Let's describe the problem briefly here. Given a string a necklace composed with Red, Blue and White beans, we are going to find the maximum number of beans we can collected if we can choose to break the necklace at a certain point. By "maximum number of beans we can collected", I mean starting from the break point, we collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end.</p>
<p>What's special is that when collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color.</p>
<h3>The Solution</h3>
<p>At first I think I can just use the simple-minded approach which is to try to break the necklace at each point and calculate how much beans I can get at that certain point. When this is done from start to end, we are able to obtain the maximum number of beans we can collected.</p>
<p>However, I have a feeling that a dynamic programming algorithm would be much more challenging and fun. So this is my approach of dynamic programming.
The main idea here is to iterate the ring once and we can dynamically sum up the numbers of last two same color collections. Finally, the maximum of the sums is the answer.</p>
<p>We are going to duplicated the necklace string and concatenate one to the other. For instance, if the necklace is rbwwrbbb, it will be made rbwwrbbbrbwwrbbb. The reason for this is that necklace is actually a ring, not a list. By doing this, we provide the illusion for the program that we are iterating in the ring.</p>
<p>Supposing we only have red and blue beans, while iterating the string from head to tail, we accumulate beans with same color, and if we have encountered a different color from what we are collecting now (let's call it a "color change"), we will store the current number of same color beans and start accumulate beans with the other color. In the meanwhile of "color change", we are going to sum up the past two numbers of different color beans collection, and compare it to the maximum number, if the sum is greater, replace the maximum number with the sum.</p>
<p>For instance, when we encounter the 5th bean "r" in rrbbrrrb, we have already stored the number of first 2 "r"s, 2, and the 3rd and 4th beans "b"s, 2, so now we got 2+2=4 to be our maximum. If we encounter the 8th bean "b", this "color change" yields sum=2+3=5, and replace maximum with 5.</p>
<p>Things got more complicated when white color joins. When we are iterating on "w" beans, we add the count to the current collection, assuming we are coloring these "w" beans to the color we are collecting. But when we encounters a "color change" (rw...b or bw...r), after maximum is compared to the sum, we are going the color the before collected white beans into the new color, maximizing the next collection.</p>
<p>For instance, brwwwbr will be viewed as brrrrbr when we are at the 5th bean, but it becomes brbbbbr when we get to the 6th bean.</p>
<h3>Conclusion</h3>
<p>By sticking to the above three principles, we can dynamically sum up the numbers of last two same color collections, which can find the answer in O(n).</p>
<h3>Source Code</h3>
<div class="highlight"><pre><span class="cp">#include <stdio.h> </span>
<span class="cp">#define BUF_SIZE 1024 </span>
<span class="kt">int</span> <span class="nf">main</span> <span class="p">()</span> <span class="p">{</span>
<span class="kt">FILE</span> <span class="n">fin</span> <span class="o">=</span> <span class="n">fopen</span> <span class="p">(</span><span class="s">"beads.in"</span><span class="p">,</span> <span class="s">"r"</span><span class="p">);</span>
<span class="kt">FILE</span> <span class="n">fout</span> <span class="o">=</span> <span class="n">fopen</span> <span class="p">(</span><span class="s">"beads.out"</span><span class="p">,</span> <span class="s">"w"</span><span class="p">);</span>
<span class="kt">int</span> <span class="n">size</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">it_len</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">i</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">state</span> <span class="o">=</span> <span class="mi">3</span><span class="p">;</span>
<span class="kt">char</span> <span class="n">beads</span><span class="p">[</span><span class="n">BUF_SIZE</span><span class="p">];</span>
<span class="kt">int</span> <span class="n">answer</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">sum1</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">sum2</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">w_combo</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">w_walk</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="k">if</span><span class="p">(</span><span class="n">fin</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">fscanf</span><span class="p">(</span><span class="n">fin</span><span class="p">,</span> <span class="s">"%d</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="o">&</span><span class="n">size</span><span class="p">);</span>
<span class="n">fgets</span><span class="p">(</span><span class="n">beads</span><span class="p">,</span> <span class="n">BUF_SIZE</span><span class="p">,</span> <span class="n">fin</span><span class="p">);</span>
<span class="n">it_len</span> <span class="o">=</span> <span class="n">size</span> <span class="o">*</span> <span class="mi">2</span><span class="p">;</span>
<span class="n">memcpy</span><span class="p">(</span><span class="o">&</span><span class="n">beads</span><span class="p">[</span><span class="n">size</span><span class="p">],</span><span class="o">&</span><span class="n">beads</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span><span class="n">size</span><span class="p">);</span>
<span class="k">for</span><span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">it_len</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">if</span><span class="p">(</span><span class="n">beads</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'r'</span> <span class="o">||</span> <span class="n">beads</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'b'</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">sum2</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
<span class="n">i</span><span class="o">++</span><span class="p">;</span>
<span class="k">break</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">sum2</span> <span class="o">=</span> <span class="n">size</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">for</span><span class="p">(;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">it_len</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">if</span><span class="p">(</span><span class="n">beads</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'w'</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">w_walk</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
<span class="n">w_combo</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
<span class="n">sum2</span><span class="o">++</span><span class="p">;</span>
<span class="n">beads</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">beads</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span>
<span class="p">}</span>
<span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">beads</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">beads</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">])</span>
<span class="p">{</span>
<span class="n">sum2</span><span class="o">++</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">else</span>
<span class="p">{</span>
<span class="k">if</span><span class="p">((</span><span class="n">sum1</span><span class="o">+</span><span class="n">sum2</span><span class="p">)</span> <span class="o">></span> <span class="n">answer</span><span class="p">)</span>
<span class="n">answer</span> <span class="o">=</span> <span class="n">sum1</span><span class="o">+</span><span class="n">sum2</span><span class="p">;</span>
<span class="n">sum1</span> <span class="o">=</span> <span class="n">sum2</span><span class="p">;</span>
<span class="n">sum2</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
<span class="k">if</span><span class="p">(</span><span class="n">w_walk</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">sum2</span> <span class="o">+=</span> <span class="n">w_combo</span><span class="p">;</span>
<span class="n">sum1</span> <span class="o">-=</span> <span class="n">w_combo</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">w_walk</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="n">w_combo</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="k">if</span><span class="p">((</span><span class="n">sum1</span><span class="o">+</span><span class="n">sum2</span><span class="p">)</span> <span class="o">></span> <span class="n">answer</span><span class="p">)</span>
<span class="n">answer</span> <span class="o">=</span> <span class="n">sum1</span><span class="o">+</span><span class="n">sum2</span><span class="p">;</span>
<span class="k">if</span><span class="p">(</span><span class="n">answer</span> <span class="o">></span> <span class="n">size</span><span class="p">)</span>
<span class="n">answer</span> <span class="o">=</span> <span class="n">size</span><span class="p">;</span>
<span class="k">if</span><span class="p">(</span><span class="n">fout</span><span class="p">)</span>
<span class="n">fprintf</span> <span class="p">(</span><span class="n">fout</span><span class="p">,</span> <span class="s">"%d</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">answer</span><span class="p">);</span>
<span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
</pre></div>
<p>}</p><p class="subheader">Category: <a href="http://hsiangholin.github.io/blog/category/algorithm.html">Algorithm</a>
Tagged:
<a href="http://hsiangholin.github.io/blog/tag/c.html">C </a>
<a href="http://hsiangholin.github.io/blog/tag/usaco.html">USACO </a>
<a href="http://hsiangholin.github.io/blog/tag/algorithm.html">Algorithm </a>
</p>
<p><a href="http://hsiangholin.github.io/blog/posts/2013/11/usaco-broken-necklace.html#disqus_thread">comments</a></p> </article>
<div class="pagination-centered">
<h6 class="subheader">Page 1 of 1</h6>
<p>
</p>
</div>
<!-- /#posts-list -->
</div>
<!-- End Main Content -->
<!-- Sidebar -->
<aside class="large-3 columns">
<h5 class="sidebar-title">Site</h5>
<ul class="side-nav">
<li><a href="http://hsiangholin.github.io/blog/archives.html">Archives</a>
<li><a href="http://hsiangholin.github.io/blog/tags.html">Tags</a>
</ul>
<h5 class="sidebar-title">Categories</h5>
<ul class="side-nav">
<li><a href="http://hsiangholin.github.io/blog/category/misc.html">MISC</a></li>
<li><a href="http://hsiangholin.github.io/blog/category/c-language.html">C Language</a></li>
<li><a href="http://hsiangholin.github.io/blog/category/algorithm.html">Algorithm</a></li>
<li><a href="http://hsiangholin.github.io/blog/category/about.html">About</a></li>
</ul>
<h5 class="sidebar-title">Links</h5>
<ul class="side-nav">
<li><a href="http://github.com">Github</a></li>
<li><a href="http://www.ntu.edu.tw">National Taiwan University</a></li>
</ul>
</aside> <!-- End Sidebar -->
</div> <!-- End Main Content and Sidebar -->
<!-- Footer -->
<footer class="row">
<div class="large-12 columns">
<hr />
<div class="row">
<div class="large-6 columns">
<p>Programming Journey by Hsiang-Ho Lin</p>
</div>
</div>
</div>
</footer>