Hey Codeforces community,
You are invited to CodeChef December Cook-Off 2018 sponsored by ShareChat. This is a 2.5-hour competition with 5 problems and it’s open to programmers across the globe. The contest problems will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.
Participants will also be in the running for some exciting jobs at ShareChat — India’s fastest growing social network.
To apply, all you need to do is fill the application form on the contest page and participate in the December Cook-Off.
I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:
Tester: Deemo (Mohammad Nematollahi)
Setter and Editorialist: Pepe.Chess (Hussain Kara Fallah)
Statement Verifier: Xellos (Jakub Safin)
Mandarin Translator: huzecong (Hu Zecong)
Vietnamese Translator: Team VNOI
Russian Translator: Mediocrity (Fedor Korobeinikov)
Bengali Translator: solaimanope (Mohammad Solaiman)
Hindi Translator: Akash Shrivastava
Contest Details:
Start Date & Time: 23rd December 2018 (2130 hrs) to 24th December 2018 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
Contest link: https://www.codechef.com/COOK101
Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu
(For those who have not yet got their previous winning, please send an email to winners@codechef.com)
Good Luck!
Hope to see you participating!!
Happy Programming!!
Will this contest have editorials ? Just asking because it's more than 1 week since December Long challenge has completed but the official editorials are still not published ! :(
Yes I promise to publish them today
posted
no collision with technocup....YAY..
How to solve CSUBSQ?
Divide and Conquer. calculate mid to every r and every l to mid. Now take prefix sums for finding answer with constraint.
As an alternative, calculate prefix sums and suffix sums for all possible "division points" with a step of W; after that, you can say that every segment of length W touches/crosses some division point, so you can construct it by combining results for prefix and suffix which start at this point.
SO you count each segment based on its first division point or last division point it contains.
Sorry for not being clear enough in my initial comment.
I'm saying that the answer is "all subsequences minus bad subsequences". I am counting all subsequences with trivial DP and then doing this "division points" stuff for "bad subsequences".
In this case, I need to find number of sequences which are lying withing a segment of length W — in order to avoid counting something twice I can say that first element of the segment should always be taken. After that, the segment that I work with contains exactly 1 division point (or starts right after division point and ends right before the next one).
My code from the contest: link.
How to approach last one?
use inclusion exclusion so instead of having A <= x <= B you will have x <= Y
for each mask you will have y1,y2,y3... you need to count how many ways you choose
x1 <= y1 , x2 <= y2 ... and S = x1+x2...
Digit dp after you extend all to 9 digits
[which digit][mask][sum][carry][number_you_are_on]
mask says for each number whether it's less than or bigger than its corresponding y
I think you can continue from here
For sum I think you need to store it special format right. I was thinking of some which has 10^3 states Like previous digit, number of 9's from second previous digit onwards and one more non 9 digit. Or just mapping or something work?
Also when you have sum why carry is needed?
oh no, imagine all numbers stacked
xxxxx
yyyyy
zzzzz
#########
sssss
you start from least significant digit, and build your sum as you go forward, so you build your sum digit by digit from least significant to most significant and after you finish each digit you check if it's included in our desired bounding interval
[digit = 9][mask = 2^n][sum = 0..9][carry = 0..n][n][2]
You need to handle zeroes in the sum because they could be leading (so you shouldn't break always with 0 if A > 0) I do it with 2. Mohammed solution doesn't need it (just few cases handling) but I just wrote it the less ifs way
Am I right that we can also improve complexity by substituting 2^7 inclusion/exclusion DPs each having 2^7 states for current state of numbers with a single DP having 3^7 states for numbers? Something like "Prefix of i-th number either matches prefix of L, or matches prefix of R, or is already in-between"?
Can SOSTD be solved by sorting two arrays with respect to one array and applying divide and conquer on the other array?
UPD: No. I was wrong. Sorry. I realized my mistake.
How to solve YVSTR?
nikesh04 you see all the good non-empty substrings are in the form of (a)+ or (a)+(b)+, where a and b are two distinct characters.you just need to count the distinct substring of this form.
I will tell you my approach. for all the substrings of (a)+, we can simply calculate the prefix array and take max for each character. for a substring of type (a)+(b)+, you can take array max[26][26][N] where max[i][j][k] represents maximum continuous character(j) after continuous k character(i) . for memory issue, just use map.
you can look at my solution : https://www.codechef.com/viewsolution/22068155
"max[i][j][k] represents maximum continuous character(j) after continuous k character(j)".What does this line meant to stay?
if there are k number of continuous character 'i', how many maximum numbers of continuous character 'j' are present in the given string. i.e. if the string is aaabb,
max[0][1][1]=1; after 1 continous 'a',there are maximum 2 continous 'b'.
max[0][1][2]=1; after 2 continous 'a',there are maximum 2 continous 'b'.
max[0][1][3]=1; after 3 continous 'a',there are maximum 2 continous 'b'.
How to solve SOSTD?
Editorials are ready to be published, I am just waiting for the admin to do it
All editorials are posted in discuss.codechef