CINXE.COM

<!doctype html><html lang="en" data-mode="light"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><meta name="theme-color" media="(prefers-color-scheme: light)" content="#f7f7f7"><meta name="theme-color" media="(prefers-color-scheme: dark)" content="#1b1b1e"><meta name="apple-mobile-web-app-capable" content="yes"><meta name="apple-mobile-web-app-status-bar-style" content="black-translucent"><meta name="viewport" content="width=device-width, user-scalable=no initial-scale=1, shrink-to-fit=no, viewport-fit=cover" ><meta name="generator" content="Jekyll v4.4.1" /><meta property="og:title" content="VProg Intro : Week 1, Introduction - Solutions" /><meta property="og:locale" content="en" /><meta name="description" content="HW1: Present from Lena" /><meta property="og:description" content="HW1: Present from Lena" /><link rel="canonical" href="https://vprog.hu/posts/2024-09-20-intro-week-1-solutions/" /><meta property="og:url" content="https://vprog.hu/posts/2024-09-20-intro-week-1-solutions/" /><meta property="og:site_name" content="VProg" /><meta property="og:type" content="article" /><meta property="article:published_time" content="2024-09-20T11:00:00+02:00" /><meta name="twitter:card" content="summary" /><meta property="twitter:title" content="VProg Intro : Week 1, Introduction - Solutions" /> <script type="application/ld+json"> {"@context":"https://schema.org","@type":"BlogPosting","dateModified":"2024-09-20T11:00:00+02:00","datePublished":"2024-09-20T11:00:00+02:00","description":"HW1: Present from Lena","headline":"VProg Intro : Week 1, Introduction - Solutions","mainEntityOfPage":{"@type":"WebPage","@id":"https://vprog.hu/posts/2024-09-20-intro-week-1-solutions/"},"url":"https://vprog.hu/posts/2024-09-20-intro-week-1-solutions/"}</script><title>VProg Intro : Week 1, Introduction - Solutions | VProg</title><link rel="apple-touch-icon" sizes="180x180" href="/assets/img/favicons/apple-touch-icon.png"><link rel="icon" type="image/png" sizes="32x32" href="/assets/img/favicons/favicon-32x32.png"><link rel="icon" type="image/png" sizes="16x16" href="/assets/img/favicons/favicon-16x16.png"><link rel="manifest" href="/assets/img/favicons/site.webmanifest"><link rel="shortcut icon" href="/assets/img/favicons/favicon.ico"><meta name="apple-mobile-web-app-title" content="VProg"><meta name="application-name" content="VProg"><meta name="msapplication-TileColor" content="#da532c"><meta name="msapplication-config" content="/assets/img/favicons/browserconfig.xml"><meta name="theme-color" content="#ffffff"><link rel="preconnect" href="https://fonts.googleapis.com" ><link rel="dns-prefetch" href="https://fonts.googleapis.com" ><link rel="preconnect" href="https://fonts.gstatic.com" crossorigin><link rel="dns-prefetch" href="https://fonts.gstatic.com" crossorigin><link rel="preconnect" href="https://fonts.googleapis.com" ><link rel="dns-prefetch" href="https://fonts.googleapis.com" ><link rel="preconnect" href="https://cdn.jsdelivr.net" ><link rel="dns-prefetch" href="https://cdn.jsdelivr.net" ><link rel="stylesheet" href="https://fonts.googleapis.com/css2?family=Lato&family=Source+Sans+Pro:wght@400;600;700;900&display=swap"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@5.3.2/dist/css/bootstrap.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@6.4.2/css/all.min.css"><link rel="stylesheet" href="/assets/css/jekyll-theme-chirpy.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/tocbot@4.21.1/dist/tocbot.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/loading-attribute-polyfill@2.1.1/dist/loading-attribute-polyfill.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/magnific-popup@1.1.0/dist/magnific-popup.min.css"><body><aside aria-label="Sidebar" id="sidebar" class="d-flex flex-column align-items-end"><header class="profile-wrapper"> <a href="/" style="display:block"> <img src="/assets/img/balloons-cartoon.png" width="100%" alt="avatar" onerror="this.style.display='none'"> </a><h1 class="site-title"> <a href="/">VProg</a></h1>Competitive programming student club at BME. ICPC, Codeforces, LeetCode, etc.<div class="sidebar-social d-flex flex-wrap align-items-center w-100 gap-2"> <a href="https://vprog.hu/discord" aria-label="discord" target="_blank" rel="noopener noreferrer" > </a> <a href="https://github.com/bmevprog" aria-label="github" target="_blank" rel="noopener noreferrer" > </a> <a href="https://www.youtube.com/@bmevprog" aria-label="youtube" target="_blank" rel="noopener noreferrer" > </a> <a href="https://www.facebook.com/bmevprog" aria-label="facebook" target="_blank" rel="noopener noreferrer" > </a> <a href="https://www.instagram.com/bmevprog" aria-label="instagram" target="_blank" rel="noopener noreferrer" > </a> <a href="https://www.twitter.com/bmevprog" aria-label="twitter" target="_blank" rel="noopener noreferrer" > </a> <a href="https://www.linkedin.com/company/bmevprog" aria-label="linkedin" target="_blank" rel="noopener noreferrer" > </a> <a href="https://www.tiktok.com/@bmevprog" aria-label="tiktok" target="_blank" rel="noopener noreferrer" > </a></div></header><nav class="flex-column flex-grow-1 w-100 ps-0"><ul class="nav"><li class="nav-item"> <a href="/" class="nav-link"> HOME </a><li class="nav-item"> <a href="/join/" class="nav-link"> JOIN </a><li class="nav-item"> <a href="/calendar/" class="nav-link"> CALENDAR </a><li class="nav-item"> <a href="/archives/" class="nav-link"> ARCHIVES </a><li class="nav-item"> <a href="/categories/" class="nav-link"> CATEGORIES </a><li class="nav-item"> <a href="/tags/" class="nav-link"> TAGS </a><li class="nav-item"> <a href="/rss/" class="nav-link"> RSS </a><li class="nav-item"> <a href="/contact/" class="nav-link"> CONTACT </a></ul></nav></aside><div id="main-wrapper" class="d-flex justify-content-center"><div class="container d-flex flex-column px-xxl-5"><header id="topbar-wrapper" aria-label="Top Bar"><div id="topbar" class="d-flex align-items-center justify-content-between px-lg-3 h-100" ><nav id="breadcrumb" aria-label="Breadcrumb"> <a href="/"> Home </a> VProg Intro : Week 1, Introduction - Solutions</nav><button type="button" id="sidebar-trigger" class="btn btn-link"> </button><div id="topbar-title"> Post</div><button type="button" id="search-trigger" class="btn btn-link"> </button> <search class="align-items-center ms-3 ms-lg-0"> <input class="form-control" id="search-input" type="search" aria-label="search" autocomplete="off" placeholder="Search..." > </search> <button type="button" class="btn btn-link text-decoration-none" id="search-cancel">Cancel</button></div></header><div class="row flex-grow-1"><main aria-label="Main Content" class="col-12 col-lg-11 col-xl-9 px-md-4"><article class="px-1"><header><h1 data-toc-skip>VProg Intro : Week 1, Introduction - Solutions</h1><div class="post-meta text-muted"> Posted <time data-ts="1726822800" data-df="ll" data-bs-toggle="tooltip" data-bs-placement="bottom" > Sep 20, 2024 </time> <div class="d-flex justify-content-between"> By Levente Gegő , <a href="https://cs.bme.hu/~nemkin">Viktória Nemkin</a> 10 min read</div></div></header><div class="content"><h2 id="hw1-present-from-lena">HW1: Present from Lena<a href="#hw1-present-from-lena" class="anchor text-muted"></a></h2><a href="https://codeforces.com/contest/118/problem/B">CF 118B</a>There are many ways you can come up with code for this.In this example, we calculate the following way:<ul><li>Iterate each cell position in the $(2n+1) \times (2n+1)$ grid.<li>For cell $(i,j)$, calculate its <a href="https://en.wikipedia.org/wiki/Taxicab_geometry">Manhattan-distance</a> from the center cell $(n,n)$, via $\vert n-i \vert + \vert n-j \vert$.<li>This distance determines the number placed in the cell, $x = n - \vert n-i \vert - \vert n-j \vert$.<li>When $x$ would be negative, we print a space instead.<li>Don’t forget to print all whitespaces in-between.</ul><div class="language-cpp highlighter-rouge"><div class="code-header"> <button aria-label="copy" data-title-succeed="Copied!"></button></div><div class="highlight"><code><table class="rouge-table"><tbody><tr><td class="rouge-gutter gl"><pre class="lineno">1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 </pre><td class="rouge-code"><pre>#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; int size = n * 2 + 1; for(int i = 0; i < size; ++i) { for(int j = 0; j < size; ++j) { int x = n - abs(n - i) - abs(n - j); if(x >= 0) { cout << x; if(j < n || x != 0) cout << " "; } else if(j < n) cout << " "; } cout << endl; } } </pre></table></code></div></div><h2 id="hw2-chat-room">HW2: Chat room<a href="#hw2-chat-room" class="anchor text-muted"></a></h2><a href="https://codeforces.com/contest/58/problem/A">CF58A</a>We can do a simple greedy algorithm: Iterate Vasya’s message and when we find the next matching character from the word “hello”, we mark it as done.<div class="language-cpp highlighter-rouge"><div class="code-header"> <button aria-label="copy" data-title-succeed="Copied!"></button></div><div class="highlight"><code><table class="rouge-table"><tbody><tr><td class="rouge-gutter gl"><pre class="lineno">1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 </pre><td class="rouge-code"><pre>#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; string hello = "hello"; int i = 0; for(char c : s) { if(i < hello.size() && c == hello[i]) ++i; } cout << (i == hello.size() ? "YES" : "NO") << endl; return 0; } </pre></table></code></div></div>Although we can see intuitively that this code is correct, for more complex greedy solutions, it might be good to know how to reason about their correctness with our teammates.In this case we can formulate a so-called “Greedy Stays Ahead” argument.If Vasya’s message contains the word “hello” as a substring, let’s say at indices $f_1, f_2, f_3, f_4$ and $f_5$, then the greedy algorithm will find a character ‘h’ at a position $g_1 \leq f_1 < f_2$.Then, when looking for the character ‘e’, it will start checking from position $g_1+1 \leq f_2$, therefore it will find one at $g_2 \leq f_2$.And so on…If Vasya’s message does not contain the word “hello”, this algorithm will return “NO” as well.You can read more about corretness proofs for greedy algorithms <a href="https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/handouts/120%20Guide%20to%20Greedy%20Algorithms.pdf">here</a>.<h2 id="hw3-we-were-both-children">HW3: We Were Both Children<a href="#hw3-we-were-both-children" class="anchor text-muted"></a></h2><a href="https://codeforces.com/contest/1850/problem/F">CF 1850F</a>The naive solution to this algorithm would look something like this:We simply calculate for each coordinate how many frogs will land there eventually.<div class="language-cpp highlighter-rouge"><div class="code-header"> <button aria-label="copy" data-title-succeed="Copied!"></button></div><div class="highlight"><code><table class="rouge-table"><tbody><tr><td class="rouge-gutter gl"><pre class="lineno">1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 </pre><td class="rouge-code"><pre>#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while(t--) { int n; cin >> n; vector<int> s(n+1, 0); for(int i=0; i<n; ++i) { int x; cin >> x; for(int j=x; j<=n; j+=x) ++s[j]; } cout << *max_element(s.begin(), s.end()) << endl; } return 0; } </pre></table></code></div></div>However, this results in a time limit exceeded. We have $n$ frogs for the outer for-loop and each frog can hop at most $n$ times, in the inner for-loop, so our algorithm is $O(n^2)$.Roughly speaking, since $n \leq 2 \cdot 10^5$, an $O(n^2)$ algorithm would perform around $const \cdot 4 \cdot 10^{10}$ steps, however $10^7$ steps is roughly around $1$ second on these platforms, so we are way out of the 3 seconds/test case time limit stated in the exercise.Intuitively, the biggest problems are caused by having too many frogs with relatively short hop-lengths, since this code spends the most time processing those, hop-by-hop. So, if we process them together, this will cut back tremendously on the runtime.Therefore, we will count the frogs who have the same hop-length and process them together, like this:<div class="language-cpp highlighter-rouge"><div class="code-header"> <button aria-label="copy" data-title-succeed="Copied!"></button></div><div class="highlight"><code><table class="rouge-table"><tbody><tr><td class="rouge-gutter gl"><pre class="lineno">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 </pre><td class="rouge-code"><pre>#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while(t--) { int n; cin >> n; map<int, int> a; for(int i = 0; i < n; ++i) { int x; cin >> x; ++a[x]; } vector<int> s(n + 1, 0); for(auto x : a) { for(int i = x.first; i <= n; i += x.first) s[i] += x.second; } cout << *max_element(s.begin(), s.end()) << endl; } return 0; } </pre></table></code></div></div>Mathematically, we can argue, that now the internal for-loop, processing the frogs with hop length $x$, will execute $\lfloor \frac{n}{x} \rfloor$ number of times, which accounts for a total of $\sum\limits_{x=1}^{n} \lfloor \frac{n}{x} \rfloor$ steps.It is very useful to remember, that the sum of a harmonic sequence, $\sum\limits_{x=1}^{n}\frac{1}{x}$ is $O(log n)$. This is because we can upper-estimate each $\frac{1}{x}$ with the closest fraction that has a power of $2$, in the following way:<a href="/assets/posts/2024-09-20-intro-week-1-solutions/harmonic-sequence.jpg" class="popup img-link shimmer"><img src="/assets/posts/2024-09-20-intro-week-1-solutions/harmonic-sequence.jpg" alt="" loading="lazy"></a>With similar logic $\sum\limits_{x=1}^{n} \lfloor \frac{n}{x} \rfloor$ is then $O(n \log n)$.Using the same rough estimation as before, when $n \leq 2 \cdot 10^5$, then this algorithm runs in roughly $const \cdot 10^5 \cdot 5 \cdot \log_2(10)$ steps, which fits into the $3$ seconds time limit of the task.<h2 id="poor-pigs">Poor Pigs<a href="#poor-pigs" class="anchor text-muted"></a></h2><a href="https://leetcode.com/problems/poor-pigs/">LC 458</a>We can quickly see that $r = \lfloor\frac{\text{minutesToTest}}{\text{minutesToDie}}\rfloor$ is the number of testing rounds we have available to us and forget about the minute parameters altogether.When you have a task that is hard to solve, one trick you can do is to solve a simpler version of it first, then try to generalize that solution. In this case, let’s first think about what the solution is for $r = 1$.For $n$ buckets, how many pigs should we request, so that we can tell exactly which bucket is poisonous?<ul><li>For $n=1$, we don’t need any pigs.<li>For $n=2$, one pig suffices, since we give one bucket to the pig, if it dies, that was the poison, otherwise it was in the other bucket.<li>For $n=3$, one pig is not enough, but we can do with two, one bucket to each and not giving the third bucket to any of them.<li>For $n=4$, two pigs are enough, since we can give, let’s say the first bucket to both pigs, the second bucket to the first pig, the third bucket to the second pig and the fourth bucket to neither. In all cases, the pattern of dead pigs will tell us which was the correct bucket.</ul>You can think about the pigs as 0/1 bit strings: 0 represents a pig that didn’t die and 1 represents a pig that died. Then the outcome is a number in binary format, where each pig corresponds to a certain bit position. For $k$ pigs, let’s number these pigs/bit positions from $0$ to $k-1$. We will also number our buckets, from $0$ to $n-1$ and represent them as binary numbers: where they contain a one, we feed them to the corresponding pig. Then, we can read the number of the poisonous bucket from the resulting deaths.For example, for $n=8$:<ul><li>Bucket $0 = 000_{2}$: Don’t give this bucket to any pigs. If no pigs die, this has the poison.<li>Bucket $1 = 001_{2}$: Give this bucket to pig $0$. If only pig $0$ dies, this has the poison.<li>Bucket $2 = 010_{2}$: Give this bucket to pig $1$. If only pig $1$ dies, this has the poison.<li>Bucket $3 = 011_{2}$: Give this bucket to pig $0$ and $1$. If exactly pig $0$ and $1$ die, this has the poison.<li>Bucket $4 = 100_{2}$: Give this bucket to pig $1$. If only pig $1$ dies, this has the poison.<li>Bucket $5 = 101_{2}$: Give this bucket to pig $0$ and $2$. If exactly pig $0$ and $1$ die, this has the poison.<li>Bucket $6 = 110_{2}$: Give this bucket to pig $1$ and $2$. If exactly pig $0$ and $1$ die, this has the poison.<li>Bucket $7 = 111_{2}$: Give this bucket to all pigs. If all pigs die, this has the poison.</ul>We can see now, that for $r = 1$, we can succeed with $k = \lceil \log_2 n \rceil$ pigs, as that’s how many bit positions we need to represent $n$ different numbers in binary.Now, what do we do, when we have more than one round to test, how does this setup change?After the first round of testing, some pigs will stay alive, so we can use them for the next round. Each pig may only die in exactly one round. If we record our results, we may write down the number of the round that the pig died in, denoting with $0$ the pigs, that are still alive at the end.So this means that our resulting pattern is now an base-$(r+1)$ number and we can apply the same logic as before.For example:Let’s say we have $2$ rounds and $8$ buckets. For this, we will need $2$ pigs.Let’s index the buckets between $0$ and $7$, and convert them to base-$3$!<ul><li>Bucket $0 = 00_3$: Don’t give this bucket to any pigs.<li>Bucket $1 = 01_3$: Give this to pig $0$ in round $1$.<li>Bucket $2 = 02_3$: Give this to pig $0$ in round $2$.<li>Bucket $3 = 10_3$: Give this to pig $1$ in round $1$.<li>Bucket $4 = 11_3$: Give this to both pigs in the first round.<li>Bucket $5 = 12_3$: Give this to pig $1$ in round $1$ and pig $0$ in round $2$.<li>Bucket $6 = 20_3$: Give this to pig $1$ in round $2$.<li>Bucket $7 = 21_3$: Give this to pig $1$ in round $2$ and pig $0$ in round $1$.</ul>Since all patterns are different, we can tell from the result which was the poisonous bucket.Therefore, we can succeed using $k = \lceil \log_{r+1} n \rceil$ pigs in general.We currently don’t have a rigorous proof on the lower bound of this, but intuitively you can see that an argument similar to the <a href="https://zoo.cs.yale.edu/classes/cs201/topics/topic-sorting-lb.pdf">lower bound on comparison-based sorts</a> could be established.Finally, the code to calculate the formula above:<div class="language-cpp highlighter-rouge"><div class="code-header"> <button aria-label="copy" data-title-succeed="Copied!"></button></div><div class="highlight"><code><table class="rouge-table"><tbody><tr><td class="rouge-gutter gl"><pre class="lineno">1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 </pre><td class="rouge-code"><pre>class Solution { public: int poorPigs(int buckets, int minutesToDie, int minutesToTest) { int rounds=minutesToTest/minutesToDie; int pigs = 0; int maxbuckets = 1; while(maxbuckets < buckets) { maxbuckets *= (rounds + 1); ++pigs; } return pigs; } }; </pre></table></code></div></div>We did a linear search for the first exponent of $(r + 1)$ which is larger than or equal to $\text{buckets}$. This runs in logarithmic time relative to $n$, so it’s actually pretty fast.Note here, that although it may be compelling to use code similar to this instead, it results in a Wrong Answer:<div class="language-cpp highlighter-rouge"><div class="code-header"> <button aria-label="copy" data-title-succeed="Copied!"></button></div><div class="highlight"><code><table class="rouge-table"><tbody><tr><td class="rouge-gutter gl"><pre class="lineno">1 2 3 4 5 6 7 8 9 </pre><td class="rouge-code"><pre>class Solution { public: int poorPigs(int buckets, int minutesToDie, int minutesToTest) { int rounds = minutesToTest/minutesToDie; return ceil(log(buckets) / log(rounds+1)); } }; </pre></table></code></div></div>This is due to problems with floating point precision. For example, for <code class="language-plaintext highlighter-rouge">rounds=4</code> and <code class="language-plaintext highlighter-rouge">buckets=125</code>, the correct answer is $3$, but the resulting numbers are just slightly off.<div class="language-cpp highlighter-rouge"><div class="code-header"> <button aria-label="copy" data-title-succeed="Copied!"></button></div><div class="highlight"><code><table class="rouge-table"><tbody><tr><td class="rouge-gutter gl"><pre class="lineno">1 2 3 </pre><td class="rouge-code"><pre>log(buckets) = 4.82831373730230151153364204219542443752288818359375 log(rounds+1) = 1.6094379124341002817999424223671667277812957763671875 result = 3.000000000000000444089209850062616169452667236328125 </pre></table></code></div></div>I bet the testcases were designed intentionally to fail this type of submission.Although we can employ tricks like substracting some $\varepsilon$ value before the ceil is applied, but a good rule of thumb for competitive programming is to avoid floating point numbers at all costs, so it is best to stick with the integer-only solutions whenever we can.</div><div class="post-tail-wrapper text-muted pt-5"><div class="post-meta"> <a href="/categories/vprog-intro/">vprog-intro</a></div><div class="post-tail-bottom d-flex justify-content-between align-items-center mt-2 pb-2"><div class="post-tags"> <a href="/tags/vprog-intro/" class="post-tag no-text-decoration" >vprog-intro</a> <a href="/tags/implementation/" class="post-tag no-text-decoration" >implementation</a> <a href="/tags/solutions/" class="post-tag no-text-decoration" >solutions</a></div><div class="share-wrapper d-flex align-items-center"> Share <a href="https://www.facebook.com/sharer/sharer.php?title=VProg%20Intro%20:%20Week%201,%20Introduction%20-%20Solutions%20-%20VProg&u=https%3A%2F%2Fvprog.hu%2Fposts%2F2024-09-20-intro-week-1-solutions%2F" data-bs-toggle="tooltip" data-bs-placement="top" title="Facebook" target="_blank" rel="noopener" aria-label="Facebook" > </a> <a href="https://twitter.com/intent/tweet?text=VProg%20Intro%20:%20Week%201,%20Introduction%20-%20Solutions%20-%20VProg&url=https%3A%2F%2Fvprog.hu%2Fposts%2F2024-09-20-intro-week-1-solutions%2F" data-bs-toggle="tooltip" data-bs-placement="top" title="Twitter" target="_blank" rel="noopener" aria-label="Twitter" > </a> <a href="https://www.linkedin.com/sharing/share-offsite/?url=https%3A%2F%2Fvprog.hu%2Fposts%2F2024-09-20-intro-week-1-solutions%2F" data-bs-toggle="tooltip" data-bs-placement="top" title="Linkedin" target="_blank" rel="noopener" aria-label="Linkedin" > </a> <button id="copy-link" aria-label="Copy link" class="btn small" data-bs-toggle="tooltip" data-bs-placement="top" title="Copy link" data-title-succeed="Link copied successfully!" > </button> </div></div></div></article></main><aside aria-label="Panel" id="panel-wrapper" class="col-xl-3 ps-2 mb-5 text-muted"><div class="access"><section><h2 class="panel-heading">Trending Tags</h2><div class="d-flex flex-wrap mt-3 mb-1 me-3"> <a class="post-tag btn btn-outline-primary" href="/tags/vprog/">vprog</a> <a class="post-tag btn btn-outline-primary" href="/tags/vprog-intro/">vprog-intro</a> <a class="post-tag btn btn-outline-primary" href="/tags/starting/">starting</a> <a class="post-tag btn btn-outline-primary" href="/tags/solutions/">solutions</a> <a class="post-tag btn btn-outline-primary" href="/tags/video/">video</a> <a class="post-tag btn btn-outline-primary" href="/tags/binsearch/">binsearch</a> <a class="post-tag btn btn-outline-primary" href="/tags/codeforces/">codeforces</a> <a class="post-tag btn btn-outline-primary" href="/tags/twoptr/">twoptr</a> <a class="post-tag btn btn-outline-primary" href="/tags/codejam/">codejam</a> <a class="post-tag btn btn-outline-primary" href="/tags/dfs/">dfs</a></div></section></div><section id="toc-wrapper" class="ps-0 pe-4"><h2 class="panel-heading ps-3 pt-2 mb-2">Contents</h2><nav id="toc"></nav></section></aside></div><div class="row"><div id="tail-wrapper" class="col-12 col-lg-11 col-xl-9 px-md-4"><aside id="related-posts" aria-labelledby="related-label"><h3 class="mb-4" id="related-label">Further Reading</h3><nav class="row row-cols-1 row-cols-md-2 row-cols-xl-3 g-4 mb-4"><article class="col"> <a href="/posts/2024-10-11-intro-week-2-solutions/" class="post-preview card h-100"><div class="card-body"> <time class="small" data-ts="1728676800" data-df="ll" > Oct 11, 2024 </time><h4 class="pt-0 my-2">VProg Intro : Week 2, Two Pointers - Solutions</h4><div class="text-muted small"> HW1: 3SUM LC 15 This exercise is similar to the TwoSum one in the video. We iterate the input vector, checking all possible candidates for the first number of the three. Inside the loop we do th...</div></div></a></article><article class="col"> <a href="/posts/2024-10-12-intro-week-3-solutions/" class="post-preview card h-100"><div class="card-body"> <time class="small" data-ts="1728741600" data-df="ll" > Oct 12, 2024 </time><h4 class="pt-0 my-2">VProg Intro : Week 3, Binary Search - Solutions</h4><div class="text-muted small"> HW1: Successful Pairs of Spells and Potions LC 2300 For each spell, we are looking for the number of potions that will form a successful pair with it. We can first order the potions by increasing...</div></div></a></article><article class="col"> <a href="/posts/2024-09-09-vprog-start/" class="post-preview card h-100"><div class="card-body"> <time class="small" data-ts="1725881700" data-df="ll" > Sep 9, 2024 </time><h4 class="pt-0 my-2">VProg Intro : Week 1, Introduction + VProg Advanced Student Club</h4><div class="text-muted small"> The VProg competitive programming study groups are continued this semester, organized by BME VIK SZIT! Join us on Discord: https://vprog.hu/discord VProg Intro Aimed at 2nd year software enginee...</div></div></a></article></nav></aside><nav class="post-navigation d-flex justify-content-between" aria-label="Post Navigation"> <a href="/posts/2024-09-09-vprog-start/" class="btn btn-outline-primary" aria-label="Older" >VProg Intro : Week 1, Introduction + VProg Advanced Student Club</a> <a href="/posts/2024-09-20-intro-week-2/" class="btn btn-outline-primary" aria-label="Newer" >VProg Intro : Week 2, Two Pointers</a></nav><footer aria-label="Site Info" class=" d-flex flex-column justify-content-center text-muted flex-lg-row justify-content-lg-between align-items-lg-center pb-lg-3 " >Using the <a href="https://github.com/cotes2020/jekyll-theme-chirpy" target="_blank" rel="noopener">Chirpy</a> theme for <a href="https://jekyllrb.com" target="_blank" rel="noopener">Jekyll</a>.</footer></div></div><div id="search-result-wrapper" class="d-flex justify-content-center unloaded"><div class="col-11 content"><div id="search-hints"><section><h2 class="panel-heading">Trending Tags</h2><div class="d-flex flex-wrap mt-3 mb-1 me-3"> <a class="post-tag btn btn-outline-primary" href="/tags/vprog/">vprog</a> <a class="post-tag btn btn-outline-primary" href="/tags/vprog-intro/">vprog-intro</a> <a class="post-tag btn btn-outline-primary" href="/tags/starting/">starting</a> <a class="post-tag btn btn-outline-primary" href="/tags/solutions/">solutions</a> <a class="post-tag btn btn-outline-primary" href="/tags/video/">video</a> <a class="post-tag btn btn-outline-primary" href="/tags/binsearch/">binsearch</a> <a class="post-tag btn btn-outline-primary" href="/tags/codeforces/">codeforces</a> <a class="post-tag btn btn-outline-primary" href="/tags/twoptr/">twoptr</a> <a class="post-tag btn btn-outline-primary" href="/tags/codejam/">codejam</a> <a class="post-tag btn btn-outline-primary" href="/tags/dfs/">dfs</a></div></section></div><div id="search-results" class="d-flex flex-wrap justify-content-center text-muted mt-3"></div></div></div></div><aside aria-label="Scroll to Top"> <button id="back-to-top" type="button" class="btn btn-lg btn-box-shadow"> </button></aside></div><div id="mask"></div><script src="https://cdn.jsdelivr.net/combine/npm/jquery@3.7.1/dist/jquery.min.js,npm/bootstrap@5.3.2/dist/js/bootstrap.bundle.min.js,npm/simple-jekyll-search@1.10.0/dest/simple-jekyll-search.min.js,npm/loading-attribute-polyfill@2.1.1/dist/loading-attribute-polyfill.umd.min.js,npm/magnific-popup@1.1.0/dist/jquery.magnific-popup.min.js,npm/clipboard@2.0.11/dist/clipboard.min.js,npm/dayjs@1.11.10/dayjs.min.js,npm/dayjs@1.11.10/locale/en.min.js,npm/dayjs@1.11.10/plugin/relativeTime.min.js,npm/dayjs@1.11.10/plugin/localizedFormat.min.js,npm/tocbot@4.21.1/dist/tocbot.min.js"></script> <script defer src="/assets/js/dist/post.min.js"></script> <script> /* see: <https://docs.mathjax.org/en/latest/options/input/tex.html#tex-options> */ MathJax = { tex: { /* start/end delimiter pairs for in-line math */ inlineMath: [ ['$', '$'], ['\$', '\$'] ], /* start/end delimiter pairs for display math */ displayMath: [ ['$$', '$$'], ['\\[', '\\]'] ] } }; </script> <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script> <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3.2.2/es5/tex-chtml.js"></script> <script defer src="/unregister.js"></script> <script> /* Note: dependent library will be loaded in `js-selector.html` */ SimpleJekyllSearch({ searchInput: document.getElementById('search-input'), resultsContainer: document.getElementById('search-results'), json: '/assets/js/data/search.json', searchResultTemplate: '<article class="px-1 px-sm-2 px-lg-4 px-xl-0"><header><h2><a href="{url}">{title}</a></h2><div class="post-meta d-flex flex-column flex-sm-row text-muted mt-1 mb-1"> {categories} {tags}</div></header>{snippet}</article>', noResultsText: '', templateMiddleware: function(prop, value, template) { if (prop === 'categories') { if (value === '') { return `${value}`; } else { return `<div class="me-sm-4">${value}</div>`; } } if (prop === 'tags') { if (value === '') { return `${value}`; } else { return `<div>${value}</div>`; } } } }); </script>