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:

- Problem Setter: hrudaipabbisetty (Hruday Pabbisetty), Berezin (Dmytro Berezin), ed1d1a8d (Tiny Wong), chemthan (Trung Nguyen), killjee (Satyam Shubham), kingofnumbers (Hasan Jaddouh), include_sajal (Sajal Agrawal)
- Problem Tester: Alex_2oo8 (Alexey Zayakin)
- Editorialist: adamant (Alexander Kulkov)
- Admin: kingofnumbers (Hasan Jaddouh)
- Statement Verifier: Xellos (Jakub Safin)
- Russian Translator: CherryTree (Sergey Kulik)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: VNOI Team

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!

Is there some kind of registration at this moment?

Codechef contests don't have registration except for the

team contests.so where do i submit?

Hahaha, I'm so sorry. I thought that I'm logged in, but I'm not.

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.I meant for contest, but I thought that i was already logged in.

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.

Wrong

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.

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*log^{2}N)).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 complexityO(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

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 !

I did the exact same thing but my query block size was sqrt(Q), Passed in 1.45s Solution

HUMONGOUS QUERY can be solved by generating all combinations and pruning.

I wrote about it here.

My solution passed in 0.51 s

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

Also it seems KILLJEE KTH LETTER can be solved with trie according to this comment

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.

Killing Monster can be solved using square root + Sum over subsets also

Here is my solution:https://www.codechef.com/viewsolution/17063146

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! :)

Well , This was how I calculated X

The value of X = one .

How did you find that the expressions for zero and one, and that final answer is "one"?

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.

The last problem is almost a subproblem of my problem Project Euler #193 on Hackerrank

Can someone explain his solution for Humongous Query using Meet in the Middle.

Thank you in advance.

For the 4th problem, what is wrong with my greedy solution?

Link

Here :I changed it to :And it passed.

LINK

Okay. Thanks man!

When can we expect the official editorials of all problems?

They are already out

Can we solve "Killing monsters" using Tries?

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.

Why my rating changed while it shows that I didn't participated? It considered me as last of contest :(

Bump, can admins fix this? -149 is not little deal.

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.

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.

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.

Anyway, thanks for information. It not hard to get that rating back, but unfortunately, there are just 3 contests in one month :(

Can someone explain the sqrt decomposition + sos dp approach for the MONSTER problem in details.

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?