May 2012 Contest Problem Editorials

Problem Tester for the contest was Subrahmanyam Velaga.

A Home for Chef (written by ishani parekh). The Editorials can be found here.

Lucky lucky number (written by ishani parekh). The Editorials can be found here.

Killing Gs (written by Hiroto Sekido). The Editorials can be found here.

Digits Forest (written by Anh Duong Quang). The Editorials can be found here.

Divisible Pairs (written by Tasnim Imran Sunny). The Editorials can be found here.

Little Elephant and Boxes (written by Vitaliy). The Editorials can be found here.

Little Elephant and Median (written by Vitaliy). The Editorials can be found here.

Jewels and Stones (written by Nikhil Garg). The Editorials can be found here.

Selling Tickets (written by David Stolp). The Editorials can be found here.

Remember the recipe (written by Kaushik Iska). The Editorials can be found here.

Comments

There is a polynomial time DP

KADR @ 11 May 2012 03:51 PM
There is a polynomial time DP solution for the problem MEDIAN. However its complexity is O(N^5) which is slower than the author's one with such a small constraints on N.

What is meaning of DP?

mayank2k11 @ 11 May 2012 04:45 PM
What is meaning of DP?

Does f[i,j,k] means something

rubanenko @ 11 May 2012 05:19 PM
Does f[i,j,k] means something like minimum expenses of making k 1-bits on i..j segment? Please, tell your idea if it's not simillar.

@KADR: Don't you forget stop

iscsi @ 11 May 2012 05:28 PM
@KADR: Don't you forget stop your script to send cockroach? :)

@rubanenko: Yep, exactly.

KADR @ 11 May 2012 06:05 PM
@rubanenko: Yep, exactly.

@iscsi: Actually, I was

KADR @ 11 May 2012 06:09 PM
@iscsi: Actually, I was trying to reach 24.0 at least in the archive. But seems it's going to take a while.

@mayank2k11-it's dynamic

ridder @ 11 May 2012 06:11 PM
@mayank2k11-it's dynamic programming.

@KADR I'm just kidding :),

iscsi @ 11 May 2012 06:27 PM
@KADR I'm just kidding :), but I'm amazed at how hard you are working. I feel little bit missing we cannot see the best score.. Congratulate you it was a very interesting and exciting contest. For the cockroach I make some greedy at the beginning of the contest for use the best improvement direction. I don't have too much time, so at the end I just make some hacking on this solution, but I feel If make some beam search on this greedy it would made some improvement (my current best was 23.15~ and I feel it would maybe 23.5), but I don't start because I feel I don't have time to debugging :(

For the cockroach part I

iscsi @ 11 May 2012 06:41 PM
For the cockroach part I would like to write everybody but this page don't like new lines :)

I think Problem Setter's

venkateswarlu @ 11 May 2012 06:42 PM
I think Problem Setter's solution TWSTR has one small problem i.e in the implementation of trie ins method wont work properly because of node->ch[index] = ins(node->ch[index], p+1) stmt causes node->ch[index] for last element in the string to be intialized to NULL. so there is no way detecting last element in the string.

In problem DIGFORST ,if we

javadecoder @ 11 May 2012 06:52 PM
In problem DIGFORST ,if we apply dijkstra ,then at every iteration any state with minimum sum is allowed to be extracted or only the valid ones,(Valid means that for (N,d*,r*) , *r is divisible by all digits detected in *d )

For DIGFOREST, my Dijkstra

pragrame @ 11 May 2012 08:20 PM
For DIGFOREST, my Dijkstra solution was timing out, so I had to use a BFS implementation (since the distance was atmost 7, its like i enumerated 6 intermediate vertices).

@javadecoder: any state,

anhdq_adm @ 11 May 2012 08:51 PM
@javadecoder: any state, because an invalid state may cause a valid state later. @pragrame: yes, using BFS or Bellman-Ford with queue will help you improve the solution

when will the editorials for

yjain35 @ 11 May 2012 11:03 PM
when will the editorials for the remaining problems come?

Problem tester solution for

iscsi @ 12 May 2012 01:42 AM
Problem tester solution for the TICKETS looks for me very nice, I really like that c++ style.

I think I found a simple

lg5293 @ 12 May 2012 02:28 AM
I think I found a simple O(N^4) solution for MEDIAN. Look at my solution: http://www.codechef.com/viewsolution/1006179 (I haven't completely proved why it works, but if you want to fill a segment [i,j] with all 1's, you only need to find one sub-segment [k,l] and fill that in, so you don't need to consider filling in two disjoint sub-segments since that is never optimal).

I used the same approach as

bodmas @ 12 May 2012 03:26 AM
I used the same approach as explained here for the TWSTR problem but i kept getting TLE. i guess the time limit for java wasn't fair enough.

can anyone explain the

just_code_it @ 12 May 2012 06:28 AM
can anyone explain the concept behind DIVPAIR

TWSTR can be solved by first

ambujpandey @ 12 May 2012 08:33 AM
TWSTR can be solved by first sorting all the strings and then applying binary search for each query.

Would come please explain the

monish001 @ 12 May 2012 11:21 AM
Would come please explain the algorithm for the CHEFHOME problem? Or atleast give some links.

Strange to see setter's

javadecoder @ 12 May 2012 12:37 PM
Strange to see setter's solution time out in DIGFORST .

although i solved DIVPAIR,but

solve @ 12 May 2012 01:17 PM
although i solved DIVPAIR,but i dont think my implementation was good(Too tedious). Anybody tell me the short approch. my idea was to use AP's sum.Any sujjestion regarding my Java code. http://www.codechef.com/viewsolution/1035209

@javadecoder: it's not

anhdq_adm @ 12 May 2012 06:45 PM
@javadecoder: it's not strange at all :) my uploaded solution is a clear version so everyone could get the idea to solve. You might see a very nice solution of the tester with lots of useful improvements.

I'm satisfied with my

bodmas @ 13 May 2012 03:20 AM
I'm satisfied with my implementation for DIVPAIR since its O(1). Pls can someone explain the concept behind solving the DIGFORST problem, am not clear with the explanation given here. PS: I'll like to suggest that it will be nice if members could inbox themselves here on codechef. I think it's gonna be nice:)

ok

cool123 @ 13 May 2012 12:59 PM
ok

First try to solve the 1-D

cool123 @ 13 May 2012 01:01 PM
First try to solve the 1-D version. You have N integer points marked on a number line, the point(s) that minimze the sum of the distances from all the points lie between the median points. Plz can any one expln hw this works.

@everyone: i tried Trie

solve @ 13 May 2012 01:19 PM
@everyone: i tried Trie implementation for "TWSTR" in java but i got too many TLE's .then i tried bruteforce approch and it passed. could anyone point out me where is the problem in my code . http://www.codechef.com/viewsolution/1008542

LOL :D .. looks like i coded

Manoharprabhu @ 13 May 2012 04:47 PM
LOL :D .. looks like i coded an unnecessarily complicated solution for DIVPAIR ... http://www.codechef.com/viewsolution/1020654

when do we add a vertex to

s1a3 @ 13 May 2012 07:44 PM
when do we add a vertex to queue in digit forest problem?

TWSTR is nice problem, but

Oleg @ 13 May 2012 10:45 PM
TWSTR is nice problem, but obviously has very weak test cases - http://www.codechef.com/viewsolution/999340 with O(N*Q*len(Qi)* len(Qi)) - comes 8th. Test case with 1000 same "abc" recepies and 1000 "abc" queries will kill all 10 top solutions.

I implemented trie for TWSTR

betlista @ 14 May 2012 04:44 AM
I implemented trie for TWSTR in Java and got TLE :-(

@s1a3: any time you visit an

anhdq_adm @ 14 May 2012 10:04 AM
@s1a3: any time you visit an unvisited vertex or be able to reduce the sum (min path) of a visited vertex

It stands for Dynamic

vipul4vb @ 14 May 2012 10:31 AM
It stands for Dynamic Programming...

For the Problem Digit Forest,

neeraj080 @ 14 May 2012 01:24 PM
For the Problem Digit Forest, how will u decide that no S is possible?

@admin: Please upload the

sourabh912 @ 14 May 2012 01:56 PM
@admin: Please upload the editorial for DIVPAIR soon or can anyone explain the logic of this problem.I have a very vague idea.

@neeraj080: there are 5M

betlista @ 14 May 2012 08:28 PM
@neeraj080: there are 5M states you have to check, if you check all and find no answer, there is no such string, so -1.

b0mb3r has nice observation

betlista @ 14 May 2012 08:34 PM
b0mb3r has nice observation (http://discuss.codechef.com/questions/654/even-setters-solution-for-digf...) about DIGFORST problem...

@neeraj080: after you apply

anhdq_adm @ 14 May 2012 09:02 PM
@neeraj080: after you apply shortest path algorithm to your graph and you still get a infinity distance to the target so it's "no solution". @betlista: this problem had been mentioned before, please check out the comments :)

please upload divpair

lalit1991 @ 15 May 2012 06:14 PM
please upload divpair solution

please tell me when u upload

cool123 @ 15 May 2012 08:40 PM
please tell me when u upload 4 divpair :)

@admin, It seems a lot of

ricola86 @ 16 May 2012 12:59 AM
@admin, It seems a lot of people including myself would like to see an editorial for the divpair problem. Much appreciated.

@All: The editorials for

admin @ 16 May 2012 02:43 PM

@All: The editorials for DIVPAIR has been uploaded. We apologize for the delay.

@lalit1991: The solution for

admin @ 16 May 2012 02:44 PM

@lalit1991: The solution for DIVPAIR is already uploaded, can u please specify f you are looking for something else?

I'm getting WA for "Killing

betlista @ 16 May 2012 04:11 PM
I'm getting WA for "Killing Gs" problem (http://www.codechef.com/problems/CKROACH/), see the forum for details please - http://discuss.codechef.com/questions/670/killing-gs-wa.

@admin no,thnx:)

lalit1991 @ 16 May 2012 06:51 PM
@admin no,thnx:)

@All : Anyone who got

solve @ 18 May 2012 12:24 AM
@All : Anyone who got accepted TWSTR using Trie in Java..?

@CHEFHOME, we need the median

siddharth10246 @ 18 May 2012 06:16 PM
@CHEFHOME, we need the median but why we have done: int dx = x[n/2] - x[n/2-1] + 1; I mean why we subtracted 2 VALUES(not dealing with pos) and added 1. (and yes i am new here)

@siddharth10246 in CHEFHOME

betlista @ 18 May 2012 07:31 PM
@siddharth10246 in CHEFHOME we are looking for locations with minimal distance sum, so when you have sequence 1, 2, 3, 4 the locations with such property are 2 and 3. If you have another ordered sequence 5, 10, 15, 20, the locations with minimal distance sum are all from [10;15] - 6 values, that's 15 - 10 + 1 and indexes of 15 and 10 are x.length/2 and a.length/2-1 for even x.length.

@betlista thanks :-)

siddharth10246 @ 18 May 2012 09:42 PM
@betlista thanks :-)

is CHEFHOME not related to

neo_aryan @ 19 May 2012 01:56 PM
is CHEFHOME not related to all pair shortest path problem and how can we differentiate between both ie when to use median technique and when to use all pairs shortest path

Can someone explain MEDIAN a

dumb @ 19 May 2012 05:26 PM
Can someone explain MEDIAN a bit better?? I am not able to get...

median is a term applicable

neo_aryan @ 19 May 2012 10:00 PM
median is a term applicable for sorted array .... its the central item of a sorted array.. it is used in statistical mathematics .... so if there are 7 terms in an array.. median is the middle element ie 4th element in the sorted array.. if there are 8 elements then average of 4th and 5th both elements are taken in consideration... if there value is v4 and v5 then median i(s v4+v5)/2.. also check this link http://www.mathsisfun.com/median.html

@neo_aryan: dude I was

dumb @ 20 May 2012 10:54 AM
@neo_aryan: dude I was talking about the problem MEDIAN, not the mathematical median that you explained! ;)

@Admin: in ckroach problem

satya_patel @ 27 Jun 2012 09:00 AM
@Admin: in ckroach problem why log(probabilities) instead probabilities................???