chapter/Chapter1.html at master · chesettitarun/chapter · GitHub

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
<!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>
                Selected Problems From Codechef Campus Chapter Contest 1
              </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/CHPTRS01?itm_campaign=contest_listing"
          >Original Contest Link</a
        >
        <h1>Table of content</h1>
        <ul>
          <li><a href="#ARTPNT">Save Us!</a></li>
        </ul>
        <div id="ARTPNT" class="row">
          <div class="col-lg-8 col-md-10 mx-auto">
            <h2 class="section-heading">Save Us ARTPNT</h2>
            <p>
              Original Problem Link:
              <a href="https://www.codechef.com/CHPTRS01/problems/ARTPNT"
                >ARTPNT
              </a>
            </p>

            <p>
              Author Name: Mohammed Shahraaz Hussain
              <a href=" http://linkedin.com/in/shahraaz">linkedin link</a>
            </p>

            <p>
              Prequisutes: Block Cut Tree and Dp on Trees.
            </p>

            <p>
              Explaination:
              <br />
              First, let us solve this for a tree. For the root, we check how
              many children subtrees are totally infection free and how many
              have at least one infected. If no child subtree has at least one
              infected we save the whole tree except the infected person.
              Otherwise, we save all subtree which is infection-free. By
              rerooting, we can solve this for the whole tree. And choose the
              best node.
              <br />
              <script src="https://gist.github.com/Shahraaz/a7868b54508b5ed4b36b0eadf23c2ffd.js"></script>
              <br />
              Now for a general graph, we can find the block cut tree (idea from
              here
              <a href="https://www.quora.com/q/threadsiiithyderabad/The-Bridge-Tree-of-a-graph">https://www.quora.com/q/threadsiiithyderabad/The-Bridge-Tree-of-a-graph</a>

              Code from <a href="https://ideone.com/hCUME3">https://ideone.com/hCUME3</a>  I edited it a bit).

              <br>
              Some picture of to give u an idea of what must be done
              <br>
              <a href="./artpnt.png">Original Graph</a>
              <br>
              <a href="./blockCutTree.png.png">Block Cut Tree</a>
              <br>
              Observation removing articulation points is the best. Each node in
              the block cut tree is a combination of multiple nodes in the input
              graph. We need to check if a node of the block cut tree represents
              only one node in the input graph, also check if that node is an
              articulation point in the original graph and finally check if the
              node is infected. If all the checks pass do some similar
              computation for the node and consider that node
            </p>
            <h3>Full Code Solution</h3>
            <script src="https://gist.github.com/Shahraaz/6440cedcfc9ab9bd0f168faa190a3a43.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 &copy; 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>