forked from CPHub-NITC/chapter
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlongMarch20.html
More file actions
371 lines (336 loc) · 15.5 KB
/
longMarch20.html
File metadata and controls
371 lines (336 loc) · 15.5 KB
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no" />
<meta name="description" content="" />
<meta name="author" content="" />
<title>Nitc Codechef Campus Chapter</title>
<!-- Bootstrap core CSS -->
<link href="vendor/bootstrap/css/bootstrap.min.css" rel="stylesheet" />
<!-- Custom fonts for this template -->
<link href="vendor/fontawesome-free/css/all.min.css" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Lora:400,700,400italic,700italic" rel="stylesheet"
type="text/css" />
<link
href="https://fonts.googleapis.com/css?family=Open+Sans:300italic,400italic,600italic,700italic,800italic,400,300,600,700,800"
rel="stylesheet" type="text/css" />
<!-- Custom styles for this template -->
<link href="css/clean-blog.min.css" rel="stylesheet" />
</head>
<body>
<!-- Navigation -->
<nav class="navbar navbar-expand-lg navbar-light fixed-top" id="mainNav">
<div class="container">
<a class="navbar-brand" href="index.html">NITC CCC</a>
<button class="navbar-toggler navbar-toggler-right" type="button" data-toggle="collapse"
data-target="#navbarResponsive" aria-controls="navbarResponsive" aria-expanded="false"
aria-label="Toggle navigation">
Menu
<i class="fas fa-bars"></i>
</button>
<div class="collapse navbar-collapse" id="navbarResponsive">
<ul class="navbar-nav ml-auto">
<li class="nav-item">
<a class="nav-link" href="index.html">Home</a>
</li>
<li class="nav-item">
<a class="nav-link" href="about.html">About</a>
</li>
<li class="nav-item">
<a class="nav-link" href="editorials.html">Editorials</a>
</li>
<li class="nav-item">
<a class="nav-link"
href="https://www.codechef.com/certification/data-structures-and-algorithms/prepare">RoadMap</a>
</li>
<li class="nav-item">
<a class="nav-link" href="contact.html">Contact</a>
</li>
<li class="nav-item">
<a class="nav-link" href="events.html">Events</a>
</li>
</ul>
</div>
</div>
</nav>
<!-- Page Header -->
<header class="masthead" style="background-image: url('img/post-bg.jpg')">
<div class="overlay"></div>
<div class="container">
<div class="row">
<div class="col-lg-8 col-md-10 mx-auto">
<div class="post-heading">
<h1>
Editorial to March Long Challenge 2020
</h1>
<!-- <h2 class="subheading">Problems look mighty small from 150 miles up</h2>
<span class="meta">Posted by
<a href="#">Start Bootstrap</a>
on August 24, 2019</span> -->
</div>
</div>
</div>
</div>
</header>
<!-- Post Content -->
<article>
<div class="container">
<a href="https://www.codechef.com/MARCH20B">Original Contest Link</a>
<h1>Table of content</h1>
<ul>
<li><a href="#CHPINTU">Pintu and Fruits (CHPINTU)</a></li>
<li><a href="#ENGXOR">XOR Engine (ENGXOR)</a></li>
<li><a href="#ADASHOP2">ADA BISHOP 2 (ADASHOP2)</a></li>
<li><a href="#LAZER">Lasers Everywhere (LAZER)</a></li>
<li><a href="#CHEFDAG">Chef and DAG (CHEFDAG)</a></li>
</ul>
<div id="CHPINTU" class="row">
<div class="col-lg-8 col-md-10 mx-auto">
<h2 class="section-heading">Pintu and Fruits CHPINTU</h2>
<p>
Original Problem Link:
<a href="https://www.codechef.com/MARCH20B/problems/CHPINTU">CHPINTU
</a>
</p>
<p>
Solution Author Name: Hritik Seth
<a href=" http://linkedin.com/in/hritik-seth-43395617a">linkedin link</a>
</p>
<p>
Prequisutes: Basics of array/list indexing and mathematics.
</p>
<p>
Explaination: Well the problem was quite easy.It only check your
basics in any programming language. It was based on the concept of
count array/list. We only have to count the minimum number of
basket cost required for the fruits. So I firstly subtracted 1
from every type of fruit and stored it in a list so that basket of
type 0 can be included while calculating then I store total cost
of the corresponding basket at the corresponding index. After the
cost is stored (index being the basket type), I finally find the
the basket type with minimal cost in the list and printed it.
</p>
<script src="https://gist.github.com/Shahraaz/9d21e4d9b6740c9f2d0fb92c188412f8.js"></script>
</div>
</div>
<div id="ENGXOR" class="row">
<div class="col-lg-8 col-md-10 mx-auto">
<h2 class="section-heading">XOR Engine</h2>
<p>
Original Problem Link:
<a href="https://www.codechef.com/MARCH20B/problems/ENGXOR">ENGXOR</a>
</p>
<p>
Solution Author Name: <a href="https://www.codechef.com/users/himanshushkl69">Himanshu
Shukla</a>
</p>
<p>
Prequisutes: Observation
</p>
<p>
Explaination: Observation <br />1. (EVEN number of bits NUMBER)
XOR (ODD number of bits NUMBER) = (ODD number of bits NUMBER)<br />
2. (ODD number of bits NUMBER) XOR (ODD number of bits NUMBER) =
(EVEN number of bits NUMBER)
<br />3. (EVEN number of bits NUMBER) XOR (EVEN number of bits
NUMBER) = (EVEN number of bits NUMBER)
</p>
<p>
Get initial count of even bit numbers(x) and odd bit numbers(y)
present in array.
<br />
When a query P comes check whether P is even bit number or odd bit
number, if P is even bit number print x and y else print y and x.
</p>
<script src="https://gist.github.com/himanshushkl691/e6169daa490918e87fcd83e9a3fb809b.js"></script>
</div>
</div>
<div id="ADASHOP2" class="row">
<div class="col-lg-8 col-md-10 mx-auto">
<h2 class="section-heading">ADA BISHOP 2</h2>
<p>
Original Problem Link:
<a href="https://www.codechef.com/MARCH20B/problems/ADASHOP2">ADASHOP2</a>
</p>
<p>
Solution Author Name: <a href="https://www.codechef.com/users/himanshushkl69">Himanshu
Shukla</a>
</p>
<p>
Prequisutes: Basic Graph Traversal Algorithm, Observation
</p>
<p>
Explaination: Well I have seen many programmers hardcoding
solution. Solution I am going to present is quite general and
works even with N X N chessboard with some modification to
solution presented below. Solution presented below is based on
graph traversal algorithm called DFS(Depth First Search).
</p>
<p>
Construct a graph which is not going to change with testcases,
(u,v) where u = (a,b), v = (c,d) is an undirected edge in graph if
u and v represents black cell and bishop can move from u to v and
from v to u beforehand. This can be constructed in O(N X N) time
for general N X N chessboard.
<br />
Whenever a query src = (r,c) comes keep a counter rem(here
initially rem = 32), perform a DFS considering src as root and
keep on pushing cells in ans array till rem becomes 0.
<br />
Finally print the ans array.
<br />
Main observation here is number of cell visited will not become
greater than 64 each cell is visited atmost twice and number of
black cell is 32 so number of cell visited is always less than
equal to 64 (loose upper bound).
</p>
<script src="https://gist.github.com/himanshushkl691/389ca68a4209fbdb7879290977cad1c4.js"></script>
</div>
</div>
<div id="LAZER" class="row">
<div class="col-lg-8 col-md-10 mx-auto">
<!-- <p>Never in all their history have men been able truly to conceive of the world as one: a single sphere, a globe, having the qualities of a globe, a round earth in which all the directions eventually meet, in which there is no center because every point, or none, is center — an equal earth which all men occupy as equals. The airman's earth, if free men make it, will be truly round: a globe in practice, not in theory.</p>
<p>Science cuts two ways, of course; its products can be used for both good and evil. But there's no turning back from science. The early warnings about technological dangers also come from science.</p>
<p>What was most significant about the lunar voyage was not that man set foot on the Moon but that they set eye on the earth.</p>
<p>A Chinese tale tells of some men sent to harm a young girl who, upon seeing her beauty, become her protectors rather than her violators. That's how I felt seeing the Earth for the first time. I could not help but love and cherish her.</p>
<p>For those who have seen the Earth from space, and for the hundreds and perhaps thousands more who will, the experience most certainly changes your perspective. The things that we share in our world are far more valuable than those which divide us.</p> -->
<h2 class="section-heading">Lasers Everywhere LAZER</h2>
<p>
Original Problem Link:
<a href="https://www.codechef.com/MARCH20B/problems/LAZER">LAZER</a>
</p>
<p>
Solution Author Name: <a href="https://www.codechef.com/users/shahraaz">Mohammed Shahraaz Hussain</a>
</p>
<p>
Prequisutes: Range Query Tree(Segment Tree or Fenwick Tree), Line
Sweep Algorithm intuition
</p>
<p>
Explaination: We can imagine Problem to be some set of adjacent
towers and wires connecting adjacent towers. Each tower has
different height.
</p>
<p>
When ever a query is asked you can assume that a light is to be
shot from x1 to x2 at height h. Which is pretty straight forward.
<br />
While processing a query what must be done? here we must be quite
strategic. here we need to process the queries offline.
</p>
<p>
now we need to think of lines as some structure. for each line we
define a start point, end point. Starting point is the point on
with higher y cordinate and end is the one with lower y cordinate.
if a line is horizontal we consider the left point as start point
and right point as end point.
</p>
<p>
Guess where we are headed! Split the line. Start point and end
Point.
</p>
<p>
Now we need to define some points as events points. These is where
we do some computaion for our queries. here start point, end point
and queries are the event points.
</p>
<p>
Now decide how to process the event points. In the mean while we
will define our event point staructre. First Observation We need
to process the event points from Top to Bottom by height. If the
events have same height we need to process start points first,
then queries and finally the end points.
</p>
<p>
When a start point is detected we add 1 at the left idx of the
line. When a end point is detected we substract 1 from left idx of
the line. when a query is detected we do a range query on the left
idx and right idx-1 of the query(Finally store then by their query
idx). If range query is done slowly we will fail. So we need to
use Segment Tree or Fenwick Tree(Link to refernce in the roadmap
section).
</p>
<script src="https://gist.github.com/Shahraaz/2152765d19fe71e7a853d9f3eea235e5.js"></script>
</div>
</div>
<div id="CHEFDAG" class="row">
<div class="col-lg-8 col-md-10 mx-auto">
<h2 class="section-heading">Chef and DAG</h2>
<p>
Original Problem Link:
<a href="https://www.codechef.com/MARCH20B/problems/CHEFDAG">CHEFDAG</a>
</p>
<p>
Solution Author Name: Written By: <a href="https://www.codechef.com/users/himanshushkl69">Himanshu
Shukla</a>
Credit: <a href="https://www.codechef.com/users/tmwilliamlin">William Lin</a>
</p>
<p>
Prequisutes: Minimum Path Cover on DAG, Maximum Bipartite Matching, Maximum Flow
</p>
<p>
<h1>Resources </h1><br />
<p>Link : <a href="https://towardsdatascience.com/solving-minimum-path-cover-on-a-dag-21b16ca11ac0">Minimum
Path Cover
on DAG</a></p><br /><br />
<iframe width="590" height="480" src="https://www.youtube.com/embed/K1i-wP82Zdo" frameborder="0"
allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture"
allowfullscreen></iframe><br />
<h1>Solution</h1><br />
<iframe width="590" height="480" src="https://www.youtube.com/embed/VR4YCGaFamc" frameborder="0"
allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
</p>
<p>Original Commented Code: <a href="https://www.codechef.com/viewsolution/30509361">tmwilliamlin's
Solution</a></p>
<script src="https://gist.github.com/himanshushkl691/202e46892d093e4d10e783bd7c16c191.js"></script>
</div>
</div>
</div>
</article>
<hr />
<!-- Footer -->
<footer>
<div class="container">
<div class="row">
<div class="col-lg-8 col-md-10 mx-auto">
<ul class="list-inline text-center">
<!-- <li class="list-inline-item">
<a href="#">
<span class="fa-stack fa-lg">
<i class="fas fa-circle fa-stack-2x"></i>
<i class="fab fa-twitter fa-stack-1x fa-inverse"></i>
</span>
</a>
</li> -->
<li class="list-inline-item">
<a href="#">
<span class="fa-stack fa-lg">
<i class="fas fa-circle fa-stack-2x"></i>
<i class="fab fa-facebook-f fa-stack-1x fa-inverse"></i>
</span>
</a>
</li>
<li class="list-inline-item">
<a href="#">
<span class="fa-stack fa-lg">
<i class="fas fa-circle fa-stack-2x"></i>
<i class="fab fa-github fa-stack-1x fa-inverse"></i>
</span>
</a>
</li>
</ul>
<p class="copyright text-muted">
Copyright © Shahraaz Hussain 2020
</p>
</div>
</div>
</div>
</footer>
<!-- Bootstrap core JavaScript -->
<script src="vendor/jquery/jquery.min.js"></script>
<script src="vendor/bootstrap/js/bootstrap.bundle.min.js"></script>
<!-- Custom scripts for this template -->
<script src="js/clean-blog.min.js"></script>
</body>
</html>