{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"challenge_problem_statement\"\u003e\u003cdiv class\u003d\"msB challenge_problem_statement_body\"\u003e\u003cdiv class\u003d\"hackdown-content\"\u003e\u003cstyle id\u003d\"MathJax_SVG_styles\"\u003e.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%}\n.MathJax_SVG .MJX-monospace {font-family: monospace}\n.MathJax_SVG .MJX-sans-serif {font-family: sans-serif}\n.MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0}\n.MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none}\n.mjx-svg-href {fill: blue; stroke: blue}\n\u003c/style\u003e\u003csvg style\u003d\"display: none;\"\u003e\u003cdefs id\u003d\"MathJax_SVG_glyphs\"\u003e\u003c/defs\u003e\u003c/svg\u003e\u003cp\u003e\u003cstrong\u003eUpdate:\u003c/strong\u003e A slight modification in the problem statement (see below) \u003c/p\u003e\n\n\u003cp\u003eEvil Nation A is angry and plans to launch \u003cstrong\u003eN\u003c/strong\u003e guided-missiles at the peaceful Nation B in an attempt to wipe out all of Nation B\u0027s people. Nation A\u0027s missile \u003cem\u003ei\u003c/em\u003e will arrive in nation B at time t\u003csub\u003ei\u003c/sub\u003e. Missile \u003cem\u003ei\u003c/em\u003e communicates with its headquarters by unique radio signals with a frequency equal to f\u003csub\u003ei\u003c/sub\u003e. Can you help the peaceful Nation B survive by building a defensive system that will stop the missiles dead in the sky?\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eDefensive system:\u003c/strong\u003e \u003c/p\u003e\n\n\u003cp\u003eThe only way to defend Nation B from the attacking missile is by counter attacking them with a \u003cem\u003ehackerX\u003c/em\u003e missile. You have a lot of \u003cem\u003ehackerX\u003c/em\u003e missiles and each one of them has its own radio frequency. An individual \u003cem\u003ehackerX\u003c/em\u003e missile can destroy Evil Nation A’s attacking missile if the radio frequency of both of the missiles match. Each \u003cem\u003ehackerX\u003c/em\u003e missile can be used an indefinite number of times. Its invincible and doesn\u0027t get destroyed in the collision.\u003c/p\u003e\n\n\u003cp\u003eThe good news is you can adjust the frequency of the \u003cem\u003ehackerX\u003c/em\u003e missile to match the evil missiles\u0027 frequency. When changing the \u003cem\u003ehackerX\u003c/em\u003e missile\u0027s initial frequency fA to the new defending frequency fB, you will need \\|fB - fA\\| units of time to do. \u003c/p\u003e\n\n\u003cp\u003e\u003cstrike\u003eEach \u003cem\u003ehackerX\u003c/em\u003e missile can only destroy one of Nation A\u0027s missile at a time. So if two evil missiles with same frequency arrive at the same time, you need at least two \u003cem\u003ehackerX\u003c/em\u003e missiles with the same frequency as the evil missiles to avoid damage.\u003c/strike\u003e \u003c/p\u003e\n\n\u003cp\u003eIf two evil missles with same frequency arrive at the same time, we can destroy them both with one \u003cem\u003ehackerX\u003c/em\u003e missile. You can set the frequency of a \u003cem\u003ehackerX\u003c/em\u003e missile to any value when its fired. \u003c/p\u003e\n\n\u003cp\u003eWhat is the minimum number of \u003cem\u003ehackerX\u003c/em\u003e missiles you must launch to keep Nation B safe?\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eInput Format:\u003c/strong\u003e \u003cbr\u003e\nThe first line contains a single integer \u003cstrong\u003eN\u003c/strong\u003e denoting the number of missiles. \u003cbr\u003e\nThis is followed by \u003cstrong\u003eN\u003c/strong\u003e lines each containing two integers t\u003csub\u003ei\u003c/sub\u003e and f\u003csub\u003ei\u003c/sub\u003e denoting the time \u0026amp; frequency of the i\u003csup\u003eth\u003c/sup\u003e missile.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eOutput Format:\u003c/strong\u003e \u003cbr\u003e\nA single integer denoting the minimum number of \u003cem\u003ehackerX\u003c/em\u003e missiles you need to defend the nation.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eConstraints:\u003c/strong\u003e \u003cbr\u003e\n1 \u0026lt;\u003d N \u0026lt;\u003d 100000 \u003cbr\u003e\n0 \u0026lt;\u003d t\u003csub\u003ei\u003c/sub\u003e \u0026lt;\u003d 100000 \u003cbr\u003e\n0 \u0026lt;\u003d f\u003csub\u003ei\u003c/sub\u003e \u0026lt;\u003d 100000 \u003cbr\u003e\nt\u003csub\u003e1\u003c/sub\u003e \u0026lt;\u003d t\u003csub\u003e2\u003c/sub\u003e \u0026lt;\u003d ... \u0026lt;\u003d t\u003csub\u003eN\u003c/sub\u003e \u003c/p\u003e\n\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n1 1\n2 2\n3 1\n5 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\n\n\n\n\n\n\n\u003cp\u003e\u003cstrong\u003eExplanation #00\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003eA \u003cem\u003eHackerX\u003c/em\u003e missile is launched at t \u003d 1 with a frequency f \u003d 1, and destroys the first missile. It re-tunes its frequency to f \u003d 2 in 1 unit of time, and destroys the missile that is going to hit Nation B at t \u003d 2. It re-tunes its frequency back to 1 in 1 unit of time and destroys the missile that is going to hit the nation at t \u003d 3. It is relaunched at t \u003d 5 with f \u003d 1 and destroys the missile that is going to hit nation B at t \u003d 5. Hence, you need only 1 \u003cem\u003eHackerX\u003c/em\u003e to protect nation B. \u003c/p\u003e\n\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n1 1\n2 3\n3 1\n5 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\n\n\n\n\n\n\n\u003cp\u003e\u003cstrong\u003eExplanation #01\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003eDestroy 1 missile at t \u003d 1, f \u003d 1. now at t \u003d 2, there is a missile with frequency 3. The launched missile takes 2 units of time to destroy this, hence we need a new hackerX missile to destroy this one. The first hackerX missile can destroy the 3rd missile which has the same frequency as itself. The same hackerX missile destroys the missile that is hitting its city at t \u003d 5. Thus, we need atleast 2 hackerX missiles. \u003c/p\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e"}}]}