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

I have never implemented Persistent Segment Tree. So, it would be better if you could either share your approach in detail, possibly accompanied by implementation if possible.

PS: Thanks

Sorry i too couldn’t implement it due to lack of time,if u wanna read it refer this: https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/

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

Didn’t expect a Combinatorics solution for this problem.

i have done second question in O(1) link:-https://www.codechef.com/viewsolution/16717619

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

Link to my solution.

To understand it more clearly,u could assume that there are N segment trees for each combination (1 for each node) where N is the number of nodes in tree which store the valid edges along the path from root to that node.Persistent just helps to use previous things (as u could see for a node v the segment tree would be the same as its parent except that only edge[v][parent] is not included in parents segment)

I too tried this, but forgot to consider ans == 9 case and got many WAs.

1 Like

Can you explain the logic behind this?

Yeah,I too didn’t expect a combinatorics solution. Infact I think DP solution is quite simple.It was an overkill I suppose :stuck_out_tongue: .

Can you explain the math behind your solution? @shubhiks

Great editorials btw! :smiley:

Thanks @chant_coder

what is the time-complexity of your dp solution?

@bhpra its not O(1) I guess it is O(logn) .

To be frank, i didn’t think about time complexity, but implemented it because i had an intuition that this will be accepted.

Theoretically, worst case complexity should be around 50^4, but i don’t think this limit is actually achieved in any test case.

@beginner_1111 can you explain how

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