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.
will it be rated?
No, it's unrated
okk
unrated like ? (^__^)
You
lmao
will there be individual prize for top contestent from each colleges
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.
if more than one person is at the top in there college will the ties be broken.
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?
I used Kmp algorithm for CSCARE, it ran in 0.08s.
Solution
The solutions are not public yet, do you mind sharing your solution on ideone/pastebin?
Link(It's not well written)
Thanks man, really clever solution. I can never think myself kmp can be used in this way also.
Can you please explain your solution briefly?
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.
"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.
I tried to write bruteforce solution for Save us.
Link
I 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!
Your code gives answer 0 0 on this case when it should be 0 1
Case :-
1
3 3 3
1 2 3
1 2
2 3
1 3
I think it fails only on cases like this where all nodes are infected.
Just initializing id = 1 would have worked out.
@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 ) .
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()
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<<i) ) , for unsetting ith bit in mask , we can do mask = mask & (~(1<<i)) ( (1<<i) has only ith bit set , ~(1<<i) has all bits set except ith bit , now if you do a bitwise and of mask with ~(1<<i) , ith bit in mask becomes 0 and rest all remains same as before . For example , say you have placed 924 and if you place 2 at current index , 2 can unset 2nd bit and 4th bit in mask , if you place 3 at current index , you can only unset 9th bit in mask.
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?
In your method ? I didn't get you bro :(
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.
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).
Thank You, eagerly waiting for the editorial!
Editorial
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,
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.
Hi, I was the author of CSCARE. The intended solution was applying KMP algorithm(or any other string matching algo) on the difference arrays.
I am attaching the solution link here — Solution
I would post the editorial soon.