nagpaljatin1411's blog

By nagpaljatin1411, 22 months ago,

Hello Codeforces!!

I, on behalf of all CodeChef Campus Chapter teams, would like to invite you to take part in our first ever Campus Chapters Contest, which will take place on Thursday, April 2, 2020 at 12:00 ISTUTC+5.5. The contest is a 2.5 day long (60 Hrs) contest. The contest will be open to everyone. We'd be offering you 8 partially graded problems with varying difficulties and a challenge problem.

The problems were invented and prepared by me, Shahraaz, shrey, aneesh2312, divyam.arora, thepushkarp, sidtiw_, imreallyjohn and MayureshPatle and tested by darshancool25, l_returns, r_zenith, taran_1407, mj_13, mann2108, sumanthst24, himanshu, mgfags, himanipopli, rsd511 and Manas Khosla.

Huge thanks to entire CodeChef Team for their invaluable help and great platform.

Hoping you'd have a great time solving the problems while in quarantine.

• +129

 » 22 months ago, # |   +2 will it be rated?
•  » » 22 months ago, # ^ |   +13 No, it's unrated
•  » » » 22 months ago, # ^ |   +3 okk
•  » » » 22 months ago, # ^ |   +3 unrated like ? (^__^)
•  » » » » 22 months ago, # ^ |   +82 You
•  » » » » » 22 months ago, # ^ |   +3 lmao
•  » » » » » 22 months ago, # ^ |   -13 hehe you stole nagpaljatin1411 comment.
 » 22 months ago, # |   +13 will there be individual prize for top contestent from each colleges
•  » » 22 months ago, # ^ | ← Rev. 2 →   +8 Yes, all the active codechef campus chapters are entitled for it. Details are already shared with the representatives along with the process for it. In order to avail it for top performer, the participation should meet >=50 from campus, along with the fact that top performer should have atleast 3 AC's.
•  » » » 22 months ago, # ^ |   +1 if more than one person is at the top in there college will the ties be broken.
 » 22 months ago, # | ← Rev. 2 →   0 The problemset was really nice and the idea behind the solution of last problem was much more interesting. Can someone share their approach for problem "save us" and what was intended solution for CSARE bcz people have execution time 0.07s and mine was 0.47 using rolling hash?
•  » » 22 months ago, # ^ | ← Rev. 2 →   +1 I used Kmp algorithm for CSCARE, it ran in 0.08s.Solution
•  » » » 22 months ago, # ^ |   0 The solutions are not public yet, do you mind sharing your solution on ideone/pastebin?
•  » » » » 22 months ago, # ^ |   0
•  » » » » » 22 months ago, # ^ |   0 Thanks man, really clever solution. I can never think myself kmp can be used in this way also.
•  » » » 22 months ago, # ^ |   0 Can you please explain your solution briefly?
•  » » 22 months ago, # ^ |   0 I have also used rolling hash and it runs in 0.09s. Maybe the difference is due to the bases and the mod values which are being used.
•  » » 22 months ago, # ^ | ← Rev. 3 →   0 "Save us" can be solved using dfs tree. Make the dfs tree (implicitly) and for each infected node, check which subtrees get removed. For each node you need to have (number of nodes, infected nodes) present in the subtree of that node. For each infected node :count (non-infected nodes) = 0.For each subtree of that node which gets disconnected:1) If infected nodes = 0, count += size of subtree.Also u need to check that if removing these disconnected subtrees also makes the original tree. non-infected and increase count accordingly.Update the answer accordingly.This is basically an articulation point logic because removing an infected node is useful if it is an articulation point(Considering multiple infected nodes).Also can you share your idea of MPRODMUL, I was using digit dp but couldn't solve it, I think I am missing something.
•  » » » 22 months ago, # ^ |   0 I tried to write bruteforce solution for Save us.LinkI just removed every infected node and check how many people are left uninfected, but it was giving wrong answer on all testcases. Can anyone point out the mistake?Thank you!
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   0 Your code gives answer 0 0 on this case when it should be 0 1Case :-13 3 31 2 31 22 31 3 I think it fails only on cases like this where all nodes are infected.Just initializing id = 1 would have worked out.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +3 @abhi2402 , Lets say you have placed some digits (of length say X ) , now you want to place some digit at position X (0 based indexing ) , lets say you placed a digit D , lets say mask will represent the digits you have placed till now (excluding the current digit) , now D can unset all the set bits in mask which are multiple of it . At last , if you have only one set bit in mask (the last digit , which cant be unset) , the digit divisibility condition is satisfied . To check the divisibility by K , take mod with K . And also every time when you place a digit check whether its in range or not ( I hope the last two conditions that i have mentioned are easy to understand , if you still have doubts , please comment ) .
•  » » » » 22 months ago, # ^ |   0 Can you please provide a small example regarding the setting and unsetting of the bits? Also how to check if the number is in range of [a, b] when we add a digit, I have done few questions of digit dp, but they have always involved ans = f(b)-f(a-1) which doesn't work with max()
•  » » » » » 22 months ago, # ^ | ← Rev. 2 →   +3 For checking whether the number is in range or not , we will take two variables lcheck and rcheck , if lcheck is 0 , it tells us that the number that have generated is already greater than L so you can place any digit(1-9) from current index , if lcheck is 1 , it means that the number is a prefix of L , you can only place digits from (1 to value_at_current_index_in_L) , similarly with R . Now how do we change these values ? if lcheck is 1 and we have placed a digit which is less than the value_at_current_index_in_L , then lcheck becomes 0 , if we place a digit which is equal to value_at_current_index_in_L , then lcheck stays as 1 . If lcheck is already 0 , we can place any digit (1-9) (only 1-9 because , in this question we cant use zeros ) . For setting a bit i , i hope you know how to do (mask | (1<
•  » » » » » » 22 months ago, # ^ | ← Rev. 2 →   0 Ok, now I understand what you wanted to explain above. If we see the digit divisibility criteria it basically demands each digit to be divisible by the lowest significant digit. So I was actually going from the reverse end, from lowest to most significant, as I only have to maintain which digit is present as the least significant digit to check for that criteria(and not a mask to check for it). But checking if no. is between [a,b] was tedious and I couldn't figure it out there. Will the same technique for checking range(if in [a,b] or not) work in my method too?
•  » » » » » » » 22 months ago, # ^ |   0 In your method ? I didn't get you bro :(
•  » » » » » » » » 22 months ago, # ^ |   0 Yes, sorry for not clearly explaining what I am doing. What I was trying to do was to iterate from lowest significant digit to most significant. By doing that I don't need to maintain a mask, just need to maintain which is the lowest significant digit since the digit divisibility criteria boils down to all digits in the number being divisible to the lowest significant digit. dp[20][102][10][10][2] — (curr place, %k, lowest significant dig, curr_digit_chosen, flag). But I was stuck on finding if it lies in optimal range.But nvm, I ll go through the editorial first and then ask if I have doubts. Just posting this to clearify what I wanted to say above.
•  » » » 22 months ago, # ^ |   +11 Very brief outline for MPRODMUL — The solution uses digit dp. We maintain digits for which digit divisibility condition isn't yet taken care of using bitmask. Also maintain remainder.My code Editorial for MPRODMUL will be ready today night(hopefully).
•  » » » » 22 months ago, # ^ |   +5 Thank You, eagerly waiting for the editorial!
•  » » » » » 22 months ago, # ^ |   0
•  » » » 22 months ago, # ^ | ← Rev. 4 →   +3 abhi2402 Thank you for the solution of Save us, i tried thinking in terms of finding articulation points but was stuck on how do i calculate if a particular node is removed than in the remaining disconnected component will it have atleast one infected person or not. My solution for MPPRODMUL Click. Solution is a bit overcomplicated but the idea here is we have 5 states, 1. index of current digit.
2. modulo k till last index.
Now if we are at some index i and we want to take a digit d then we go through the mask and off all the bits which are divisible by d since we have found their divisor, set the dTH bit and send this mask to next state. At the end(base case) if we have only one bit set in mask which is obviously for last digit we return 1 as last digit need not to be divisible further by any digits. I think code can give you a more clear idea.