April 2012 Contest Problem Editorials

Problem Tester for the contest was Hiroto Sekido.

Find a special connected block (written by shangjingbo). The Editorials can be found here.

Double Strings (written by Sergey Kulik). The Editorials can be found here.

Greatest Dumpling Fight (written by ishani parekh). The Editorials can be found here.

Lucky Array (written by Vitaliy). The Editorials can be found here.

Stacking Pancakes (written by Kaushik Iska). The Editorials can be found here.

Parallel Computing (written by Tomaz Hocevar). The Editorials can be found here.

PDS Number (written by Anh Duong Quang). The Editorials can be found here.

Fit to Play (written by Vamsi Kavala). The Editorials can be found here.

Similar Graphs (written by David Stolp). The Editorials can be found here

Substrings on a Tree (written by Sergey Kulik). The Editorials can be found here.

Comments

I could not understand the

dpraveen @ 11 Apr 2012 03:12 PM
I could not understand the approach behind PDS by editorial , please help me to understand underlying dp ,, thank you ,, I had all the abstract ideas as mentioned in approach ,,, So more details about dp will be helpful

and one thing that I really

dpraveen @ 11 Apr 2012 03:24 PM
and one thing that I really think that can be improved in codechef , Solutions written by writers and testers are never commented ,, Commenting them might help others to understand code better ,,

The sequence generated in

Manoharprabhu @ 11 Apr 2012 05:05 PM
The sequence generated in Pancake stacking problem is also called Bell numbers.. http://en.wikipedia.org/wiki/Bell_number

Can you elaborate a bit more

sukun007 @ 11 Apr 2012 05:26 PM
Can you elaborate a bit more on the PDS question, on the underlying DP?

i tried to do panstack by

akshaydixi @ 11 Apr 2012 05:56 PM
i tried to do panstack by generating the bell numbers but got tle... any idea how to pull it off??

@Admin:will u please explain

solve @ 11 Apr 2012 06:03 PM
@Admin:will u please explain lil bit more for PDS problem..Thanks.

Explain more about PDS

gauravkatoch @ 11 Apr 2012 06:49 PM
Explain more about PDS problems admin

@akshaydixi i just

Manoharprabhu @ 11 Apr 2012 06:52 PM
@akshaydixi i just constructed the bell numbers till 1000 as specified in wikipedia and answered each query in constant time

use memoization. save results

gargnitin123 @ 11 Apr 2012 06:58 PM
use memoization. save results 1000th number then keep returning answeres

Please provide more explan.

rukawa @ 11 Apr 2012 07:02 PM
Please provide more explan. about PDS no.

anyone please explain PDS

gargnitin123 @ 11 Apr 2012 07:04 PM
anyone please explain PDS Number Solution in detail.

@PDSNUM: The simplest

anhdq_adm @ 11 Apr 2012 07:19 PM
@PDSNUM: The simplest solution to calculate G function is: 1. Parse X to string A of length L, 2. Choose respective possible sum of digits - D to calculate G function, 3. With a chosen sum D, let G(i, k, s, p) be number of PDSnums which is constructed from position i (from left); k = true/false whether constructed part [1..i - 1] is less than part of A[1..i-1] of not; sum of digits is s & product of digits is p. 4. To calculate G(i, k, s, p), we consider: which digit used to build the i-th digit, foreach we calculate the new DP status (i', k', s', p') with i' = i+1; k' = (k' || chosen digit < A[i]); s = s + chosen digit and p = p * chosen digit. Take some simple optimization: there is just around 40 possible sums of digits; just store p by remainder when dividing it to D... and some more than you will get the suitable running time

about PANSTACK: the dp

cyberax @ 11 Apr 2012 07:53 PM
about PANSTACK: the dp computation is the way of computing Bell numbers. http://en.wikipedia.org/wiki/Bell_number

@admin: Can you please

jadaayu @ 11 Apr 2012 08:06 PM
@admin: Can you please explain the CONNECT problem's solutions a bit more?

Please give more explanation

javadecoder @ 11 Apr 2012 08:26 PM
Please give more explanation on solution for CONNECT

I think that editorial

dpraveen @ 11 Apr 2012 09:17 PM
I think that editorial writers should understand that guys who see the editorial are the one who have tried to solve the problem for quite some time , So just giving abstract approach do not work ,, because this is somehow they find out theirself ,, So editorial should properly explain every step ,,,which is missing in this editorial ,, ,, hope that this will be updated soon ,,,

can you give the wiki link

flingo_1992 @ 11 Apr 2012 09:39 PM
can you give the wiki link as mentioned in article on parallel please?

is catalan number not the

ashmish2 @ 12 Apr 2012 12:48 AM
is catalan number not the solution of panstack problem

@dpraveen:Agree with

solve @ 12 Apr 2012 01:32 AM
@dpraveen:Agree with you.editorials generally seen by those students who have attempted that problem but was not able to crack it. so now expectation is somewhat elaborative.also code provided in editorials is really hard to understand it as they dont have any comment. thanks:)

Just curious, for the problem

bloops @ 12 Apr 2012 04:11 AM
Just curious, for the problem CONNECT how do you know that problem setters solution produces the correct answers? Or were the testcases hand-crafted?

For SIMGRAPH ,, Can you show

dpraveen @ 12 Apr 2012 10:08 AM
For SIMGRAPH ,, Can you show some kind of proof that doing a random labelling and then making some changes into it to get more accurate results works , >> thanks :)

It seems to me that solution

betlista @ 12 Apr 2012 12:24 PM
It seems to me that solution for CONNECT assumes that there are k distinct numbers in matrix, but it is not true, we have to find block with at least 7 distinct numbers but such block can be bigger than n*m/2. n = 5 m = 5 K = 7 1 2 3 4 5 -1 -1 -1 -1 6 6 6 6 6 6 6 -1 -1 -1 -1 6 6 6 6 7

i tried PARALLEL but could

timedout @ 12 Apr 2012 11:02 PM
i tried PARALLEL but could not solve within instruction constraints of max 2000, more explanation is required than what's present here.

Can anybody explain his idea

javadecoder @ 13 Apr 2012 01:29 AM
Can anybody explain his idea with reference to his solution for problem CONNECT ?? ,(i haven't received any response for my previous comment) ..,somebody please help...

@javadecoder @betlista

triplem @ 13 Apr 2012 05:28 AM
@javadecoder @betlista Suppose you replace all the 1s in the matrix by a random number between 1 and K (call it r[1]), replace all the 2s in the matrix by a random number between 1 and K (r[2]), .. all the 225s in the matrix by a random number between 1 and K (r[225]). Suppose the best block in the original matrix covers the positive integers a1, a2, .., aK. In the new matrix, it covers the positive integers r[a1], r[a2], .., r[aK]. If those are all different, when we solve the new matrix we will find the solution. There are K^K ways of choosing what r[a1] through r[aK] are, and K! ways where they end up all different. So we will find the best solution with probability at least K!/K^K. When K is 7, that is about 0.006. If we do that 10000 times, the probability we never find the best solution is <= (1-0.006)^10000 = 0.00000000... Thus all you have to do is know how to solve the new matrix where there are only numbers from -1 to K, which you can do with DP/shortest-path.

hey the problem setter's code

fmm @ 13 Apr 2012 06:22 AM
hey the problem setter's code could only run about 200 times (rounding it up) respecting the time limit of 7.0 seconds (at least with some input I created), so the probability of get wrong in that case is (1-0.006)^200 = 0.300107521, quite big...

admins: Could you give a link

acube @ 13 Apr 2012 08:47 AM
admins: Could you give a link for the tricky test case for problem PLAYFIT?

@triplem: Thanks a lot,now I

javadecoder @ 13 Apr 2012 12:34 PM
@triplem: Thanks a lot,now I get the solution .... :)

In the setter's solution for

dr_go_fast @ 13 Apr 2012 09:57 PM
In the setter's solution for Similar Graphs what does this condition check?? (cost<4 && (rand()%100)<4-cost)

Problem: DUMPLING FIGHT

rajneesh2k10 @ 13 Apr 2012 10:06 PM
Problem: DUMPLING FIGHT (DUMPLING) In setter's solution, in function "lcm", why the multiplication "1LL*a*b" is done? How a simple "a*b" is different from "1*a*b" , when 'a' and 'b' are already defined as long long?

@rajneesh2k10 yes you are

isha_adm @ 13 Apr 2012 10:31 PM
@rajneesh2k10 yes you are correct in saying that. There is no need for the extra 1ll in the product.

Problem: DUMPLING FIGHT

satya_patel @ 14 Apr 2012 12:59 AM
Problem: DUMPLING FIGHT (DUMPLING) let x=gcd(A,B) and y=gcd(C,D) now i calculate lcm=x*(y/gcd(x,y)). i m using signed long long here if this cross the limit of long long then it will be in minus so ans should be 1 as K<=10^18 or ans=2*K/lcm+1 ok..........this giving me WA...............but when i write ans=(K/(x/gcd(x,y)); ans=ans*2+1; this gives me Accepted...............any one can explain it???

@satya_patel x and y can fit

isha_adm @ 14 Apr 2012 01:35 PM
@satya_patel x and y can fit into signed long long integers. But their lcm may not fit into signed long long. It may overflow to give you undefined results ( can be positive or negative ).

@isha_adm as x and y can not

satya_patel @ 14 Apr 2012 02:25 PM
@isha_adm as x and y can not more than 10^18 so gcd(x,y) will not be more than 10^18 so that y/(gcd(x,y)) also will not be more than 10^18 so when it is multiplied with x which is not more than 10^18 will be overflow the limit of long long but it can be negative after overflow but can not be positive.....................am i missing something???

Take the case x=10^18, y=999;

isha_adm @ 14 Apr 2012 02:38 PM
Take the case x=10^18, y=999; Their lcm overflows and is positive when stored in signed long long. Product of 10^18 and 10^18 is negative because of many overflow cycles. Thus overflow depends on the input too and not just the limits of the input variables.

@Isha..........ok now got

satya_patel @ 15 Apr 2012 03:27 PM
@Isha..........ok now got it....thanks....:)

k' = (k || chosen digit <

bhanuism @ 15 Apr 2012 06:56 PM
k' = (k || chosen digit < A[i]); please help me to understand this when k is false !!

"let G(i, k, s, p) be number

bhanuism @ 15 Apr 2012 07:05 PM
"let G(i, k, s, p) be number of PDSnums which is constructed from position i (from left); k = true/false whether constructed part [1..i - 1] is less than part of A[1..i-1] of not" Can u explain it with an example, which part of the string is denoting the PDS number and how the value of k is being updated??

@ashmish2: no it is not, for

sourabh912 @ 15 Apr 2012 08:15 PM
@ashmish2: no it is not, for example for n=4 there are 15 possible combinations instead of 14 (1,1,1,1),(1,1,1,2),(1,1,2,1),(1,1,2,2),(1,1,2,3),(1,2,1,1),(1,2,1,2),(1,2,2,1),(1,2,2,2),1,2,2,3),(1,2,3,1),(1,2,3,2),(1,2,3,3),(1,2,3,4) and (1,2,1,3)

admin: Could you give a link

acube @ 15 Apr 2012 08:22 PM
admin: Could you give a link for the tricky test case for problem PLAYFIT or explain it?

@admin: Problem LUCKY4

sourabh912 @ 16 Apr 2012 12:30 AM
@admin: Problem LUCKY4 involves finding k-th minimal sequence. Can you elaborate the idea of how to find such k-th sequence in general in a bit more detail?

@triplem: thanks for hint

betlista @ 16 Apr 2012 12:16 PM
@triplem: thanks for hint

@admin: the solutions are not

nnimish19 @ 17 Apr 2012 05:37 PM
@admin: the solutions are not visible(if they were uploaded)! i could just see the comments

where are the

saayaa @ 18 Apr 2012 12:14 PM
where are the editorials.....just the comments available...???

check out this link:

kq_viet @ 18 Apr 2012 12:17 PM
check out this link: http://www.codechef.com/node/1062815/revisions/1064751/view I dont know why @@.