{"id":182448,"date":"2025-01-13T19:56:31","date_gmt":"2025-01-13T19:56:31","guid":{"rendered":"https:\/\/learnexams.com\/blog\/?p=182448"},"modified":"2025-01-13T19:56:34","modified_gmt":"2025-01-13T19:56:34","slug":"aisha-is-playing-a-game-where-she-controls-a-character-to-catch-pancakes-falling-onto-a-stage","status":"publish","type":"post","link":"https:\/\/www.learnexams.com\/blog\/2025\/01\/13\/aisha-is-playing-a-game-where-she-controls-a-character-to-catch-pancakes-falling-onto-a-stage\/","title":{"rendered":"Aisha is playing a game where she controls a character to catch pancakes falling onto a stage"},"content":{"rendered":"\n<p>Aisha is playing a game where she controls a character to catch pancakes falling onto a stage. \u2022 The character can move left and right on a stage of length n. The character&#8217;s location : is in the range {1, 2, \u2026.., n}. Let or by the location of the character at time t. At each second, Aisha can move the character to the left (C++1 = 2t &#8211; 1) one step, to the right 2+1 = 2t +1) one step, or stay in the same spot (3t+1 = x+). (Exceptions: can&#8217;t move left when current 2 = 1 and can&#8217;t move right when I = n.)<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The game lasts m seconds.<\/li>\n\n\n\n<li>Aisha knows the game really well, so she knows when and where pancakes will fall, i.e. pairs (t,p), which means at t seconds, a pancake will be at position p. You are given this, and assume lookup of this information in constant time.<\/li>\n<\/ul>\n\n\n\n<p>The character starts at location 1 at time 0. Please design an algorithm to find out the most pancakes Aisha can catch. It should run in Omn) time &#8211; please also justify why.<\/p>\n\n\n\n<p>Example: (t, p) sequence: (1, 1), (2, 2), (3, 4), (3, 5), (4, 3), (4,4), (5, 2)). Optimal solu- tion: 4 pancakes. Aisha can stay still for first step (21 = 1) and catch pancake, move right (22 = 2) and catch pancake, stay still (23 = 2) then move right (14 = 3) and catch pancake, and move left at (35 = 2) and catch pancake.<\/p>\n\n\n\n<p><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-6-color\">The correct answer and explanation is:<\/mark><\/strong><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Algorithm<\/h3>\n\n\n\n<p>The task can be solved using <strong>dynamic programming (DP)<\/strong>. Let <code>dp[t][x]<\/code> represent the maximum number of pancakes Aisha can catch if she is at position <code>x<\/code> at time <code>t<\/code>. We can build this DP table based on the following rules:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialization:<\/strong> At <code>t = 0<\/code>, <code>dp[0][1] = 0<\/code> (Aisha starts at position 1 and has not caught any pancakes).<\/li>\n\n\n\n<li><strong>Transition:<\/strong> For each <code>t<\/code> and <code>x<\/code>, the value of <code>dp[t][x]<\/code> depends on:\n<ul class=\"wp-block-list\">\n<li>Staying at the same position (<code>x<\/code>): <code>dp[t][x] = max(dp[t-1][x], dp[t][x])<\/code>.<\/li>\n\n\n\n<li>Moving left (<code>x-1<\/code>), if <code>x > 1<\/code>: <code>dp[t][x] = max(dp[t-1][x-1], dp[t][x])<\/code>.<\/li>\n\n\n\n<li>Moving right (<code>x+1<\/code>), if <code>x &lt; n<\/code>: <code>dp[t][x] = max(dp[t-1][x+1], dp[t][x])<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Catch pancakes:<\/strong> If a pancake falls at position <code>x<\/code> at time <code>t<\/code>, increment <code>dp[t][x]<\/code> by 1.<\/li>\n\n\n\n<li><strong>Final result:<\/strong> The maximum value in the last row of the DP table (<code>dp[m][*]<\/code>) gives the maximum number of pancakes Aisha can catch.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">Implementation Steps<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Initialize a DP table of size <code>m+1 x n+1<\/code> with zeros.<\/li>\n\n\n\n<li>Preprocess the pancake positions for constant-time lookup using a hash table.<\/li>\n\n\n\n<li>Fill the DP table row by row (time step by time step).<\/li>\n\n\n\n<li>Return the maximum value in the last row.<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Why O(mn)O(mn)?<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We iterate over <code>m<\/code> time steps.<\/li>\n\n\n\n<li>For each time step, we update <code>n<\/code> positions.<\/li>\n\n\n\n<li>Each update involves constant-time operations (checking moves and adding pancake values). Thus, the time complexity is O(mn)O(mn).<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Example Walkthrough<\/h3>\n\n\n\n<p>Given <code>n = 5<\/code>, <code>m = 5<\/code>, and pancakes at <code>(1,1)<\/code>, <code>(2,2)<\/code>, <code>(3,4)<\/code>, <code>(3,5)<\/code>, <code>(4,3)<\/code>, <code>(4,4)<\/code>, <code>(5,2)<\/code>:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Start at <code>(1, 1)<\/code>, catch 1 pancake.<\/li>\n\n\n\n<li>Move to <code>(2, 2)<\/code> in the second second, catch another pancake.<\/li>\n\n\n\n<li>Move to <code>(3, 3)<\/code> (not catching at <code>(3,4)<\/code> or <code>(3,5)<\/code>), then move to <code>(4, 3)<\/code> for a pancake.<\/li>\n\n\n\n<li>Return to <code>(5, 2)<\/code> for a total of 4 pancakes.<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>This algorithm ensures correctness and efficiency by systematically exploring all possible movements while avoiding redundant computations.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Aisha is playing a game where she controls a character to catch pancakes falling onto a stage. \u2022 The character can move left and right on a stage of length n. The character&#8217;s location : is in the range {1, 2, \u2026.., n}. Let or by the location of the character at time t. At [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[25],"tags":[],"class_list":["post-182448","post","type-post","status-publish","format-standard","hentry","category-exams-certification"],"_links":{"self":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/182448","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/comments?post=182448"}],"version-history":[{"count":0,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/182448\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/media?parent=182448"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/categories?post=182448"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/tags?post=182448"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}