TTUPLE - Editorial

editorial
, , , , ,
149

Same here.
https://www.codechef.com/viewsolution/34482259

150

Were you able to solve? If yes can you share test case which was failing for subtask 1? Thanks.

151

The problem was to reach (a, b, c) from (p, q, r) in minimum number of steps. Therefore, I used recursion + shuffling approach. I created an ArrayList (vector in C++) of pairs (p, a), (q, b) and (r, c). For every iteration, I tried 3 operations:

  1. Addition operation:
    a. Resolve the first pair using addition operator. Let’s call the difference ‘diff’
    b. Added this ‘diff’ value to the first pair, and called the recursive function for the next iteration.
    c. Added the ‘diff’ value to the second pair and again, called the recursive function.
    d. Finally, added the ‘diff’ value to the third pair and performed recursion.

Code Snippet:

Collections.shuffle(p);                // p = ArrayList of pairs
long diff = p.get(0)[1] - p.get(0)[0];
p.get(0)[0] += diff; attempt(p, movesSoFar + 1);
p.get(1)[0] += diff; attempt(p, movesSoFar + 1);
p.get(2)[0] += diff; attempt(p, movesSoFar + 1);

  1. Multiplication operation:
    Code snippet:

     Collections.shuffle(p);
 if (p.get(0)[0] != 0 && p.get(0)[1] % p.get(0)[0] == 0) {
     long fac = p.get(0)[1] / p.get(0)[0];
     p.get(0)[0] *= fac; attempt(p, movesSoFar + 1);
     p.get(1)[0] *= fac; attempt(p, movesSoFar + 1);
     p.get(2)[0] *= fac; attempt(p, movesSoFar + 1);
 }

  2. Finally, the tricky part, tricky multiplication:
    Here, I tried to solve the cases which required a tricky way to solve. For example (2, 3, 7) and (17, 22, 42). [(2, 3, 7) * 5 = (10, 15, 35) and (10, 15, 35) + 7 = (17, 22, 42)]. These cases are handled by solving any two equations simultaneously. The value to multiply came as (m = m = (a - b) / (p - q)). I tried to multiply this value and execute the recursive function again.

Code snippet:

// For pairs (a, x) and (b, y), m = (x - y) / (a - b)
long abDiff = p.get(0)[0] - p.get(1)[0], xyDiff = p.get(0)[1] - p.get(1)[1];
if (abDiff != 0 && xyDiff % abDiff == 0) {
    long m = xyDiff / abDiff;
    p.get(0)[0] *= m; attempt(p, movesSoFar + 1);
    p.get(1)[0] *= m; attempt(p, movesSoFar + 1);
    p.get(2)[0] *= m; attempt(p, movesSoFar + 1);
}

Pruning: The recursive calls are arrested as soon as ‘moveSoFar’ value exceeds the current best ‘ans’ value.

1 Like
152

This is quite good and dealing with all cases can be avoided by randomization. Thank you for this. :blush:

1 Like
154

Which maths concept did you use?

155

See…you can easily handle the cases where only one or zero operations are required…the question’s hard part is identifying how can we identify all the cases that can be handled using 2 operations…Now you can have 4 types of ordering…

  1. add & add
  2. multiply & multiply
  3. add then multiply
  4. multiply then add

If you observe carefully the first 2 orders can be only possible if addition required by one of the value is the sum of other two which is a very easy check and similarly second is possible iff mutliplication required by one of the values is product of other two. Now comes the logical part…
case 3 of add then multiply
suppose the initial values are a1,b1,c1 and target values are a2,b2,c2
now you see in this case you are first adding then multiplying so it can be represented in the form of this equation…
(a1+s)*p=a2
(b1+s)*p=b2
(c1+s)*p=c2
(s is some value to be added and p is some value to be mutliplied)
these are equations of some lines and you can find the point of intersection of these lines and check it with third
same is the case with a1 * p + s=a2.
here is my submission which got me AC
https://www.codechef.com/viewsolution/34128963
p.s ignore the function is2PossibleBF() it is brute force approach for first test case

1 Like
156

I am a beginner and i m unable to understand this line in code
FORE(mask,1,7)… in post contest editorial session i understood it is for making subsets… but exactly how? pls explain

1 Like
157

I initially solved with conditions including zeros; but later I removed them thinking it would wouldn’t affect my code, and I was wondering why I keep getting a wrong answer.
All your test cases, except those with zeros, pass through my code.
Thanks

2 Likes
158

See if this helps.

https://www.youtube.com/watch?v=1tYoQx2LZDE

2 Likes
159

Hey pavan! could you also tell what should be the answer for each case.

160

Thanks for the detailed explanation <3 , I did it using similar approach but wasn’t able to debug after it was getting Wrong Answer

1 Like
161

One of those codes where you just see #include<> and coffin dance music starts playing in your mind.

162

Happy to help :upside_down_face:

163

Hello Geeks,
Can anyone help me to understand what is the use of this line in editorials solution?
FOR(j,3)if(mask&(1<<j))all.pb(j);

1 Like
164
  • Perform that operation, and call the function itself with the new parameters. … y we have to do this?
165

it is used to create different subsets from this set of initial values(a1,a2,a3) . u can read more here . it’ll help
Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique cap to every person) - GeeksforGeeks

https://www.geeksforgeeks.org/power-set

167

why does this not allow me to submit, like other contest questions show the

submit (practice)

button…so why is it that I cannot do the same for these questions

168

Worst problem seen on Codechef. Actual solution so specific and another solution (which most have done) take days to implement. Didn’t expected this type of problem. Long Challenge doesn’t mean that you will make problem that take days to implement. We are not here to do donkey work.

169

They solved it by doing donkey work i.e., by handling every case separately. This is not that I expected from CodeChef. These type of problems take days to implement.

170

Well it depends, ranked 1 user of div 2 solved it in less then 80 lines.
Also few questions are always there which are debatable. Though i did expected a neat solution.