Unofficial Editorials December Lunchtime

Hello Guys, I’m back with another set of editorials in hope you would like them. :slight_smile:

I hadn’t attended December Cook Off due to certain unavoidable circumstances, that’s the reason of no editorials for Cook Off.

Without wasting much time, Here are the editorials.

Days in a Month

Difficulty: Cakewalk

Problem:

Given number of days in month and Day as on 1st of given month, Find out frequency of each day.

Solution:

Simplest solution use if else statements (Carefully though).

For W = 28, print 4 for each day, because a month with 28 days will always have 4 Sunday, 4 Monday ans so on.

For W = 29, print 4 for all days except the day of first of month. Example, for input 29 mon, ans is 5 4 4 4 4 4 4. (frequency of monday increased by 1).

For W = 30, print 4 for all days except the day of first of month and its next day. Example, for input 29 mon, ans is 5 5 4 4 4 4 4. (frequency of monday increased by 1).

For W = 31, print 4 for all days except the day of first of month and next two days. Example, for input 29 mon, ans is 5 5 5 4 4 4 4. (frequency of monday increased by 1).

For proof of above, You may consult Calendar. :smiley:

Link to my


[1]

### Strange Function

#### Difficulty:Easy

### Problem:

Given A and N, compute $f(A^N)$, where $f(X)$ is defined as:

 -  Compute the sum of digits of A; let's denote this sum by S.
 - If S is a single-digit integer, then F(A) = S.
 - Otherwise, F(A) = F(S).

### Solution:

FIrst thing, make a function $f(X)$ as described above. Now, Notice that we need to calculate $f(ans)$ where ans = $A^N$, we can directly compute $f( (f(A))^N)$. Doing this avoids the issue of overflow.

**Typical Modular exponentation Code** (Refer [geeksforgeeks][2])
int power(int x, unsigned int y, int p)
{
    int res = 1;      // Initialize result
 
    x = x % p;  // Update x if it is more than or 
                // equal to p
 
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1){
            res = (res*x);
            if(res>=p)res = res%p;
        }
        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;  
    }
    return res;
}

Now, our solution is similar to modular exponentation, with one change. In Modular exponentation, we take res = (res*x); if res >= p, res = res%p;

But in our solution, we take res = res*x; $if(res >= 10) res = f(res)$. This way, we are calculating $f(A^N)$ in the same manner as Modular exponentation.

That's all.

Reason this works, is that suppose we have A = 15, N = 2.

$f((9+6)^2)  = f(6^2 + 9*(9+12)) = f(36 + 9*21)$

Now, notice that the term 9*21 will never affect the value of our function.

For further proof, Calculate $f(9*X + Y)$ for some values of X and Y. The answer will always be Y.

Link to my 

[3]

Too Much Sweetness

Difficulty: Easy-medium

Prerequisites: DP

Problem

Given two bags of sweets with p and q sweets respectively, Find out number of ways of eating Exactly N sweets, subject to conditions that

  1. ith bag cannot be opened more than Bi time.
  2. We cannot eat more than Si sweets in one step from ith bag.
  3. We need to choose bags alternatively.
  4. First bag can be either one.

Solution;

Usually for counting problems where we need to make choices and count the number of ways of some sequence, we use DP, taking all the variables affecting answer in dp state.

DP state for this problem has been defined as

  1. N = Number of sweets to be eaten.
  2. p = Number of sweets in Bag 1
  3. q = Number of sweets in Bag 2
  4. B1 = Number of times we can open Bag 1
  5. B2 = Number of times we can open Bag 2

Base Case if(N == 0) return 1; if (N < 0, )return 0.

DP recurrence

if(last == 1)dp[N][p][q][B1][B2][last] = Summation from i = 1 to i = min(q,S2)solve(N-i, p,q-i,B1,B2-1, 2);

if(last == 2)dp[N][p][q][B1][B2][last] = Summation from i = 1 to i = min(p,S1)solve(N-i, p-i,q,B1-1,B2, 1);

Now, see what;s going on.

In each recursive call, we eat i sweets from bag other than the last one, Reducing sweets to be eaten, also reducing Number of sweets in that bag, and reducing the max number of times of opening respective bag by one, Thus, meeting all conditions.

Also, we run loop from 1 to min(p, S1) and 1 to min(q,S2), to comply with the condition of max sweets at a single step.

Also, use map in place of arrays which may give TLE. we do not visit all states.

Further We can also reduce state variables from 6 to 5 by noticing that N = P - p + Q - q where P and Q are input values while p and q is the current state values. But is didn’t use it ad still it works. :slight_smile:

Here’s the link to my


[4].

Hope you all like my editorials.

On an important note, For further contests, One of my friend (@soham1234) has agreed to write unofficial editorials similar to mine. I hope you would like them too as much as you all do like mine.


  [1]: https://www.codechef.com/viewsolution/16703802
  [2]: https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/
  [3]: https://www.codechef.com/viewsolution/16707912
  [4]: http://codechef.com/viewsolution/16713650
22 Likes

Thanx!! Very nice editorial and congracts for 6*.

I think we could solve the 4th problem using persistent segment tree.Lets say we have 7 of them for each of the combination (001-111) where 0 represents not divisible ,and 1 represents divisible by 2,3,5 respectively.Now lets say for a node v i have a segment tree for a combination(lets say 001 - divisible by 5),so if we store the sum of valid edge cost at a node ,lets say there are edges of cost 5,5,3 from this node to root so segment[5:5]=10,segment[3:3]=0. This segment tree could be constructed from parent.So ansFromRootToNodeV can be obtained by simply searching for the range x:y in all combination of segment tree and adding it,where x,y can easily be calculated(as it is intersection ie for 011 it is intersection of x2,y2 and x3,y3).
So ans for u to v is ansFromRootToNodeu+ansFromRootToNodev-2*ansFromRootToNodeLCA(u,v)

1 Like

Too much Sweetness can be solved using basic Combinatorics as well! Just consider the cases of length of sequence and find out the number of the solutions of the equation formed using Multinomial and Inclusion - Exclusion!

2 Likes

i have done second question in O(1) link:-CodeChef: Practical coding for everyone

For the second question, i used the exact same code of mod exp from geeksforgeeks and got an AC :smiley:

Link to my solution.

what is the time-complexity of your dp solution?

Actually we can reduce it to 50^3 with 50^3 states using arrray (instead of map). The state must be like

  1. p left

  2. q left

  3. block number

  4. flag to indicate either first or second.

And now naively calculating each state takes O(50) time. But in a clever way computing prefix sums over previous level it can changed to O(1) since the dependency states are contiguous.I hope its clear.
Caveats in your states: B2 is redundant if B1 is there since it was required for them to be alternate.

2 Likes

I have explained by Combinatorics approach briefly for Too Much Sweetness below:

Let us say our sequence formed is x1y1x2y2…xkyk, where xi is the number of sweets taken out from first box in the ith turn, and similarly for yi. Notice here there are three other cases which can be similarly dealt with:

  1. y1x1y2x2…ykxk 2) x1y1x2y2…yk-1xk 3) y1x1y2x2…xk-1yk

Now we need to find the number of solutions to the equation for each k (max limit depending upon B1 and B2).

x1 + y1 + x2 + y2 + … + xk + yk = n

=> (x1 + x2 +… +xk) = n1 and (y1 + y2 +… + yk) = n - n1 such that xi ranges from 1 to S1 and yi ranges from 1 to S2.

This can be done using Multinomial and Inclusion and Exclusion. How?

Let us consider x1 + x2 + … + xk = n1, x1 can range from 1 to S1.
Now, take a substitution zi = xi - 1

So, z1 + z2 + … + zk = n1 - k, zi can range from 0 to S1 - 1(both inclusive)

Let us say there was no upper bound then by Multinomial we have number of solutions as NcR(n1 - k + k - 1, k - 1).
But there are some other solutions in which zi >= S1. So that can be removed from the answer by taking similar substitutions and Inclusion - Exclusion.

Code: CodeChef: Practical coding for everyone

10 Likes

4th problem can be solved using centroid decomposition. Let L be the lca of U and V in the centroid tree. So the path between U and V can be broken down into two parts, U to L and L to V. Also we know that the centroid tree has at most log(n) depth, so each node has atmost log(n) ancestors. We store information about the path between U and ancestors of U(say A). We store the cost of each edge between U and A in a vector v[U][A] and sort them. Then using binary search and prefix sums we can process each query in log(n).
Expected Time Complexity: log(n) per query with nlog(n) preprocessing.

1 Like

Thank you for the lovely editorials!
I too tried to memoize my recursive solution for the 3rd question, but got AC verdict only for the 1st subtask. The others were TLE and WA. Looking at your solution, I don’t find much difference in my approach. Maybe I missed a trick somewhere.Could anyone help me find the error in my code?

Here’s a link to my submission CodeChef: Practical coding for everyone

Thank you for the “Too Much Sweet” Editorial.

key = (B2 + 201*(B1 + 201*( q + 201*(p+201*(N)))))*2 + prev%2)

This line of your code got me into thinking if there would be any pair of tuples ( tuple1 = (B2,B1,q,p,N,prev) and

tuple2 = (B2’,B1’,q’,p’,N’,prev’) ) will collide i.e. if tuple1 and tuple2 under any condition will yield the same key?

Also How did you came up with very hash formula ? Is there any specific norm ?

Thanks for the editorial. I have a couple comments:

Strange Function

We can simplify a bit further if we need to. We observe that f(A) simply maps A to its equivalence class modulo 9 (just like A \mod 9, except multiples of 9 get mapped to 9 instead of 0). This is the key to the grade-school “divisibility by 9” check, and it is the reason why f(A^N) = f(f(A)^N). However, we can simplify even further.

  • If f(A) = 9, then f(A^N) = 9 for all values of N.
  • If f(A) \in \{3,6\} and N>1, then f(A^N) = 9, since A^N will be divisible by 9.
  • The remaining remainders \{1,2,4,5,7,8\} form a cyclic-group under multiplication of order 6. Thus, if we are not in the first two categories above, we can instead calculate f(f(A)^{(N\%6)}).

TL;DR,

  • If A is divisible by 3 and N > 1, print 9
  • Otherwise, just calculate ((A \mod 9) ^ {(N \mod 6)}) \mod 9. If the answer is 0, print 9, otherwise, just print that result.

Too Much Sweetness

(Full disclosure: my programming is rusty, do I didn’t get AC during the contest and only later in the afternoon (after debugging silly mistakes))

I used what I thought was perhaps a slightly more efficient approach than the one described. I also like it because the first half is a pretty generic piece of code that can possibly be used elsewhere. I broke the problem up into two parts:

  • I used DP and precomputed the ways to split up n objects into k non-empty partitions where each partition was no bigger than s. I stored these in a 3-D array (i.e. ways[n][k][s]).
  • I then used these to solve each query with a nested for loop per query (looping over the number of candies of type 1 and then the number of trips to the first box). After fixing these two terms, the number of candies of type 2 is determined, and there are only 3 possibilities for the number of trips to the 2nd box.

The thing I liked about this was that we could reuse the same DP result for both types of candies which kept the size of the DP down. The code seemed to execute several orders of magnitude faster than the time limit.

1 Like

@taran_1407 ‘Strange Function’ can be solved with O(1) with a bit of precomputation like @bhpra said. Basically, we need to find cycle for each value from 1 to 9 inclusive.


[1]


  [1]: https://www.codechef.com/viewsolution/16705694

EDIT - Yes it's complexity O(log(log(...(n))..)
1 Like

@taran_1407 Only two observations were to be made to solve the second question in O(1) time for each query.

  1. F(A^N) = F(F(A)^N)
  2. If the sum of digits of A is 1 or 9, the answer will always be the number itself. For 3 & 6, if N = 1, it will be the number itself. Else if N > 1, it will always be 9.
  3. For the remaining numbers 2, 4, 5, 7 & 8 we just needed to find the cycle after how many multiplication the sum of digits will start repeating.

Here is the link to my solution which runs in constant time for all the subtasks.

1 Like

I need some help in question “Too much sweetness”. I have implemented it in similar way as explained in editorial, but getting WA even for subtask#1.

My code is: [CodeChef: Practical coding for everyone][1]

Thanks in advance!!
[1]: CodeChef: Practical coding for everyone

@taran_1407: can u plzz explain this briefly

we can directly compute f((f(A))N). Doing this avoids the issue of overflow.

@sukhbir947 your logic and approach to the problem is wrong… it will give wrong answers in some test cases like these…

1
2 3 5
2 2
1 1

please dry run it and then check your logic… :smiley:

can someone please explain me the O(50^3) solution of 3rd problem. I had read the comments above but didn’t get it! please help.

Hii there,in the Question “Too Much Sweetness”, during the contest I tried this approach
Algo:

  • Generate all the 2^N permutations containing 1 and 2.
    -check every permutations if it satisfies all conditions
    if yes cnt++;

this approach has Time complexity = O(2^N)
for subtask 2, N=p+q<=20 so TO(2^N) = 10O(2^20) = 10^7(approximately)
so this solution should pass subtask 1 and 2.
But my solution is clearing only subtask1 and give TLE for the second.
my code :CodeChef: Practical coding for everyone
Plz help me to rectify this.

@taran_1407 ur editorials are easy to understand than most others
too much sweetness u explained in just 2 lines …