All Questionshttps://ipc.discuss.codechef.com/questions/?type=rssquestionsenSun, 28 Dec 2014 14:53:09 +0530Sept - Week 1 - Discussions / Week 2 Contest Updatehttps://ipc.discuss.codechef.com/questions/51017/sept-week-1-discussions-week-2-contest-update<p>Hey guys, welcome to the new platform :)</p>
<p>BIG Thanks to the Codechef team.</p>
<p>Couple of things : Online contests for ACM are coming up and time to put in more efforts!
The more active you are the more you can learn, you have to come up and ask your doubts dont expect others to reach out to you.
See the tags - Each month contest we shall use month#, week# format.</p>
<p>If you have doubt regarding some problem, you can post it as different question and use the same month# and week# format. Also add tags like "NEERC08".</p>
<p>Contest-Update</p>
<p>Sept-Week2</p>
<p>Contest link : <a href="http://codeforces.com/gym/100200">http://codeforces.com/gym/100200</a></p>anudeep2011Mon, 15 Sep 2014 19:40:23 +0530https://ipc.discuss.codechef.com/questions/51017/sept-week-1-discussions-week-2-contest-updateweek1month9NEERC 2008 Drive Through Megacityhttps://ipc.discuss.codechef.com/questions/51030/neerc-2008-drive-through-megacity<p>I found this problem the most interesting out of all the problems. Here is the link to the contest: <a href="http://codeforces.com/gym/100286/">http://codeforces.com/gym/100286/</a>. It's problem D.</p>
<p>I tried to solve it using djkstra. I was trying to create a DAG, by always going forward ( increasing x ) until I hit a rectangle. After that I had 3 options, go through the rectangle, go up till the top of the rectangle and go down to the bottom. Then, I found a test case for which it didn't work.</p>
<p>Later I figured, in the optimal path, all my horizontal paths will have y coordinates parallel to the rectangles bottom or top and all my vertical paths will have x coordinates parallel to the sides. With 1000 rectangles, I can have 2000 unique y-levels and 2000 unique x-levels. Therefore I can divide the whole grid into a 2000 by 2000 grid. Then run djkstra through it. The difficulty with this idea is to determine if the path is inside a rectangle, outside or on the boundary.</p>
<p>That's all the idea I got. Didn't find anything over the net either.</p>forthrightMon, 15 Sep 2014 20:43:37 +0530https://ipc.discuss.codechef.com/questions/51030/neerc-2008-drive-through-megacityweek1month9neerc08ssspgeometryFibonacci Systemhttps://ipc.discuss.codechef.com/questions/51042/fibonacci-system<p>How to approach sep week-1's question fibonacci system?</p>phantom002Mon, 15 Sep 2014 21:46:53 +0530https://ipc.discuss.codechef.com/questions/51042/fibonacci-systemweek1month9neerc08Google Apactest Round B problem Chttps://ipc.discuss.codechef.com/questions/51117/google-apactest-round-b-problem-c<p>Hi,
I participated in google apactest Round B. I was unable to solve this problem for large input. Can anyone explain how to solve it:
<a href="https://code.google.com/codejam/contest/4214486/dashboard#s=p2">https://code.google.com/codejam/contest/4214486/dashboard#s=p2</a></p>sanjeev1779Tue, 16 Sep 2014 13:11:59 +0530https://ipc.discuss.codechef.com/questions/51117/google-apactest-round-b-problem-cdynamic-programmingQuery regarding ICPC Gwalior Sitehttps://ipc.discuss.codechef.com/questions/51211/query-regarding-icpc-gwalior-site<p>The last date for registration is 20th Sept. The date for the onsite contest is likely to be postponed but has not been finalized yet. Will the deadline for registration be extended? If not, how is one supposed to decide whether to choose Gwalior or not? I think the deadline for registration should be at least one week after the day the onsite contest date is announced.</p>sikander_nsitWed, 17 Sep 2014 19:47:40 +0530https://ipc.discuss.codechef.com/questions/51211/query-regarding-icpc-gwalior-siteregionalsacm-icpcSept-Week1-NEERC: Help regarding problem: Aerodynamicshttps://ipc.discuss.codechef.com/questions/51235/sept-week1-neerc-help-regarding-problem-aerodynamics<p>This problem was solved by a lot of users, so it seemed like there is a standard approach to problems like these. Any help on how to solve this problem or some hint towards the solution will be highly appreciated.</p>anubhav94Wed, 17 Sep 2014 23:27:03 +0530https://ipc.discuss.codechef.com/questions/51235/sept-week1-neerc-help-regarding-problem-aerodynamics#neerc08#week1#month9A link with many algorithmshttps://ipc.discuss.codechef.com/questions/51381/a-link-with-many-algorithms<p>See if this helps you <a href="http://e-maxx.ru/algo/">http://e-maxx.ru/algo/</a></p>
<p>Use some translator</p>anudeep2011Sat, 20 Sep 2014 20:16:09 +0530https://ipc.discuss.codechef.com/questions/51381/a-link-with-many-algorithmsalgorithmsBug in tools.anudeep2011.comhttps://ipc.discuss.codechef.com/questions/51426/bug-in-toolsanudeep2011com<p>The codeforces module of <a href="http://tools.anudeep2011.com">tools.anudeep2011.com</a> is not working for me. The contest field is empty and not responding to click on dropdown arrow while the TC and CC modules are working fine. Anyone else facing the same problem? <a href="/users/284/anudeep2011">@anudeep2011</a> Can you please take a look?</p>sikander_nsitSun, 21 Sep 2014 20:05:37 +0530https://ipc.discuss.codechef.com/questions/51426/bug-in-toolsanudeep2011combugTwo Sets(CF)https://ipc.discuss.codechef.com/questions/51761/two-setscf<p>How to approach <a href="http://codeforces.com/contest/469/problem/D">Two Sets</a>?</p>amitpandeykgpFri, 26 Sep 2014 18:28:49 +0530https://ipc.discuss.codechef.com/questions/51761/two-setscfcodeforcesSRM 634 250 pthttps://ipc.discuss.codechef.com/questions/51778/srm-634-250-pt<p>I tried a greedy approach to solve this question which failed during system testing. I am trying to find proof of incorrectness but am not able to do so. This is my approach. <br>
I first sort vector s(number of customers for each item in reverse order) and start from assigning items with most customers. I have an array a[] which stores the number of items bought by customer i. In each iteration, I sort a[]. For each item s[j],I do the following:<br>
1. Move in increasing order of a[i] and if a[i]+1 is less than K, then give the item to customer i, (decrease s[j] and move ahead) otherwise break and start assigning that item in decreasing order of a[i]. <br>
Can anyone tell when this approach will fail?</p>thunderkingFri, 26 Sep 2014 22:38:19 +0530https://ipc.discuss.codechef.com/questions/51778/srm-634-250-ptgreedysrmCodeSprint - Fill the tankhttps://ipc.discuss.codechef.com/questions/51827/codesprint-fill-the-tank<p>How to approach the problem <a href="https://www.hackerrank.com/contests/csindia14-er1/challenges/fill-the-tank">Fill the Tank</a> ?</p>karan173Sun, 28 Sep 2014 02:45:29 +0530https://ipc.discuss.codechef.com/questions/51827/codesprint-fill-the-tankcodesprinthackerrankCodesprint - Working with boxes Modificationhttps://ipc.discuss.codechef.com/questions/51862/codesprint-working-with-boxes-modification<p><a href="https://www.hackerrank.com/contests/csindia14-er1/challenges/working-with-boxes">Original Problem</a></p>
<p>After an update</p>
<p><code>If the operation time < 0 at any point of time, the the time taken is 0.</code></p>
<p>I misinterpreted the problem as to resetting the <strong>total</strong> operation time to 0 when it goes negative. i.e, now order of operations matters even more. </p>
<p>For example, (1 1 2 2) with C = 3,</p>
<p><code>1*1 + 1*1 - 3 = -1
Total Time = -1 -> 0
2*1 + 2*1 - 3 = 1
Total Time = 0+1 = 1
....</code></p>
<p>Or in other order</p>
<p><code>2*1 + 2*1 - 3 = 1
Total Time = 1
1*1 + 1*1 - 3 = -1
Total Time = 1-1 = 0
....</code></p>
<p>Any ideas on this interpretation of the problem?</p>nims11Sun, 28 Sep 2014 14:26:07 +0530https://ipc.discuss.codechef.com/questions/51862/codesprint-working-with-boxes-modificationcodesprintSRM 633 Div II 1000 ptr.https://ipc.discuss.codechef.com/questions/52065/srm-633-div-ii-1000-ptr<p>Can anyone discuss this problem as the editorial is long due and this problem is not discussed in any forum. I feel this relates to find sort of Euler tour on the conditions, but could not come up with any conclusive algorithm.</p>
<p><a href="http://community.topcoder.com/stat?c=problem_statement&pm=13470&rd=16076">Problem Statement</a></p>orchidmajumderWed, 01 Oct 2014 13:25:26 +0530https://ipc.discuss.codechef.com/questions/52065/srm-633-div-ii-1000-ptrtopcodersrmCodeforces 270 Div1/2 Problem Fhttps://ipc.discuss.codechef.com/questions/52079/codeforces-270-div12-problem-f<p>Can somebody explain the tutorial to problem F present <a href="http://codeforces.com/blog/entry/14028">here</a> in more detail? What is meant by bases?
Can somebody share some related material?</p>aduryskWed, 01 Oct 2014 15:06:19 +0530https://ipc.discuss.codechef.com/questions/52079/codeforces-270-div12-problem-fmathscodeforcesalgebraUSACO Bronzehttps://ipc.discuss.codechef.com/questions/52193/usaco-bronze<p><a href="http://usaco.org/index.php?page=viewproblem2&cpid=360">http://usaco.org/index.php?page=viewproblem2&cpid=360</a></p>
<p>Please tell me how to solve this.I am stuck.I think I am not also getting what the question wants to ask.</p>vishalsharmaThu, 02 Oct 2014 23:15:50 +0530https://ipc.discuss.codechef.com/questions/52193/usaco-bronzesearchingusacoSolution for srm 635 easy problemhttps://ipc.discuss.codechef.com/questions/52334/solution-for-srm-635-easy-problem<p>Try for each pair (i, j) of starting indices. Now, to compare them, first we have to transform both of them to start from zero. So all coordinates of the first part are seen as (x[k] - x[i], y[k] - y[i]) and similarly for second. Now the scaling factor for a particular pair can be calculated by finding the number which we should multiply the coordinates in the second part to get the corresponding coordinate in the first part. This is (x[j + 1] - x[j]) / (x[i + 1] - x[i]). Now we just keep looping till we can scale the second part to match the first part and calculate the distance in the first part. Take maximum of those. Seems like using double for the scaling factors causes precision problems. Hope i am clear.</p>balajiganapathSat, 04 Oct 2014 23:37:10 +0530https://ipc.discuss.codechef.com/questions/52334/solution-for-srm-635-easy-problemsrm635easySRM 635 div II 1000 ptr.https://ipc.discuss.codechef.com/questions/52364/srm-635-div-ii-1000-ptr<p>I saw a post last night regarding Div II 1000 ptr. but could not find it now.
So, here is my approach to solve the Div II 1000 ptr problem from SRM 635 (this idea is mostly based on a comment of <a href="/users/11746/xellos0">@xellos0</a> on topcoder forum).</p>
<p>You have n-1 edges to deal with. In every turn, you remove one edge say (X--Y). Then, the tree is broken into two subtrees one with root X and another with root Y. Now, find diameter of both the subtrees individually; say it's d1 and d2. There should be one edge with the same cost as of edge (X--Y) that should be added between the two subtrees to make it a tree again (it does not matter which endpoints we connect while adding this edge, as the cost remains same). So, diameter of the new tree becomes d1+d2+cost[X][Y]. We take maximum over all such diameters and the initial diameter.</p>
<p>Finding diameter is a well known problem.
<a href="http://www.spoj.com/problems/PT07Z/">Problem on SPOJ</a></p>
<p>The idea is to run a DFS/BFS from any chosen vertex(here the vertex is fixed as we are dealing the problem in such a way that the tree is broken into two subtrees with root X and Y) and find the farthest vertex; call it Z. Now from Z, run a second dfs/bfs to find the farthest vertex and take max distance between these two paths (root to Z and from Z to farthest_from_z).</p>
<p>Here is an implementation:
<a href="http://pastie.org/private/8le9klbdceqszrywkpfgbw">Link</a></p>orchidmajumderSun, 05 Oct 2014 10:12:43 +0530https://ipc.discuss.codechef.com/questions/52364/srm-635-div-ii-1000-ptrdiametergraphdfsbfstopcodersrm635ZQUERY(SPOJ)https://ipc.discuss.codechef.com/questions/52439/zqueryspoj<p>Can anyone tell me the suitable algorithm/approach to solve this problem
<a href="http://www.spoj.com/problems/ZQUERY/">http://www.spoj.com/problems/ZQUERY/</a></p>viperxSun, 05 Oct 2014 19:52:44 +0530https://ipc.discuss.codechef.com/questions/52439/zqueryspojspojCodeforces Round 271 Problem E Pillarshttps://ipc.discuss.codechef.com/questions/52538/codeforces-round-271-problem-e-pillars<p>How can we solve the problem using BIT ? After figuring out the basic dp we need a data structure to find best[i]=max(best[j])+1 with j<i,|h[j]-h[i]|>= D. We can find this using segment tree. Can we find this maximum using BIT ?</p>
<p>Link to the problem <a href="http://codeforces.com/contest/474/problem/E">http://codeforces.com/contest/474/problem/E</a> </p>nilmishTue, 07 Oct 2014 12:51:25 +0530https://ipc.discuss.codechef.com/questions/52538/codeforces-round-271-problem-e-pillarsfenwickCodeSprint India : Island Queries Approachhttps://ipc.discuss.codechef.com/questions/52554/codesprint-india-island-queries-approach<p>As asked by few people on facebook, I am posting my solution to the <a href="https://www.hackerrank.com/contests/csindia14-er2/challenges/island-queries">problem</a> here</p>
<p>In the question let us assume the permutation of the row as <b>N</b> nodes of a chain connected by <b>N - 1</b> edges. Let the value of each edge be the maximum of the two elements it is connecting.
Now if we are coloring all the nodes whose values are less than or equal to <b>X</b>, let us assume all the nodes are separate Islands initially. So there are <b>X</b> Islands initially. </p>
<p>Now we connect two adjacent Islands together and make a single Island if the maximum value of the two Islands is less than of equal to <b>X</b> (why?) and the count of number of Islands decreases by one. But the maximum value between two Islands is the value of the edge connecting it. So all those edges whose value is less than or equal to <b>X</b> will decrease the count of number of Islands by one.</p>
<p>We can count the number of edges whose value is less than or equal to <b>X</b> by using Binary Indexed Trees or Segment Trees. </p>
<p>In the update operation if we are swapping two different elements the values of the edges connecting those two elements will change. So we need to update 4 edges twice. Complexity ~ <b>O(8 * Q * log(N))</b>.</p>aduryskTue, 07 Oct 2014 18:44:33 +0530https://ipc.discuss.codechef.com/questions/52554/codesprint-india-island-queries-approachfenwickSPOJ MINSEQhttps://ipc.discuss.codechef.com/questions/53289/spoj-minseq<p>my solution to the problem <a href="http://www.spoj.com/problems/MINSEQ/">http://www.spoj.com/problems/MINSEQ/</a>
<a href="http://ideone.com/2PsjEt">http://ideone.com/2PsjEt</a>
i have solved the problem in O(len(a)+len(b)) but getting wrong ans , i have tried all possible test cases ,if possible give me some test cases where the solution fails</p>viperxWed, 15 Oct 2014 23:36:26 +0530https://ipc.discuss.codechef.com/questions/53289/spoj-minseqspoj2014 TCO Algorithm Round 3A - Division I, Level Onehttps://ipc.discuss.codechef.com/questions/53329/2014-tco-algorithm-round-3a-division-i-level-one<p>How to approach <a href="http://community.topcoder.com/stat?c=problem_statement&pm=13343">this problem</a>? </p>amitpandeykgpThu, 16 Oct 2014 19:02:53 +0530https://ipc.discuss.codechef.com/questions/53329/2014-tco-algorithm-round-3a-division-i-level-onetopcoderFractional Cascadinghttps://ipc.discuss.codechef.com/questions/56148/fractional-cascading<p>Can somebody provide some good links to learn fractional cascading ? and some links to good problems related to it?</p>aduryskSat, 22 Nov 2014 18:19:51 +0530https://ipc.discuss.codechef.com/questions/56148/fractional-cascadingcascadingExtenstion of Coupon collector problemhttps://ipc.discuss.codechef.com/questions/60064/extenstion-of-coupon-collector-problem<p>X took N dices, numbered from 1 to N, shuffled them, took K of them randomly and then recorded their numbers and returned them to the pile. Then he repeated these steps:
shuffle them again, again took the K dices, and so on.</p>
<p>how many times he need to do so,that each dice has been taken at least once?</p>anup1pmaSun, 28 Dec 2014 14:53:09 +0530https://ipc.discuss.codechef.com/questions/60064/extenstion-of-coupon-collector-problemdynamic-programmingexpectationprobability