Questions Tagged With challengehttps://discuss.codechef.com/tags/challenge/?type=rssquestions tagged <span class="tag">challenge</span>enTue, 08 Jul 2014 18:03:11 +0530CAKES - Editorialhttps://discuss.codechef.com/questions/4287/cakes-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/CAKES/">Practice</a><br>
<a href="http://www.codechef.com/SEPT10/problems/CAKES/">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>CHALLENGE</p>
<h1>EXPLANATION</h1>
<p>As is the case with many challenge problems, this problem is NP-hard. It is often called the "Concurrent Open Job Shop" problem in research<br>
literature. There is, however, one simplification that can be made. That is, we can restrict our attention to solutions where the cakes are scheduled<br>
in the same order by all bakers for the following reason. Consider a solution S and say baker i works the longest overall (i.e. has the largest sum<br>
of preparation times) and processes cake j last in S. Adjust S by moving cake j to the end of every baker's schedule while not changing the<br>
relative order of the remaining cakes. The completion time of every cake j' != j is not decreased since their completion time by each individual<br>
baker does not decrease. The completion time of cake j does not decrease since baker i worked the longest so all other bakers i' != i still<br>
complete cake j no later than baker i. Recursively apply these arguments to the remaining cakes j' != j.</p>
<p>The problem can, however, be approximated somewhat well. The following O(n * (n+m)) algorithm finds a solution whose weighted completion<br>
time is no more than 2 times the optimum. Denote the weight of customer j by w(j) and the processing time of cake j by baker i by p(j,i). Let I<br>
be the baker that will work the longest (i.e. maximizes p(j _ 1, i) + p(j _ 2, i) + ... + p(j _ n, i)) and let j be the cake j that minimizes w(j)/p(j,i). Add<br>
cake j to the end of the schedule we will recursively compute on the remaining cake. For each job j' != j, update w(j') := w(j') - w(j) * p(j',i)/p(j,i).<br>
Recursively compute a schedule on the remaining cakes j' != j according to these new weights and add cake j to the end of this schedule.<br>
The arguments showing why this is a 2-approximation are subtle and can be found in [1]. Assuming P != NP, one cannot approximate this problem<br>
within any constant better than 6/5 with a polynomial-time algorithm</p>
<p>[1]. Finally, even approximating this problem within a constant better than 2 will refute a fundamental open conjecture known as the<br>
"Unique Games Conjecture" (independently shown in [2] and [3]). So, while this<br>
conjecture is still open we do not know how to guarantee a better-than-2 approximation in polynomial time.<br>
[1] M. Mastrolilli, M. Queyranne, A. Schulz, O. Svensson, and N. Uhan, Minimizing the sum of weighted completion times in a concurrent open shop.<br>
Operations Research Letters (2010), doi:10.1016/j.orl.2010.04.011<br>
[2] N. Bansal and S. Khot, Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. Preprint available at Subhash's<br>
page <a href="http://cs.nyu.edu/~khot/">http://cs.nyu.edu/~khot/</a><br>
[3] A. Kumar, R. Manokaran, M. Tulsiani, N. Vishnoi, On LP-based approximability for strict CSPs. Preprint available at<br>
<a href="http://arxiv.org/abs/0912.1776">http://arxiv.org/abs/0912.1776</a></p>adminThu, 29 Nov 2012 11:27:55 +0530https://discuss.codechef.com/questions/4287/cakes-editorialcakeschallengeeditorialsept10IOPC 2013: IOPC13Ghttps://discuss.codechef.com/questions/7149/iopc-2013-iopc13g<p>I have tried solving this question <a href="http://www.codechef.com/IOPC2013/problems/IOPC13G">http://www.codechef.com/IOPC2013/problems/IOPC13G</a> , but iam not able to figure out an algorithm, can any one explain/ideas about??</p>saikiranboga11Sun, 10 Mar 2013 12:47:35 +0530https://discuss.codechef.com/questions/7149/iopc-2013-iopc13giopc2013chelpchallengeunsolvedproblemScoring of challenge questionhttps://discuss.codechef.com/questions/7200/scoring-of-challenge-question<p>I have seen a trend that whenever I submit my challenge question, I get the best score on my very first submission. If I resubmit it, my score fluctuates but stay below the score of my first submission. Why does it happen so, even though the test cases are randomized?</p>manasvi2001Mon, 11 Mar 2013 04:59:21 +0530https://discuss.codechef.com/questions/7200/scoring-of-challenge-questionchallengeplease Explain how to solve RDFhttps://discuss.codechef.com/questions/7248/please-explain-how-to-solve-rdf<p>Hi ,
I have solved two easy problem and fire escape problem but unable to figure out solution for RDF . Can any one explain the solution of RDF problem please ? </p>javag05Mon, 11 Mar 2013 22:59:57 +0530https://discuss.codechef.com/questions/7248/please-explain-how-to-solve-rdfchallengealgorithmString Query problem- need test caseshttps://discuss.codechef.com/questions/8321/string-query-problem-need-test-cases<p>i need test cases for <a href="http://www.codechef.com/APRIL13/problems/STRQUERY">link text</a> problem.I wrote code for it....but getting WA.I executed some of my custom test case but could not find any error.</p>atulbondTue, 16 Apr 2013 12:26:40 +0530https://discuss.codechef.com/questions/8321/string-query-problem-need-test-caseschallengec++April Long Fault Tolerance editorial explanation?https://discuss.codechef.com/questions/8688/april-long-fault-tolerance-editorial-explanation<p>I didn't get the gaussian elimination method. Here servers and chunks are denoted along rows and columns respectively, then to convert 1 into 0 they Xor two columns. But isn't it conceptually wrong to Xor 2 different chunks? Remember that column operations are invalid in Gauss Elimination for solving linear equation.</p>
<p>Here they have assumed servers to be the linear combinations of chunks, which may have 1 or 0 as coefficient, But isn't it chunks which are linear combinations of servers?</p>mangatmodiWed, 24 Apr 2013 17:23:22 +0530https://discuss.codechef.com/questions/8688/april-long-fault-tolerance-editorial-explanationfaultchallengegauss-elimlapindromes comp problemhttps://discuss.codechef.com/questions/13046/lapindromes-comp-problem<p>why it is giving wrong answer</p>alpit_93Mon, 10 Jun 2013 02:01:54 +0530https://discuss.codechef.com/questions/13046/lapindromes-comp-problemchallengeScrap JUNE LONG CONTESThttps://discuss.codechef.com/questions/14030/scrap-june-long-contest<p>As there are so many cases of cheating it would be appreciated if ratings of JUNE CONTEST are scrapped</p>sumanth3232Tue, 18 Jun 2013 17:03:53 +0530https://discuss.codechef.com/questions/14030/scrap-june-long-contestchallengeChallengeshttps://discuss.codechef.com/questions/14487/challenges<p>After solving a couple of challenges in long contests I would like to say that it would be really nice to have at the beginning of the contest the problem setter/tester score for that challenge problem. I'm really curios to see how many times the best contest solution defeats the setter's solution.</p>insederThu, 20 Jun 2013 15:25:04 +0530https://discuss.codechef.com/questions/14487/challengeschallengeList of past challenge problemhttps://discuss.codechef.com/questions/17256/list-of-past-challenge-problem<p>Where to get list of all past challenges problem of codechef</p>nirajsSun, 14 Jul 2013 17:41:15 +0530https://discuss.codechef.com/questions/17256/list-of-past-challenge-problemchallengerunning problemhttps://discuss.codechef.com/questions/19751/running-problem<p>i have compiled a program in C,which runs perfectly according to need,but codechef is not accepting it,neither it says any error in any of line,just WRONG CODE gets displayed on the screen.
whats the problem? </p>drj28Tue, 06 Aug 2013 01:33:53 +0530https://discuss.codechef.com/questions/19751/running-problemchallengeProblem in to queue or not to queuehttps://discuss.codechef.com/questions/23323/problem-in-to-queue-or-not-to-queue<p>To Queue or not to queue is one of the Question...</p>
<p>Ive been satisfyin all the conditions like the range of Q, string length is a +ve integer, c is lower case and modulo... Ive gone through all these conditions and performed almost all the test cases i perform... I've written the code in java its succesfully running but telling wrong code.. I am sure with my code it matches the sample case given but still its appearing wrong code...</p>nishDcoderSun, 08 Sep 2013 19:37:10 +0530https://discuss.codechef.com/questions/23323/problem-in-to-queue-or-not-to-queueseptemberchallenge2013EDSTGRID - Editorialhttps://discuss.codechef.com/questions/27844/edstgrid-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/EDSTGRID">Practice</a><br>
<a href="http://www.codechef.com/OCT13/problems/EDSTGRID">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/ACRush">Tiancheng Lou</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/jingbo_adm">Jingbo Shang</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/djdolls">Ajay K. Verma</a></p>
<h1>DIFFICULTY:</h1>
<p>CHALLENGE</p>
<h1>PREREQUISITES:</h1>
<p>Bipartite matching, <a href="http://en.wikipedia.org/wiki/Hungarian_algorithm">Hungarian algorithm</a></p>
<h1>PROBLEM:</h1>
<p>Given a grid with some cells colored black and others white, the task is to trasform the grid into one where all black cells are connected, using minimum cost transformations. A single transformation can change the color of a single cell, or swap the colors of two adjacent cells. The cost of a swapping transformation is 1, while the cost of changing the color of a cell to black (white) is c<sub>2</sub> (c<sub>3</sub>). </p>
<h1>QUICK EXPLANATION:</h1>
<p>If the target grid, as well as the cells whose colors have to be changed are already known, then the problem reduces to transform a source grid configuration into a target grid configuration using only swapping operations. This can be solved using a min-cost matching algorithm. Hence, the main task is to find the target grid and the cells whose color should be changed. This can be done either using a greedy heuristic or using a simulated annealing kind of algorithm.</p>
<h1>EXPLANATION:</h1>
<p>First, let us ignore the costly transformations of changing the color of a single cell, and assume that the only allowed transformation is to swap the color of two adjacent cells. Furthermore, let us assume that some oracle already found the target grid configuration for us (we will discuss later how to implement this oracle). This means that we have a source grid configuration, and a target grid configuration (from oracle), and we want to find out how to transform the former into the latter using minimum cost transformations.</p>
<p>Let the black cells in the source configuration be at positions A<sub>1</sub>, A<sub>2</sub>, ..., A<sub>n</sub>, and in the target configuration be at positions B<sub>1</sub>, B<sub>2</sub>, ..., B<sub>n</sub>. After applying the swapping transformations each of the A<sub>i</sub>'s will be mapped to exactly one of the B<sub>j</sub>. In other words, the problem is equivalent to find a minimum cost matching between the set of A<sub>i</sub>'s and B<sub>j</sub>'s.</p>
<p>The number of transformations to move the color of a cell at position A (x1, y1) to a cell at position B (x2, y2) is the same as the L<sub>1</sub>-distance between the two points, i.e., <strong>abs</strong>(x1 - x2) + <strong>abs</strong>(y1 - y2).</p>
<p>Hence, we can create a complete bipartite graph G = (U, V, E = (U x V)), where the vertices on the left side correspond to the cell A<sub>i</sub>'s, and the nodes on the right side correspond to the cell B<sub>j</sub>'s. The weight of the edge between A<sub>i</sub> and B<sub>j</sub> is the L<sub>1</sub>-distance between their cell positions.</p>
<p>One could use <a href="http://en.wikipedia.org/wiki/Hungarian_algorithm">Hungarian algorithm</a> to compute the min-weight matching, however it takes O (n<sup>3</sup>) time, and will run out of time. Hence, we need to use some heuristic to solve the problem approximately. One possibility could be start with a random matching and then use the path augmentation only a bounded number of times. Other possibility could be to start with a random matching and then swap the pair of matched edges when beneficial, i.e., if a matching has A<sub>i</sub> matched to B<sub>i</sub> and A<sub>j</sub> matched to B<sub>j</sub>, while c (A<sub>i</sub>, B<sub>i</sub>) + c (A<sub>j</sub>, B<sub>j</sub>) > c (A<sub>i</sub>, B<sub>j</sub>) + c (A<sub>j</sub>, B<sub>i</sub>), then we should match A<sub>i</sub> with B<sub>j</sub> and A<sub>j</sub> with B<sub>i</sub>.</p>
<h3>Finding the Target Configuration:</h3>
<p>In the previous section we have assumed that the target grid configuration is already known. In this section we will discuss how to find a "potential candidate" for the target configuration.</p>
<p>There are two main constraints:<br>
1) In the target configuration, all black cells must be connected, and<br>
2) Number of black cells in the target configuration should be the same as the number of black cells in the original configuration.<br>
Ideally, We would also like a target configuration, which is not "too far away" from the source configuration. Basically, we can pick a pivot cell, and then move all the black cells to this pivot cell, until they form a connected graph. This can be done using <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's algorithm</a></p>
<p>For example, let us assume that the position of black cells in the original grid were at position (0, 0), (1, 2), (1, 6), (3, 4), (3, 9), (5, 8), and we pick (3, 4) as a pivot point, then the process will follow as follows:</p>
<p>(3, 4) is already occupied, we have four locations, where a black cell can be moved so that it is connected to the so far constructed connected component. These locations are (2, 4), (5, 4), (3, 3), and (3, 5). Among these (3, 3) is closest to the any of the un-moved cells. Hence, we move (1, 2) to (3, 3).</p>
<p>Now, connected component has two cells (3, 4) and (3, 3). The free locations are (3, 2), (3, 5), (2, 3), (2, 4), (4, 2), (4, 4). Since (0, 0) is closest to (3, 2), it should be moved there.</p>
<p>The same process continues untill all black cells are moved to form a connected graph. The location of pivot is arbitrary. Ideally, the center of the grid should be the best location. However, if all the black cells are concentrated to one of the corners, then that corner might be a better choice. Once could try the center as well as the four corners of the grid as pivot, and pick the one which gives the best results.</p>
<h3>Addition/Removal of Black Cells May Help</h3>
<p>So far we have considered only the swap transformation. The operations of changing the color of a cell (or equivalenly addition or removal of black cells) are more expensive than the swapping transformation. However, they could be beneficial in some cases. If one black is too far away from the other set of black cells, which are close to one another, then it is better to remove the far away black cell rather than moving it to form a connected component.</p>
<p>These addition and removal transformation can be used as a secondary optimization. Compute the min-cost matching based on only the swap transformations, then iterate through the edges of the matching in decreasing order of the cost. If the cost of an edge is more than the cost of a remove transformation, and removing the corresponding cell from the traget configuration does not make it disconnected, then remove that cells corresponding to this edge from both source and target configurations. In a similar way, if the weigt of an edge (A, B) is more than the cost of add transformation, and it is possible to add a cell C to the target configuration while keeping it connected such that the c (A, C) < c (A, B), then one should add the cell A in the source configuration and C in the target configuration. The addition and removal process can be further tuned as seen in the setter's solution.</p>
<p>After doing these addition and removal transformations, the min-cost matching is applied again followd by possible addition and removal transformations. The process is repeated until the cost improves, or we run out of time.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2013/October/Setter/EDSTGRID.cpp">here</a>. <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2013/October/Tester/EDSTGRID.cpp">here</a>. </p>djdollsMon, 28 Oct 2013 00:43:05 +0530https://discuss.codechef.com/questions/27844/edstgrid-editorialchallengeedstgridoct13Why do i get a wrong answer?https://discuss.codechef.com/questions/28327/why-do-i-get-a-wrong-answer<p>// CODE DELETED</p>
<p>I've tested for several test cases and the answers are correct for those.
Link: <a href="http://www.codechef.com/NOV13/problems/SDSQUARE">http://www.codechef.com/NOV13/problems/SDSQUARE</a></p>gaurav9510Mon, 04 Nov 2013 14:48:05 +0530https://discuss.codechef.com/questions/28327/why-do-i-get-a-wrong-answerchallengei'm getting tle on the challenge problem when i submit the same solution i had submitted earlierhttps://discuss.codechef.com/questions/29395/im-getting-tle-on-the-challenge-problem-when-i-submit-the-same-solution-i-had-submitted-earlier<p>I got an ac yesterday in this submission <a href="http://www.codechef.com/viewsolution/2985422.">http://www.codechef.com/viewsolution/2985422.</a> But now i'm getting a tle when i try to submit the same solution and also my submission in the contest is also showing TLE.. how?</p>darkrayshiroThu, 14 Nov 2013 21:57:14 +0530https://discuss.codechef.com/questions/29395/im-getting-tle-on-the-challenge-problem-when-i-submit-the-same-solution-i-had-submitted-earliernovemberchallengetleProvide test cases for SEAVEChttps://discuss.codechef.com/questions/29533/provide-test-cases-for-seavec<p>As we all know, there have been significant changes in the challenge problem score after the rejudging. Many people(including me) are finding it hard to understand what led to such major changes and are not able to feel comfortable with this 20% rule. So I request <a href="/users/1/admin">@admin</a> to provide the test data for the problem SEAVEC, so that we can see for ourselves the reason for this and the participants who have suffered a major rank drop can get some closure.</p>sikander_nsitSat, 16 Nov 2013 15:38:30 +0530https://discuss.codechef.com/questions/29533/provide-test-cases-for-seavecadminchallengetest-casesseavecNOVEMBER LONG - SDSQUAREhttps://discuss.codechef.com/questions/28805/november-long-sdsquare<p>I have submitted so many solutions for SDSQUARE when i submitted two wrong answered solution both take 1.34s <a href="http://www.codechef.com/viewsolution/2953890">THIS</a> and 1.35s <a href="http://www.codechef.com/viewsolution/2954539">THIS</a> even though both are same and my right solution <a href="http://www.codechef.com/viewsolution/2959027">THIS</a> takes 2.01s in every submission. Why ?</p>smitshiluMon, 11 Nov 2013 17:42:16 +0530https://discuss.codechef.com/questions/28805/november-long-sdsquaresdsquarenovemberchallengeSEAVEC submissions not rejudged...!!https://discuss.codechef.com/questions/29144/seavec-submissions-not-rejudged<p>Hello, I don't think my submissions <a href="http://www.codechef.com/NOV13/status/SEAVEC,code_master01">http://www.codechef.com/NOV13/status/SEAVEC,code_master01</a>
have been rejudged.</p>
<p>The scores haven't changed at all and I get completely different scores on submitting the same solutions in practice section.</p>
<p><a href="/users/1/admin"><a href="/users/1/admin">@admin</a></a> please look into this at the earliest.</p>code_master01Wed, 13 Nov 2013 11:35:27 +0530https://discuss.codechef.com/questions/29144/seavec-submissions-not-rejudgednovemberchallengeseavecCan we track the progress of the rejudging for the challenge problem ?https://discuss.codechef.com/questions/28982/can-we-track-the-progress-of-the-rejudging-for-the-challenge-problem<p>Is there any way (for normal users) to track the progress of the rejudging of the submissions for the challenge problem? Moreover, I don't understand the order in which the submissions are being rejudged (it's definitely not chronological order). I am mostly interested in this month's challenge problem (Sereja and Vectors), but the question also refers to future challenge problems.</p>mugurelionutTue, 12 Nov 2013 12:06:03 +0530https://discuss.codechef.com/questions/28982/can-we-track-the-progress-of-the-rejudging-for-the-challenge-problemnovemberchallengeseavecWhy is the score for challenge problem changing?https://discuss.codechef.com/questions/28926/why-is-the-score-for-challenge-problem-changing<p>Why is the score for challenge problem changing after the end of the contest? If anything then it should have changed during the contest, so that one could make improvements on their scores! </p>v_akshayTue, 12 Nov 2013 00:21:24 +0530https://discuss.codechef.com/questions/28926/why-is-the-score-for-challenge-problem-changingnovemberchallengeMismatch of scores in SMPAINT submissions page and rank tab.https://discuss.codechef.com/questions/32009/mismatch-of-scores-in-smpaint-submissions-page-and-rank-tab<p>The scores in SMPAINT submissions page and in rank tab seems to be different. Is the rejudging over?</p>beethovenTue, 17 Dec 2013 14:47:20 +0530https://discuss.codechef.com/questions/32009/mismatch-of-scores-in-smpaint-submissions-page-and-rank-tabchallengesmpaintgetting WA for ERRORhttps://discuss.codechef.com/questions/37386/getting-wa-for-error<p><a href="http://www.codechef.com/problems/ERROR">question</a></p>
<p><a href="http://www.codechef.com/viewsolution/3277639">my solution</a></p>
<p>please give me a test case where my code fails</p>chitti2013Mon, 20 Jan 2014 22:18:55 +0530https://discuss.codechef.com/questions/37386/getting-wa-for-errorchallengepracticeruntime errorhttps://discuss.codechef.com/questions/41497/runtime-error<p>Guys my code is working fine in Ideone but here it is giving runtime error. Can anybody help</p>ishu1989singlaSun, 20 Apr 2014 23:26:46 +0530https://discuss.codechef.com/questions/41497/runtime-errorchallengeScoring problem with the Challenge problem (ANUMFS)https://discuss.codechef.com/questions/42554/scoring-problem-with-the-challenge-problem-anumfs<p>As you can see from the last submissions for the Challenge problem of MAY'14 long contest (ANUMFS), both me and <a href="/users/54486/aawisong"><a href="/users/54486/aawisong">@aawisong</a></a> submitted solutions which scored an absolute score of 0 (yes, that means we got the answer exactly right for each test case without the need of asking any question), which is the minimum possible.</p>
<p>However, it seems that the system cannot handle such scores and it ended up assigning a score of 0 to everyone. Of course, the correct ranking would assign full score to me and <a href="/users/54486/aawisong"><a href="/users/54486/aawisong">@aawisong</a></a> and a relative score of 0 for everyone else.</p>
<p>The issue is that the problem allowed the possibility to obtain 0 score per test case. My suggestion would be to fix this problem in one of two ways:</p>
<p>1) fix the scoring algorithm in the judge so that the minimum score per test case is > 0 (e.g. add 1 to the absolute score of every test case, or something smaller than 1, if you want, like 0.00001) - should be very easy to do and wouldn't change the relative order of the scores (it would simply add a fixed value to the score of each contestant)</p>
<p>2) fix the general scoring problem in the system, so that scores of 0 for minimization problems are handled correctly - this is probably more difficult to fix</p>mugurelionutMon, 12 May 2014 15:12:11 +0530https://discuss.codechef.com/questions/42554/scoring-problem-with-the-challenge-problem-anumfsanumfschallengeChallenge Problemhttps://discuss.codechef.com/questions/46681/challenge-problem<p>In the challenge problem say we submit 10 solutions that get scored differently .So which will be the score recorded in the system,the highest score we obtain or the last solution we submit ,though it has less score?</p>varuntinkleMon, 07 Jul 2014 12:19:04 +0530https://discuss.codechef.com/questions/46681/challenge-problemchallengeShould we have two challenge problems in Long Contest?https://discuss.codechef.com/questions/46784/should-we-have-two-challenge-problems-in-long-contest<p>Hello</p>
<p>100 hours into the July Long Contest, Top 10 scores are >=9.95.</p>
<p>I think having <strong>two</strong> challenge problems will make it more interesting!</p>yash_15Tue, 08 Jul 2014 18:03:11 +0530https://discuss.codechef.com/questions/46784/should-we-have-two-challenge-problems-in-long-contestchallengelong-contestwhen ratings will be updated ?https://discuss.codechef.com/questions/35367/when-ratings-will-be-updated<p>I recently started programming just 1 month back.
For the first time I participated in a contest "Jan challenge 2014" .. Getting excited to see my rating as surprisingly I solved a question in my first attempt(only 1) in such contests.. When it will be updated ?? </p>shantanu10Mon, 13 Jan 2014 15:17:32 +0530https://discuss.codechef.com/questions/35367/when-ratings-will-be-updatedratingscontestrankingschallengerankstartnewName reduction Query( May Challenge)https://discuss.codechef.com/questions/10167/name-reduction-query-may-challenge<p>I submitted this code and got WA. Could someone please tell me why I am getting WA despite it working perfectly in my computer.</p>
<p>Link to the problem:</p>
<p><a href="http://www.codechef.com/MAY13/problems/NAME1">Name reduction</a></p>
<p>Here is my code:</p>
<pre><code>//name red 2
#include<iostream>
#include<cstring>
#include<cmath>
#define l 42000
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
char a[l],b[l],c[l],alpha[27]={0};
scanf("%s",a);
scanf("%s",b);
for(int j=0;j<strlen(a);j++)
{
// a[j]=tolower(a[j]);
alpha[a[j]-'0'-97]++;
}
for(int k=0;k<strlen(b);k++)
{
//b[k]=tolower(b[k]);
alpha[b[k]-'0'-97]++;
}
int flag=0;
int n;
scanf("%d",&n);
while(n--)
{
scanf("%s",c);
// cin.ignore();
for(int i=0;i<strlen(c);i++)
{
alpha[c[i]-'0'-97]--;
if((alpha[c[i]-'0'-97])<0)
{
flag=1;
break;
}
}
}
if(flag==0)
printf("YES\n");
else
printf("NO\n");
}
}
</code></pre>
<p>The logic I am using is: I have created an array of size 26 corresponding to all the alphabets in English language. For each letter in parent, the count is incremented. Letter 'a' is array[0] and 'z' is array[25]. Then from each of the children I decrement the alphabets. As soon as a negative number appears in the array, NO is ouput, otherwise I output YES. Could someone please clarify why this code was leading to WA.</p>piy9Thu, 16 May 2013 17:52:05 +0530https://discuss.codechef.com/questions/10167/name-reduction-query-may-challengechallengewaGRAPHCH - Editorialhttps://discuss.codechef.com/questions/4209/graphch-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/GRAPHCH/">Practice</a><br>
<a href="http://www.codechef.com/NOV10/problems/GRAPHCH/">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>CHALLENGE</p>
<h1>EXPLANATION</h1>
<p>For small constraints, this problem can be modelled into a Linear programming problem with 2N variables [ 2 variables for co-ordinate of centre of each vertex : xi and yi ] with the Choose(N,2) constraints [ Each constraint for non-intersection of rectangles]. Now, we can use modified Simplex Algorithm to come up with a good solution.<br>
However, there are other approaches as well which can be taken for the problem. We can use divide and conquer to get a reasonable solution to the problem as well. Try breaking the set of vertices into 2 sets, so that the number of edges between the set is as low as possible. Now if you have a solution for each of the 2 sets, try placing the 2 sets adjacent in each of 4 directions and take the best option. This approach gives good results when dealing with squares.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/November/Setter/GRAPHCH.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/November/Tester/GRAPHCH.cpp">here</a>.</p>adminTue, 27 Nov 2012 18:15:32 +0530https://discuss.codechef.com/questions/4209/graphch-editorialchallengenov10graphcheditorialFAULT - Editorialhttps://discuss.codechef.com/questions/8121/fault-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/FAULT">Practice</a><br>
<a href="http://www.codechef.com/APRIL13/problems/FAULT">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/pieguy">David Stolp</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/laycurse">Hiroto Sekido</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/anton_lunyov">Anton Lunyov</a></p>
<h1>DIFFICULTY:</h1>
<p>CHALLENGE</p>
<h1>PREREQUISITES:</h1>
<p><a href="http://en.wikipedia.org/wiki/Bitwise_operation">Bitwise operations</a></p>
<h1>PROBLEM:</h1>
<p>The best described in the problem statement.</p>
<h1>EXPLANATION:</h1>
<p>The simplest solution is to output all servers. It will bring you only <strong>13.249427</strong> points, but you can even don't read distribution of chunks by servers :)</p>
<p>The second simplest solution that still allows you to not read distribution of chunks by servers is to output first <strong>S − N + 1</strong> servers. Thus, we left only <strong>N − 1</strong> servers. It is clear that it is impossible to recover all <strong>N</strong> chunks having only <strong>N − 1</strong> their combinations. Such solution brings you exactly <strong>10</strong> points and actually scoring function provides a hint to such solution :)</p>
<p>The third simplest solution is to iterate over all chunks, find the one that belongs to the least number of servers and output servers of this chunk. This will bring a better score <strong>6.378516</strong>. This works because after deleting these servers, the chosen chunk is not contained at any other server, so we can't recover it.</p>
<p>Now we consider the idea that allows to reach the high score.<br>
The input can be represented as <strong>S × N</strong> system of linear equations over the field <strong>Z<sub>2</sub></strong>. The variables are chunks and the right hand side is composed of servers. If <strong>A</strong> is the matrix of this system, then <strong>A[i][j] = 1</strong> if and only if chunk <strong>j</strong> is contained on server <strong>i</strong> (<strong>1 ≤ i ≤ S, 1 ≤ j ≤ N</strong>).</p>
<p><strong>Claim</strong>. <em>The chunks could be always uniquely recovered if and only if all <strong>N</strong> columns of this matrix are linearly independent over <strong>Z<sub>2</sub></strong>.</em><br>
Indeed, if columns are linearly independent, then using facts from basic linear algebra we can left only <strong>N</strong> rows of this matrix such that obtained <strong>N × N</strong> matrix is non-degenerate. Hence we can recover chunks by servers using inverse matrix. Now assume that columns are linearly dependent and their rank is <strong>K < N</strong>. Then we can left exactly <strong>K</strong> linearly independent rows in the system. It is well-known that such system has not-unique solution for every possible vector in right-hand-side.</p>
<p><strong>Thus, we need to delete as few rows as possible such that some column becomes a linear combination of other columns modulo 2.</strong> This, in turn, equivalent to performing series of elementary column operations such that some column becomes zero (in the matrix with deleted rows). Elementary column operation is simply a bitwise xor of columns if we consider them as binary numbers.</p>
<p>Instead of deleting some rows and then trying to reach zero column, we can do at first some elementary column operations and then for every column the set of rows we should delete to make this column zero is simply all rows having 1 in this column.</p>
<p>To achieve better performance we could represent columns as collection of 32bit unsigned variables and do bitwise xor 32 times faster (see bitset data structure in <a href="http://www.codechef.com/download/Solutions/2013/April/Setter/FAULT.cpp">author's solution</a>).</p>
<p>Now the simplest we can do is to perform random bitwise xors while time permits, check whether the column we change have less ones than the answer and update the answer if necessary. To count the number of ones at GNU C++ we can use fast built-in function <code>__builtin_popcount</code>. Otherwise we can precalculate popcount for numbers up to <strong>2<sup>16</sup></strong> and calculate popcount of 32bit number as a sum of popcount for its lower 16 bits and popcount for its higher 16 bits. Such solution could bring about <strong>4.89</strong> points.</p>
<p>Another method to use this idea is the following.<br>
At each step we select random <strong>1</strong> in the matrix. Let it be in the intersection of the <strong>i</strong>-th row and the <strong>j</strong>-th column. Then we do the step like in <a href="http://en.wikipedia.org/wiki/Gaussian_elimination">Gaussian elimination</a>. For each column <strong>k</strong> other than <strong>j</strong>, if the <strong>i</strong>-th element in the <strong>k</strong>-th column is 1 we replace <strong>k</strong>-th column by its bitwise xor with the <strong>j</strong>-th column. Also we check whether the updated <strong>k</strong>-th column has less ones than the answer and update the answer if necessary. We do these steps while time permits. Such solution could bring you about <strong>3.75</strong> points (note that the winner score is about <strong>3.60</strong>).</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2013/April/Setter/FAULT.cpp">here</a> but it get WA :) <br>
The corrected version is <a href="http://www.codechef.com/viewsolution/2056563">here</a> (the score of this submissions is <strong>3.745888</strong>).</p>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2013/April/Tester/FAULT.cpp">here</a>. </p>
<h1>RELATED PROBLEMS:</h1>
<p><a href="http://www.codechef.com/problems/IGNITE">IGNITE</a><br>
<a href="http://www.codechef.com/problems/CUCUMBER">CUCUMBER</a> </p>anton_lunyovMon, 15 Apr 2013 15:00:45 +0530https://discuss.codechef.com/questions/8121/fault-editorialfaultchallengegauss-elimbitwiseapril13editorial