Alex_2oo8's blog

Invitation to CodeChef January Long Challenge 2018!
By Alex_2oo8, history, 7 years ago, In English

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!

  • Vote: I like it
  • +52
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there some kind of registration at this moment?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Codechef contests don't have registration except for the team contests .

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so where do i submit?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I meant for contest, but I thought that i was already logged in.

          → Reply
»
7 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Lets discuss the approaches for the harder questions of the contest.

  1. KILLING MONSTER : Is it parallel binary search + updates using square root n dp.Complexity=N*sqrt(N)*log(N)

  2. KILLJEE KTH LETTER: I think only approach (suffix array/suffix tree)+binary search.

  3. 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.??

  4. 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.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it -8 Vote: I do not like it

    Wrong

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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)).

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +8 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 !

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

    I wrote about it here.

    My solution passed in 0.51 s

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +57 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

Thank you in advance.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Link

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When can we expect the official editorials of all problems?

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can we solve "Killing monsters" using Tries?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply