### Alex_2oo8's blog

By Alex_2oo8, history, 9 months ago, ,

New Year Greetings to the CodeForces Community!

Start off 2018 with some stimulating coding challenges as part of the January Long Challenge from CodeChef. I hope they will give you a pleasant beginning to your coding campaign this year. Joining me on the problem setting panel, we have:

I hope you will enjoy solving the problems. Please give your feedback on the problem set in the comments below after the contest.

Contest Details:

Time: 5th January 2018 (1500 hrs) to 15th January 2018 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/JAN18

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 global and top 20 Indian winners get 300 Laddus each, 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!

•
• +52
•

 » 9 months ago, # |   0 Is there some kind of registration at this moment?
•  » » 9 months ago, # ^ |   0 Codechef contests don't have registration except for the team contests .
•  » » » 9 months ago, # ^ |   0 so where do i submit?
•  » » » » 9 months ago, # ^ |   +5 Hahaha, I'm so sorry. I thought that I'm logged in, but I'm not.
•  » » » » 9 months ago, # ^ |   0 oh , if you meant registering for account , then ofcourse you need to create your account ( or register your account ) by clicking on the link given in the post.
•  » » » » » 9 months ago, # ^ |   0 I meant for contest, but I thought that i was already logged in.
 » 9 months ago, # |   +20 Lets discuss the approaches for the harder questions of the contest. KILLING MONSTER : Is it parallel binary search + updates using square root n dp.Complexity=N*sqrt(N)*log(N) KILLJEE KTH LETTER: I think only approach (suffix array/suffix tree)+binary search. HUMONGUOUS QUERY: I hardly got my meet in the middle fit in TL.so to solve x1*x2+y1*y2=c . I tried going over all x1,x2<=1900 and the checked y1 and y2 by preprocessing the factors till 10^6.Any better ways.?? SQUARE ROOT GOOD: Is it to implement some paper or are there any elegant solutions. I would like to hear if there are some easy/better solutions for 1 and 3. Also good approaches for approximate problem is invited.
•  » » 9 months ago, # ^ | ← Rev. 3 →   -8 Wrong
•  » » » 9 months ago, # ^ |   +4 I dont think so because in this question strong testcases are quite evident(atleast for vanilla N*sqrt(N)*log(N)).Also I observed that execution time on codechef servers is faster than that on codeforces custom test. So may be their servers are fast enough for it.But still I hope chemthan can clarify regarding.
•  » » » » 9 months ago, # ^ |   +5 Intended solution is . Also, you can see that the constant is very small. So, It may run faster than other problems with complexity ) (or even O(N * log2N)).
•  » » » 9 months ago, # ^ | ← Rev. 3 →   +8 O(NlogNsqrt(Q)) does not pass. (Atleast not for me).I did SOS dp from this blog for a constant number of updates (let's call this the Blocksize) and then check after this updates if a particular monster has died. If it has died, go back and check where did it die exactly.The first part has complexity O(NlogN * (Q / Blocksize)). The second part has complexity O(N * Blocksize). On setting Block_size in the range [1300 — 1400], the total time complexity becomes exactly 10^8 which should fit in the given TL.Link to my solution: Link
•  » » » » 9 months ago, # ^ |   0 U are indeed correct , blocksize in the range 1300-1400 indeed results in a good enough complexity.Sorry, my comment doesn't deserve reading and thanx for the cool optimization !
•  » » » » 9 months ago, # ^ |   0 I did the exact same thing but my query block size was sqrt(Q), Passed in 1.45s Solution
•  » » 9 months ago, # ^ | ← Rev. 2 →   +8 HUMONGOUS QUERY can be solved by generating all combinations and pruning.I wrote about it here.My solution passed in 0.51 s
•  » » 9 months ago, # ^ |   0 MONSTER, KILLKTH — the same with optimisations HYHUMOQ — you can also memoize solutions for both parts and then iterate through solutions of diophantine equations SQRGOOD — use binary search with square decomposition from paper and then decrease search interval by approximation
•  » » 9 months ago, # ^ |   0 Also it seems KILLJEE KTH LETTER can be solved with trie according to this comment
•  » » 9 months ago, # ^ |   +3 In killkth, I got 100pts AC with a linear traversal on the sorted list of nodes without binary search, and that too in 0.25s(Did binary search later and got the same execution time). Asserted and found out that I'm visiting atmost 20 nodes per query, via linear search, which is surprising to me.
•  » » 9 months ago, # ^ |   0 Killing Monster can be solved using square root + Sum over subsets alsoHere is my solution:https://www.codechef.com/viewsolution/17063146
 » 9 months ago, # |   0 Can anybody give derivation/reasoning on how to calculate X (number of humongous strings) in "HUMONGUOUS QUERY" . I spent 2 days in derivation and came up with, like ten wrong formulas before I gave up the question for good. The meet in the middle was quite apparent, but calculating X was what hindered me. Any help will be appreciated, thanks! :)
•  » » 9 months ago, # ^ |   0 Well , This was how I calculated X int zero = 0 , one = 0 ; int z = (int) str.size() ; for (int j=z-1;j>=0;j--) { if (str[j] == '0') { zero += (1 + one) ; }else { one += zero ; } } The value of X = one .
•  » » » 9 months ago, # ^ |   0 How did you find that the expressions for zero and one, and that final answer is "one"?
•  » » 9 months ago, # ^ |   +6 X=(A+1)*(C+1)-1 + B*D.A=10/1010 type in left string.B=1/101 type in left string.C=10/1010 type in right string.D=0/010 type in right string. For each type A seq, we can join it to a type C seq. We add +1 to each of these values to account for empty seq and subtract -1 finally to account for taking empty seq from both sides. For each B seq, we must combine it with some type D seq. So this contributes B*D sequences.
 » 9 months ago, # |   +57 The last problem is almost a subproblem of my problem Project Euler #193 on Hackerrank
 » 9 months ago, # | ← Rev. 2 →   +4 Can someone explain his solution for Humongous Query using Meet in the Middle.Thank you in advance.
 » 9 months ago, # |   0 For the 4th problem, what is wrong with my greedy solution? Link
•  » » 9 months ago, # ^ |   0 Here : if (v.back() <= rs) { rs -= v.back(); two.pb(v.back()); } I changed it to : if (v.back() <= rs && rs - v.back() != x) { rs -= v.back(); two.pb(v.back()); } And it passed. LINK
•  » » » 9 months ago, # ^ |   0 Okay. Thanks man!
 » 9 months ago, # |   0 When can we expect the official editorials of all problems?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 They are already out
 » 9 months ago, # |   +3 Can we solve "Killing monsters" using Tries?
•  » » 9 months ago, # ^ |   0 i don't think that ,it is can be solved with trie. There are 2^18 queries ,it is a one problem ,and also trie it is not good to this problem,because you don't uses prefixes.Trie is good for strings. I didn't solved this problem.I will solve after school's exams.
 » 9 months ago, # |   +1 Why my rating changed while it shows that I didn't participated? It considered me as last of contest :(
•  » » 9 months ago, # ^ |   0 Bump, can admins fix this? -149 is not little deal.
•  » » » 9 months ago, # ^ |   0 You have wrong submissions on problem PRTITION during the contest. If you even submitted one solution during the contest, whatever maybe the verdict, it means you participated in the contest.
•  » » » » 9 months ago, # ^ |   0 I know it, but it at least it should say you are participants of contest. In ranklist it shows same thing with challenge of December which I didn't participated. If it considers me as participant, I must be on ranklist.
•  » » » » » 9 months ago, # ^ |   0 It's like this from ages. Until and unless you get some positive score, ranklist will say that you haven't participated. Quite weird ranklist. I don't think your rating will be restored.
•  » » » » » » 9 months ago, # ^ |   0 Anyway, thanks for information. It not hard to get that rating back, but unfortunately, there are just 3 contests in one month :(
 » 9 months ago, # |   +5 Can someone explain the sqrt decomposition + sos dp approach for the MONSTER problem in details.
 » 9 months ago, # |   0 I have a doubt regarding the time complexity of 'MONSTERS' using sqrt- decomposition + SOS DP approch. This is a accepted solution. If we look at the last for loop, we are comparing all the queries in the current block with all the values of h[i]. We are doing for all the blocks. So, shouldn't the time complexity of the solution be "number of blocks" * "size of each block" * n. In that case, wouldn't the time complexity be n *q ? What am I missing?