Unofficial Editorials December Lunchtime

general
, , , ,
41

@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
42

Thanks man! Understood where I went wrong. Changed the hash function to b1+201*(b2+201*(p+201*(q)))+last; Using an unordered hash map and a hash of numbers instead of strings removes the TLE. The new hash function removes the WA. Got AC! Only if this has dawned on me during the contest time :\

Could you give further insights as to how you chose the hash function like this? A hash function of p+201*(q+201*(b1+201*(b2)))+last; fails even for the sample test case. Whatā€™s the difference?

43

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: [https://www.codechef.com/viewsolution/16725382][1]

Thanks in advance!!
[1]: https://www.codechef.com/viewsolution/16725382

44

Wow. the concept is really is good. I used to struggle a lot with these DP problems.

It would be really helpful if you can link few more problem of the similar type.

45

I remember reading an editorial written by @likecs where he had hashed a bitmask, and grid coordinates this way.

46

Nice oneā€¦ Though an overkillā€¦

47

You didnā€™t multiply p+201(q+201(b1+201*(b2))) by 2 before adding last. This causes collisions in your hash values. There must be atleast two different tuple (p,q,b1,b2,last) which give same hash value.

48

But dont you discuss with the coordinator or someone(atleast testers) regarding your solutions or questions .

49

@teja349 Yes we do discuss the problems as well as the solutions. But if you see to it around 5% (of the total participants) got 100 points and that was the difficulty which I intended to put up for the 3rd problemā€¦so that way it was fine.

50

@taran_1407: can u plzz explain this briefly

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

51

@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:

52

plz format the test case accordinglyā€¦

53

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.

54

You may refer this solution. https://www.codechef.com/viewsolution/16730334

I know this is not the best implementation and probably complex than other ones mentioned above, but i had implemented it this way, so i shared. This one use dp table instead of map, thus doesnā€™t use hash.

55

thanks but currently i donā€™t know java. So, if possible please explain the dp states.

56

P and Q are number of sweets left in bag 1 and 2 respectively, B mean number of times box can be opened, and cur is the current box to be opened.

count0 and count1 has only one difference, see the recursive call, count0 calls with B-1 when cur is 1 while count1 calls with B-1 when cur is 0.

57

@beginner_111 in my sol maximum 3 recursive call

58

isnā€™t it O(50^4) because you are looping for building each dp states!

59

But my point was not regarding the difficulty. I was thinking that whether every coordinator you proposed to and also the testers did get an O(n^3) solution instead of O(n^2)(which was also pretty easy to point). Then I feel its a deep trouble because the point of coordinator or tester is atleast observing the O(n^2) solution even though you allow O(n^4)to pass (which I believe is unobserved by them or either not pointed out to you by your previous comments).

ANOTHER DOUBT(Anyone can clarify): Is there any possibility that I get an update through mail or any if get a reply to my comment here.

60

Testers obviously know the most optimal solution(as they explore every possible solutions).