When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Morphy's blog

By Morphy, history, 5 years ago, In English

Greetings Codeforces Community! CodeChef September Long Challenge is just around the corner. Everyone is encouraged to partake starting 6th September till 16th September. It is an occasion to put to test your exceptional programming skills.

The problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

Accompanying me on the problem setting panel are:

In despite of having two chess "world champions" in the judge panel, this time there are no chess problems.

Hope to see you participating!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem DODGERS

I have a doubt in getting l,r from x,y

if(s==0)
    l=(x-1)%(N+1)

and x is in range of [1,N] then l will be in range of [0,N-1] is it correct or i am understanding it wrong.

Please help

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

    You added parentheses that aren't in the statement. It's modulo $$$N$$$, then plus 1, as normal precedence rules say.

»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

The challenge is over.

Congrats to the winners!

Div 1.

  1. narry
  2. .I. (The cf logo coder)
  3. wmoise
  4. wrong_answer_1
  5. zhouyuyang

Div 2.

  1. YalG
  2. Mlxa
  3. tmyklebu
  4. MicGor
  5. tripPple_A
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

    Are you sure thats CF logo?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Morphy Chef Designed a Network: CHEFK1 . I think author solution is wrong for this problem . Critical test case: 22 242 .

    Ans should be 22 . But my code passed which shows output 21 .

    My connections: https://ideone.com/1xUKm4

    If you have better answer give me the connection . Not only 22 242 . It does not follow pattern for n=22 ,24,25,28,34,37,38,39,40,42,44,45,46,48,49,50,52,54,55,56,58,59,60,62,6364,65,66,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83 .

    My bruteforce code: https://ideone.com/ahag0p

    My Accepted code: https://ideone.com/3vklml

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      ans is 21 construct without self edges with degree 20. hence, 2E = 20 * 22 => E=220,that is max number of edges we can built if degree is 20. now add self loops which are atmost 22 adding 1 degree to each edge. so net required is 21.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        You can not count same edges twice. How can 22 nodes all have equal and unique 20 edges i can't understand. Let me understand, please write a printf code to show me which are the connections you are counting.

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

          do u know this 2*E <= n*degree, if not then google.you could also work on paper, its very simple.see one edge contributes to degree of two nodes. for building of graph that you have to do on your own, and you will able to it easily one you understand above equation.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone please explain their approach for DODGERS and DOOFST?

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

    DOOFST:

    Subtask 1: Everyone hates each other, so everyone has to be in different groups at some point. Divide the bit string in half, left half gets all $$$0$$$, right half gets all $$$1$$$, then recursively divide each half again. You get something like

    00001111
    00110011
    01010101
    

    Subtask 2: In short: it should be a complete k-partite graph for some k.

    In not-short: If there is no edge between some pair of people, then these people must belong to the same group every time. Let's "invert" the graph, in every pair where there was an edge, now there's no edge, and vice-versa. Find the connected components in the inverted graph, you get this problem.

    After we've found the inverted connected components, let's return to our original graph. If there is any edge that connects two nodes in the same inverted connected component, then answer is $$$-1$$$. Otherwise we can consider each inverted CCs as a single node, every inverted CCs hate each other, so now the problem is literally subtask 1 again.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      more related problem than connected components, https://codeforces.com/problemset/problem/190/E after building connected components, we just have to build complete graph. using divide and conquer and maintain address of parent.

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

      Hello!

      First of all thanks a lot for such a nice explanation. I implemented the solution but got WA in just 1 test case. If possible then Can you please help?

      solution

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

        I think you missed case $$$M = 0$$$. Should be $$$0$$$ operations.

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

      Can you please explain me this a little more.

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

        Can you please explain me your question a little more? :)

        I don't know which part you are not understanding. It is simply "subtask 2 = subtask 1 + 920E or 190E".

        Take a small test for example:

        3 1
        1 2
        

        We can see here that $$$1$$$ and $$$3$$$ don't hate each other, so every time the hate-inator fires, they have to be in the same group. $$$2$$$ and $$$3$$$ must also be in the same group. Since $$$1$$$, $$$3$$$, and $$$2$$$ must be in the same group every time, it's impossible to get $$$1$$$ and $$$2$$$ to hate each other, so the answer is $$$-1$$$.

        With the same reasoning we can invert the graph and solve with the exact same idea as 920E or 120E.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I couldn't solve DODGERS, but I liked DOOFST a lot. Try to think for a few minutes, before opening each successive hint.

    Hint 1
    Hint 2
    Hint 3
    Final
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    DODGERS: Let's solve subtask 1 first.

    For each guest, let's find the closest left and closest right to that guest that they dislike. Now each guest can be represented as an interval $$$[Lguest, Rguest]$$$ in which they'll think the game is fair iff only the guests in that range are invited. We want to know how many guest think the game is fair for each query $$$[L, R]$$$.

    Let's think of it another way. Let's think of each query $$$[L, R]$$$ as points $$$(X, Y)$$$ on the 2D plane $$$(X = L$$$ and $$$Y = R)$$$. We have $$$O(N^2)$$$ possible points. For each guest, they will answer YES for a specific set of points. These points form a rectangle. So we have $$$N$$$ YES-rectangles, each corresponds to a guest.

    Let's get back to our question: "Given a query $$$[L, R]$$$, how many guest say YES for that query?". We rephrase the question as "Given a point $$$(X, Y)$$$, how many YES-rectangles does this point lie in?".

    This is now solvable offline with a line sweep + a range addition/point query data structure in $$$O((N+Q)logN)$$$. Fenwick is very fast.

    Subtask 2 is just subtask 1 with persistence.

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

      can you please explain the first part a little more? How you are finding [Lguest, Rguest]?

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

        $$$Lguest$$$ is the closest to the left guest that they dislike, and $$$Rguest$$$ is the closest to the right that they dislike.

        For example, if guest $$$1$$$ dislikes guest $$$4$$$ and $$$5$$$, then we only really care that $$$1$$$ dislikes $$$4$$$, since they'll say "NO" to parties $$$[1, 4]$$$ or $$$[1, 5]$$$ or anywhere further anyway.

        To find the closest left and closest right guests that they dislike, you just DFS once to find the order of befriendings. Then for every guest, you just go through their adjacency list and find the closest left and right by index that they dislike. Basically follow the statement.

        "Go through their adjacency list" for all the guests takes $$$O(sum\ of\ vertices'\ degrees)$$$ in total, which is just $$$O(M)$$$

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

          Sorry to disturb you again but can you please show a little how to add persistence to this to solve the subtask 2?

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

            Have you solved subtask 1?

            For subtask 1 we want to query how many rectangles that contain a certain point. We can solve offline, so let's sort the queries by $$$X$$$ first. Then let's do a line scan in increasing $$$X$$$. We have to do the following:

            • Whenever the scan line encounters the start of a rectangle, update the $$$Y$$$-range in which the rectangle lies in.
            • Whenever we encounter a query point, just query the corresponding $$$Y$$$.
            • Whenever the scan line encounters the end of a rectangle, update the $$$Y$$$-range in which the rectangle lies in (again).

            Therefore we need to support these operations:

            • Update some range by $$$+1/-1$$$
            • What is the current value of an element?

            The easiest way to do this is by using a fenwick (but segment tree does work):

            • When we want to update some range $$$[L, R]$$$ by $$$1$$$, we update $$$arr[L]$$$ with $$$+1$$$ and $$$arr[R+1]$$$ with $$$-1$$$
            • When we want to find out the value of $$$arr[P]$$$, we simply query the sum of $$$arr[1..P]$$$

            No need for lazy propagation and goes very well with persistence.

            Now, for subtask 2, since we're solving online, we can't actually sort the queries. But we can still pre-process all the rectangles. Now the operations we need to support becomes:

            • Update some range by $$$+1/-1$$$
            • What is the value of an element at some past version of the array?

            This is where persistent data structures come into play. It allows for us to query at a specific version of the DS.

            A little bit about persistent DS: the main idea is that instead of modifying the value in the DS, we create a new version of it without actually deleting the old version. We exploit the fact that very little $$$(O(logN))$$$ changes are made during each update, so we don't have to build the entire thing anew. There are two common ways of building a persistent DS: path copying (creating new root node, copy the entire new path) and fat node (turn every nodes into a dynamic array, store every value along with their version, and binary search for the most up-to-date version to the version we query) . There are plenty(1) of(2) tutorials(3) online.

»
5 years ago, # |
Rev. 6   Vote: I like it +2 Vote: I do not like it

I was stuck at last two questions ( excluding Challenge question ).

For PSUM, I thought about going from some state of $$$a^k + b^k + c^k$$$ to $$$(a+val)^k + (b+val)^k + (c+val)^k$$$, but that requires $$$O(K^2)$$$ time, using binomial expansion and precalculating factorials and inverse factorials. I think it was FFT based question, but I couldn't figure out how to apply FFT here. I thought maybe we can do transition between states in $$$O(KlogK)$$$. What I want to know here is, what's the correct way to think about something when you have some idea that, ok, maybe FFT could be used here? In this case, I didn't know how FFT works before I read this problem. I just knew FFT is something that can multiply polynomials in $$$O(KlogK)$$$ compared to the naive $$$O(K^2)$$$. I tried to read a lot of blogs of FFT, but I guess I was too focussed on bringing $$$O(K^2)$$$ down to $$$O(KlogK)$$$ whereas maybe we had to do something else.

For DODGERS, if we look closely at the three conditions, you see that there is no point in graph structure ( please correct me if I am wrong ). If some guest has number outside $$$[L,R]$$$, then he won't be invited. If among all guests in $$$[L,R]$$$, we just find how many are directly connected ( friends ), then among all those there will always be one person who became friends with Dodger before other. i.e. problem reduces to find number of edges with endpoints in $$$[L,R]$$$. For each edge between $$$u$$$ and $$$v$$$, if $$$u$$$ finds it fair, then $$$v$$$ has to find it unfair. So we can drop the whole graph representation, and don't even need $$$DFS$$$. We just need for query $$$[L,R]$$$, how many intervals ( consider input $$$a$$$,$$$b$$$ as interval ) lie completely inside it. But I tried mergesort tree and fractional cascading too ( Credits: ifsmirnov for blog ). But it was too slow, and was giving WA on some cases. What am I doing/assuming wrongly here?

UPD: Trying to clear its_aks_ulure's doubt, I got what I am doing wrongly! I was counting unfair because maybe people who think it is fair, overlap, i.e. They come before multiple people. But forgot to think same for unfair. For unfair also, there might be overlaps, thus counting edges from one person twice is wrong.

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

    For DODGERS, shouldn't it be how many intervals, lie completely inside it or lie partially intersecting ?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Partially intersecting doesn't matter, because if one end point is outside $$$[L,R]$$$, then that person wasn't invited ( only guests from $$$[L,R]$$$ are invited ).

      Did I understand something wrongly in the question?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I think so it actually matters, for example consider a Query [l, r] like [2, 5] say. The segment [L, R] for person 2 is say [1, 3], then surely person 2 is not happy because he has person 3 in the same set tho the segment [1, 3] is not completely inside query range [2, 5]

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Oh, it seems you didn't read my whole post. The input given as edges $$$x$$$,$$$y$$$ is "considered" as "intervals".

          Then for query $$$[L,R]$$$, we need count of how many "intervals" are completely inside $$$[L,R]$$$. Because for each of those "intervals", it means that both persons ( end points ) are inside the query range, which makes sure both are invited. And both are connected ( friends ), because the "interval" exists ( we're not making up intervals on our own ).

          And finally, since time stops for no one, for a given "interval" which we now like to think of as an edge, out of the endpoints, Dodgers would definitely have become friends with one person before other, and other person will find it unfair. We count number of such "intervals", which gives number of people who think unfair, and subtract this from $$$R-L+1$$$.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone share their approach for PSUM?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    First let's solve it in O(SKN * logK). We have dp[i][j][k] = including i first elements, we have sum of cost j, and chose k elements. In other words, dp[i][j][k] = sum for ii < i for possible sequences seq of size k with elements that we chose at least once summing up to j and elements we chose 0 times having seq[x] = 0 of (value[ii]^s[ii] / (s[ii]!)). dp[i+1][j+cost] is (the convolution of 1 + (val[i]*x)^1 / 1! + (val[i]*x)^2/ 2! + ... and dp[i][j]) + (dp[i][j+cost]). The answer is sum of dp[i][j<=S][k] * k!. Link

    But that wasn't enough for my ntt code to pass, even though it should have been :P

    With my ntt being too slow for this problem I managed to optimize it to a slightly better complexity. We can use 2D FFT/NTT to convolute matrices and solve this problem convoluting matrices of groups of size X. So for each group of size X we'll compute all the subsets that it has and put the proper things in the matrix, then we convolute it with what we had before. This has complexity O(2^X*K*(N/X) + (N/X)* SK * logSK). Choosing X as log(S * log(SK)) we can get complexity O(SKN) * O(log(SK) / log(S * log(SK))) and that's slightly better than the previous solution. Link. Actually, I didn't calculate the complexity before getting AC, I just plotted the function of the complexity in google and chose the minimum from there :P

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

      Thanks a lot. And yeah,codechef time limits can be irritating at times.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Wrong !

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

        Uh... both the setter's solution and the tester's solution look like NSK*logK to me, they have O(N) loop with O(S) inner loop with a call of ntt/mutiplication of size O(K) so it's O(NSK*logK)

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          The editorial mentions a neat trick to solve it in O(NSK)

          Copy Paste from official editorial.

          Spoiler

          Update: It's wrong. Now removed from editorial.

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

            That's incorrect because multiplication over roots of unity is cyclic convolution so the coefficients get messed up. That's the reason why the actual solutions don't use that.

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

              Indeed, ur right, I'm sorry, the intended complexity is $$$O(NSK \log K ) $$$

»
5 years ago, # |
Rev. 5   Vote: I like it +18 Vote: I do not like it

Could somebody share their test generator for challenge? The 4-th test set is confusing me: the way it is described:

"After generating the triples, try again if any of them have equal elements."

seems to run very long for me. Even checking right after each triple seems to take forever. So instead I did some weird search:

"After generating each triple, if the triple has equal elements, try again and add +1 to count_mistakes. Start again from scratch if count_mistakes > 64."

Now it generated the test fast, but it felt like my local 4-th type tests were somehow very different still compared to the one visible test of 4th type. (sometimes very different scores)

My generator: http://ideone.com/H144pL

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

    I found that confusing as well. Did not really have the time to for good scores, but the way I understand it is this: if the three registers are always added to the list in a fixed order and in the end we take every third element of the list, that means that really we are just listing all the values of a single register during the run of the program. If an instruction does not change that register, we get consecutive equal values, so in order to get a list of valid triples, the program needs to change the register on at least 2/3 of its instructions, which explains why the fully random generation takes so long.

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

    I don't think I can help with this as long as there isn't a mistake in the description — I just edited what I was given and didn't check if it makes sense or works nicely. Spending hours on generating tests in special problems isn't that rare.

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

      There was more discussion about this on codechef: thread

      TL;DR: the description was wrong — the real generation process was more like "Make 3 moves, shuffle registers, then add all 3 registers as a triple, repeat." (yes, can be solved using 60^3 brute force per triple) rather than what pwild described.

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

        Bleh. For reference, this is the original text:

        - 20% : 
            - pick three random 64-bit unsigned integer and assign those different registers
            - do this 3*$$$N$$$ times :
                - pick random two register, and picking randomly between the whole and the lower half part of the register
        	    - apply xor, and, or, add or sub instruction on the two register as operands
        	    - add the three register to the list
            - select every third item from the list
        
        - if the triplet is not valid than try to generate a new one with the same method
        
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve FUZZYLIN . Please Help ?