<commit_before>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1 align=\"center\"> Nowfloats Screening round, CET BBSR, 19/08/2016</h1>\n",
    "<h2 align=\"center\"> Revenge of the Pokemons </h2>\n",
    "<h4 align=\"center\"> General Instructions </h4>\n",
    "<h4 align=\"center\"> Total time : 75 mins </h4>\n",
    "<h4 align=\"center\"> Total Questions : 4 </h4>\n",
    "<h4 align=\"center\"> Maximum points : 120 </h4>\n",
    "<h4 align=\"center\"> Qualifying points : 60 </h4>\n",
    "<p></p>\n",
    "<h3 align=\"center\"> Prologue </h3>\n",
    "<p></p>\n",
    "<div align=\"center\">When it comes to catching Pokemons, no-one has beat the students at  NowFloats University. Since launch, catching these monsters has gone viral at NowFloats. The students have mastered the knack of throwing PokeBalls and haven't spared even one.\n",
    "Pokemons around the world travelling through Hyderabad have never been seen again. They say that the life of a Pokemon around here is hardly a few seconds. This created a serious scare among Pokemons around the world and thus, they called a meeting. In this meeting, it was decided that all the pokemons attack NowFloats University and raze it to the ground. This attack would more affect Hyderabad so to erase every possibility of comeback. The revenge has started. </div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3 align=\"center\"> Chapter 1 </h3>\n",
    "<h3 align=\"center\"> Points : 50 </h3>\n",
    "<div align=\"left\"> Day of the attack\n",
    "10:00 AM\n",
    "\n",
    "Here’s a conversation between two gym leaders, Pranav and Rachit. They are roommates and have shared every secret to catch’em all. <br>\n",
    "Pranav : Dude, wake up. Check your whatsapp <br>\n",
    "Rachit : What happened? It's 5 in the morning. <br>\n",
    "Pranav : Look at these pictures! Sajal got attacked around midnight and is badly injured. Everyone is scared and staying in. They have burnt our library, completely destroyed our labs and spreading fast outside the campus. <br>\n",
    "Rachit : *completely woken up now* Oh yes, i have more pictures. They are everywhere, we have to do something. If we don't stop them, our beautiful city could be destroyed.<br>\n",
    "Pranav: I have an idea. Lets first stop the Pokemons from spreading across the campus. First we need to build a fence around them. But the question is how do we do thet :O <br>\n",
    "Rachit: Great idea. I can make the fence real fast but we also need to plan as to where we would put up the pillars for the fence. Any idea?  <br>\n",
    "Pranav: Let me attack the pokemons on the outer ring of the attack zone. As soon as i catch a pokemon, i will also build the fence pillar. You follow me secretly and build the fence around those pillars. <br>\n",
    "So they start. <br>\n",
    "Consider there are N pokemons that attacked the campus. And the location of the ith pokemon can be represented as (xi, yi). Help Pranav find the pokemons that he needs to catch (and build a fence pillar at that location) so that Rachit can quickly fence all the pokemons. Remember they have only limited material to build the fence. <br><br>\n",
    "Write a code which Pranav can run to get the M locations $${(x_1,y_1), (x_2,y_2) … (x_m,y_m)}$$ of pokemons where he can catch pokemons and also build the pillars.<br><br>\n",
    "<h3>Example 1:</h3>\n",
    "<h4>Input</h4>\n",
    "4 <br>\n",
    "35 7 <br>\n",
    "55 65 <br>\n",
    "35 41 <br>\n",
    "17 62 <br>\n",
    "<h4>Output</h4>\n",
    "3 <br>\n",
    "17 62 <br>\n",
    "35 7 <br>\n",
    "55 65 <br>\n",
    "<h3> Explanation </h3>\n",
    "Number of pokemons (N) : 4 <br>\n",
    "Locations of the pokemons (Loc_array): (35,7), (55,65), (35,41), (17,62) <br>\n",
    "Result: <br>\n",
    "Minimum number of location where pillar needs to be built (M): 3 <br>\n",
    "Location of the pillars: (17,62), (35,7), (55, 65) <br>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Locations of pokemons and the fence](./Q1.png)\n",
    "<h4> This will ensure that all the pokemons are caged. The pokemon at the location (35,41) will automatically get surrounded by fence. </h4>\n",
    "\n",
    "<h3>Example2:</h3>\n",
    "<h4>Input: </h4>\n",
    "7 <br>\n",
    "377 106 <br>\n",
    "588 361 <br>\n",
    "450 261 <br>\n",
    "377 261 <br>\n",
    "274 381 <br>\n",
    "404 342 <br>\n",
    "150 150 <br>\n",
    "\n",
    "<h4>Output: </h4>\n",
    "4 <br>\n",
    "150,150 <br>\n",
    "377,106 <br>\n",
    "588,361 <br>\n",
    "274,381 <br>\n",
    "\n",
    "\n",
    "<h3> Graphical Explanation </h3>\n",
    "\n",
    "![Locations of pokemons and the fence](./Q1_2.png)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}<commit_msg>questions done<commit_after>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1 align=\"center\"> Nowfloats Screening round, CET BBSR, 19/08/2016</h1>\n",
    "<h2 align=\"center\"> Revenge of the Pokemons </h2>\n",
    "<h4 align=\"center\"> General Instructions </h4>\n",
    "<h4 align=\"center\"> Total time : 75 mins </h4>\n",
    "<h4 align=\"center\"> Total Questions : 4 </h4>\n",
    "<h4 align=\"center\"> Maximum points : 120 </h4>\n",
    "<h4 align=\"center\"> Qualifying points : 60 </h4>\n",
    "<h5 align=\"center\"><i> Examples have been graphically illustrated by me for better understanding of a wider audience, they weren't originally </i><h5>\n",
    "<p></p>\n",
    "<h3 align=\"center\"> Prologue </h3>\n",
    "<p></p>\n",
    "<div align=\"center\">When it comes to catching Pokemons, no-one has beat the students at  NowFloats University. Since launch, catching these monsters has gone viral at NowFloats. The students have mastered the knack of throwing PokeBalls and haven't spared even one.\n",
    "Pokemons around the world travelling through Hyderabad have never been seen again. They say that the life of a Pokemon around here is hardly a few seconds. This created a serious scare among Pokemons around the world and thus, they called a meeting. In this meeting, it was decided that all the pokemons attack NowFloats University and raze it to the ground. This attack would more affect Hyderabad so to erase every possibility of comeback. The revenge has started. </div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3 align=\"center\"> Chapter 1 </h3>\n",
    "<h3 align=\"center\"> Points : 50 </h3>\n",
    "<div align=\"left\"> Day of the attack\n",
    "10:00 AM\n",
    "\n",
    "Here’s a conversation between two gym leaders, Pranav and Rachit. They are roommates and have shared every secret to catch’em all. <br>\n",
    "Pranav : Dude, wake up. Check your whatsapp <br>\n",
    "Rachit : What happened? It's 5 in the morning. <br>\n",
    "Pranav : Look at these pictures! Sajal got attacked around midnight and is badly injured. Everyone is scared and staying in. They have burnt our library, completely destroyed our labs and spreading fast outside the campus. <br>\n",
    "Rachit : *completely woken up now* Oh yes, i have more pictures. They are everywhere, we have to do something. If we don't stop them, our beautiful city could be destroyed.<br>\n",
    "Pranav: I have an idea. Lets first stop the Pokemons from spreading across the campus. First we need to build a fence around them. But the question is how do we do thet :O <br>\n",
    "Rachit: Great idea. I can make the fence real fast but we also need to plan as to where we would put up the pillars for the fence. Any idea?  <br>\n",
    "Pranav: Let me attack the pokemons on the outer ring of the attack zone. As soon as i catch a pokemon, i will also build the fence pillar. You follow me secretly and build the fence around those pillars. <br>\n",
    "So they start. <br>\n",
    "Consider there are N pokemons that attacked the campus. And the location of the ith pokemon can be represented as (xi, yi). Help Pranav find the pokemons that he needs to catch (and build a fence pillar at that location) so that Rachit can quickly fence all the pokemons. Remember they have only limited material to build the fence. <br><br>\n",
    "Write a code which Pranav can run to get the M locations $${(x_1,y_1), (x_2,y_2) … (x_m,y_m)}$$ of pokemons where he can catch pokemons and also build the pillars.<br><br>\n",
    "<h3>Example 1:</h3>\n",
    "<h4>Input</h4>\n",
    "4 <br>\n",
    "35 7 <br>\n",
    "55 65 <br>\n",
    "35 41 <br>\n",
    "17 62 <br>\n",
    "<h4>Output</h4>\n",
    "3 <br>\n",
    "17 62 <br>\n",
    "35 7 <br>\n",
    "55 65 <br>\n",
    "<h3> Explanation </h3>\n",
    "Number of pokemons (N) : 4 <br>\n",
    "Locations of the pokemons (Loc_array): (35,7), (55,65), (35,41), (17,62) <br>\n",
    "Result: <br>\n",
    "Minimum number of location where pillar needs to be built (M): 3 <br>\n",
    "Location of the pillars: (17,62), (35,7), (55, 65) <br>\n",
    "</div>\n",
    "<div>\n",
    "![Locations of pokemons and the fence](./Q1.png)\n",
    "<h4> This will ensure that all the pokemons are caged. The pokemon at the location (35,41) will automatically get surrounded by fence. </h4>\n",
    "\n",
    "<h3>Example2:</h3>\n",
    "<h4>Input: </h4>\n",
    "7 <br>\n",
    "377 106 <br>\n",
    "588 361 <br>\n",
    "450 261 <br>\n",
    "377 261 <br>\n",
    "274 381 <br>\n",
    "404 342 <br>\n",
    "150 150 <br>\n",
    "\n",
    "<h4>Output: </h4>\n",
    "4 <br>\n",
    "150,150 <br>\n",
    "377,106 <br>\n",
    "588,361 <br>\n",
    "274,381 <br>\n",
    "\n",
    "\n",
    "<h3> Graphical Explanation </h3>\n",
    "\n",
    "![Locations of pokemons and the fence](./Q1_2.png)\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3 align=\"center\"> Chapter 2 </h3>\n",
    "<h3 align=\"center\"> Points : 10 </h3>\n",
    "<div align=\"left\">Pranav and Rachit saved the day by containing the Pokemon attack to NowFloats University.\n",
    "But this made the Pokemons furious! They evolve and plan another attack. Sajal saw what Rachit and Pranav did. He just remembered that a week before he had prototyped a few versions of his Smart Transport Cage in the Mechanical Workshop. <br> \n",
    "He knew that those cages could be used to cage the Pokemons and completely contain the attack. \n",
    "The cages vary in sizes and can hold many Pokemons. But Sajal is stuck at a simple problem. He realised that the Pokemons are of varied weights. He is confused now as to how many cages would be required to capture all of them. <br>\n",
    "\n",
    "Sajal had built K cages in his lab. Each cage can hold max weight of W units. The Pokemons (N) have weights $w_1,w_2,w_3...w_n$  and each pokemon has at-least a weight of 1 unit. Find the arrangement so that the number of cages required to catch all Pokemons is minimised.  <br>\n",
    "Let's say Sajal has C cages $(c_1, c_2,..., c_c)$ for catching N pokemons. For each <b>$i^{th}$</b> cage, print the indices of pokemons, j which is caught in it. Each Pokemon must be caught in only one cage.  <br>\n",
    "\n",
    "Find C and respective placement of pokemons in these cages.  <br>\n",
    "<h3>Example 1 </h3>\n",
    "<h4> Input </h4>\n",
    "6  <i> (Number of pokemons) </i><br> \n",
    "6 <i> (Max capacity of each cage) </i><br> \n",
    "1 2 4 3 5 3 <i> (weights of pokemons) </i><br>\n",
    "<h4> Output </h4>\n",
    "4 <br>\n",
    "1 2 3 <br> \n",
    "3 <br>\n",
    "4 <br>\n",
    "5 <br>\n",
    "<h4>Explanation</h4>\n",
    "Number of Cages required ( C ): 4 <br>\n",
    "First cage: $[1,2,3]$  [Contains Pokemons of weights 1, 2 and 3]<br>\n",
    "Second cage: $[3]$ [Contains Pokemon of weight 3]<br>\n",
    "Third cage: $[4]$ [Contains Pokemon of weight 4]<br>\n",
    "Fourth cage: $[5]$ [Contains Pokemon of weight 5]<br>\n",
    "\n",
    "<h3>Example 2 </h3>\n",
    "<h4> Input </h4>\n",
    "3 <br>\n",
    "10 <br> \n",
    "5 6 4 <br>\n",
    "<h4> Output </h4>\n",
    "2 <br>\n",
    "6 4 <br> \n",
    "5 <br>\n",
    "\n",
    "<h6>Note: First line is the value of C. So 2 cages required. The second two lines shows the pokemons in each of the cage. Cage 1 has two pokemons with weights 6 and 4 units. Cage 2 has one pokemon with weight 5 units <br> You could also have placed the pokemons as $[5, 4]$ and $[6]$ </h6>\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3 align=\"center\"> Chapter 3 </h3>\n",
    "<h3 align=\"center\"> Points : 50 </h3>\n",
    "<div align=\"left\">Pokemons are very frustrated looking at the smart fight back from the students of the NowFloats University. They come up with a group attack strategy. Pokemons divide themselves into groups, and the groups started spreading around the university campus. <br>\n",
    "\n",
    "Each pokemon has a unique fighting style which can be represented using a number, say 12. It means this pokemon when attacked, would throw 12 fireballs at the same time. Based on this unique feature the pokemon war-groups are being created. Each group plans to attack a particular zone in the college.<br>\n",
    "\n",
    "Students get a bit surprised to see this move from the pokemons. Suddenly there is a pokemon group formations across the college. But the NowFloats university students do not give up. They get together and gather the best pokemon catchers. The engineering students create a unique device called <b>“Fire-Ball Reverse Shield (FBRS)”</b>. A war-group is created even by the students, and each student owns FBRS device which has a unique property say 4. This means the FBRS device would fireback 4 fireballs if you throw one fire-ball at it.<br>\n",
    "\n",
    "The students send a spy to find some hidden details of the pokemon strategy. And it does work. The spy is able to figure out number of pokemons in each war-group. This information is vital for the students and they start making equal sized groups to attack the pokemons. So a group of 5 pokemons would be attacked by a group of 5 students.\n",
    "We need your help so that we can predict the overall damage that would happen in the university campus assuming the worst case - every student group would fight with every pokemon war-group.<br><br>\n",
    "\n",
    "Assume that there are N pokemon war groups. Each war-group has a size of P pokemons. The $i^{th}$ war-group has P pokemons with fighting style index as ${f_1, f_2,...,f_p}$. Here $j^{th}$ pokemon in this group, when attacked would throw $f_j$ fireballs at a time.\n",
    "Also say there are M student groups and each group has P students. The ith student-group has P students with FBRS index as ${s_1,s_2...s_p}$. Here for the $j^{th}$ student in this group, when one fireball is thrown at the FBRS would throwback $s_j$ new fireballs as response.<br>\n",
    "\n",
    "When one group of pokemons and one student-group start fighting in a building, one pokemon throws the fireballs at the closest student and the closest student uses the FBRS to fight back only with that pokemon. Since all groups have the same size, so during every group fight one student fights with only one pokemon. <br>\n",
    "\n",
    "Example student group (1,2) attacks pokemon group (5,6). Then the fight happens between 1 and 5 , 2 and 6. Pokemon “5” would throw 5 fireballs at student “1”. Student “1” would throw back 5 fireballs as fight back. Pokemon “6” would throw 6 fireballs at student “2”. Student “2” would throw back 12 fireballs to fight back. Hence total damage at that location is 5+12 = 17. <br>\n",
    "<h3>Example 1 </h3>\n",
    "<h4> Input </h4>\n",
    "2 <br>\n",
    "1 <br>\n",
    "2 <br>\n",
    "2 <br>\n",
    "3 4 <br>\n",
    "1 2 <br>\n",
    "4 5 <br>\n",
    "<h4> Output </h4>\n",
    "2 <br>\n",
    "14 32 <br>\n",
    "<h4> Explanation </h4>\n",
    "Input:<br>\n",
    "Number of pokemon groups (N): 2 <br>\n",
    "Number of student groups (M): 1<br>\n",
    "Size of pokemon group (P): 2<br>\n",
    "Size of student group (P): 2<br>\n",
    "Fighting Index of all pokemons (pokemon_array):$[(3,4), (1,2)]$<br>\n",
    "FBRS index of all student groups (fbrs_array): $[(4,5)]$<br>\n",
    "Output:<br>\n",
    "Total Number of fights: 2<br>\n",
    "Damage Spread across the campus: [14, 32]<br><br>\n",
    "<i>Note: The first fight is between student group (4,5) and pokemon group (3,4). So the damage is 32. The second fight is between student group (4,5) and pokemon group (1,2). So the damage is 14.</i><br>\n",
    "\n",
    "<h3>Example 2 </h3>\n",
    "<h4> Input </h4>\n",
    "3 <br>\n",
    "2 <br>\n",
    "3 <br>\n",
    "3 <br>\n",
    "1 1 1 <br>\n",
    "2 2 2 <br>\n",
    "3 4 5 <br>\n",
    "1 2 3 <br>\n",
    "4 4 5 <br>\n",
    "<h4> Output </h4>\n",
    "6 <br>\n",
    "6 12 13 26 26 53 <br>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3 align=\"center\"> Chapter 4 </h3>\n",
    "<h3 align=\"center\"> Points : 10 </h3>\n",
    "<div align=\"left\">Finally, the fight is over! With your help, all Pokemons have been caught. This great victory, calls for a celebration. So, NowFloats University announces a huge party tonight. M boys and N girl would attend this party. Each boy wants a girl who is strictly shorter than him. A girl can dance with only one boy and vice-versa. Given the heights of all the boys and girls tell whether it is possible for all boys to get a girl. <br><br>\n",
    "<b>Input:</b> <br>\n",
    "The first line contains T denoting the number of test cases.<br>\n",
    "Each test case contains three lines.<br>\n",
    "The first line contains M and N.<br>\n",
    "The second line contains M integers each denoting the height of boy.<br>\n",
    "The third contains N integers each denoting the height of girl.<br>\n",
    "<br>\n",
    "<b>Output</b>:<br>\n",
    "Print YES if it is possible for each boy to get a girl else print NO.<br>\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    ""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2.0
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
{'fraction_non_alphanumeric': 0.15414046121593292, 'fraction_numerical': 0.03333333333333333, 'mean_word_length': 3.069311153764129, 'pattern_counts': {'":': 66, '<': 320, '<?xml version=': 0, '>': 320, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4642217', 'n_tokens_mistral': 6830, 'n_tokens_neox': 6467, 'n_words': 2674}