tag:blogger.com,1999:blog-4115025577315673827.post8801674987675148149..comments2019-10-08T12:02:40.465+05:30Comments on CSE Blog - quant, math, computer science puzzles: Soldiers in a LineUnknownnoreply@blogger.comBlogger6125tag:blogger.com,1999:blog-4115025577315673827.post-37853761957455433252016-02-21T14:29:22.573+05:302016-02-21T14:29:22.573+05:30Is there an algorithm for constructing this permut...Is there an algorithm for constructing this permutation ?Anoopam Agarwalhttps://www.blogger.com/profile/08598660334815237787noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-12128036066580828942016-01-16T18:29:48.318+05:302016-01-16T18:29:48.318+05:30For any general N,answer is the sequence with ceil...For any general N,answer is the sequence with ceil(sqrt(N)) decreasing subsequences:<br />(ceil(sqrt(N)),1) , (2*ceil(sqrt(N)),ceil(sqrt(N))+1), ....(i*ceil(sqrt(N)),(i-1)*ceil(sqrt(N))+1) .... (N,(ceil(sqrt(N))-1)*ceil(sqrt(N))+1)<br />which will essentially give maximum ceil(sqrt(N)) sized increasing/decreasing subsequences.<br />For example,for N=15: 4 3 2 1 8 7 6 5 12 11 10 9 15 14 13Tanmay Ladhttps://www.blogger.com/profile/15029883625237670248noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-61778198228723163082015-09-20T00:45:21.231+05:302015-09-20T00:45:21.231+05:30In other words, we want to find the minimum number...In other words, we want to find the minimum number k such that, for any permutation of 10 elements, we can always either find an increasing subsequence of length k, or a decreasing subsequence of length k.<br /><br />Given a permutation, we can build a standard Young tableau using the Schensted correspondence: <br />https://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted_correspondence<br /><br />This tableau has the property that the length of longest increasing subsequence is the length of the first row (or equivalently, the number of columns), and the length of the longest descreasing subsequence is the height of the first column (or equivalently, the number of lines).<br /><br />Since a tableau with 10 elements necessarily has either at least 4 lines or at least 4 columns, the number k we are looking for is 4.<br /><br />More generally, for N soldiers, the numbers is ceil(sqrt(N)).FĂ©lix de Chaumont Quitryhttps://www.blogger.com/profile/02724420621332283916noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-70182089862421217932015-09-20T00:13:35.465+05:302015-09-20T00:13:35.465+05:304. This is essentially asking to prove the Erdos-S...4. This is essentially asking to prove the Erdos-Szekeres Theorem.Wei Chenhttps://www.blogger.com/profile/06088969504536570097noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-60216166229894583152015-09-19T20:47:27.110+05:302015-09-19T20:47:27.110+05:30Assuming we picker can preprocess the heights befo...Assuming we picker can preprocess the heights before selecting, the least number of soldiers that can be picked in either descending or ascending order would be 2. <br /><br />this scenarios would occur when you pick the first guy as the 5 highest person then try to oscillate between picking the descending and ascending options. <br /><br />Something like this pattern would occur : /\/\/\/\/Vineet Goyalhttps://www.blogger.com/profile/00796666167994910395noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-3145017859265650882015-09-14T18:38:58.244+05:302015-09-14T18:38:58.244+05:30If one does not pick any soldiers then the answer ...If one does not pick any soldiers then the answer is 0. In what way are we picking the soldiers ?Kushal Sharmahttps://www.blogger.com/profile/12087461542612216465noreply@blogger.com