Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

kingofnumbers's blog

By kingofnumbers, history, 19 months ago, In English,

Hello CodeForces Community! I would like to take this opportunity to extend this invitation for CodeChef May Cook-Off. As usual it is scheduled for the second last Sunday of the month.

Joining me on the problem setting panel, we have:

You will be provided by 5 problems of various difficulties to solve during 2 hours and 30 minutes, I have found the problemset very interesting and I recommend coders of various skills to participate especially GrandMasters, please feel free to provide your feedback in the comments section after the contest, I hope you will enjoy solving the problem set.

You can find the rest of the details about the contest below.

Time: Sunday, 21st May, 2017 at 21:30 HRS (IST) (Indian Standard Time — +5:30 GMT) — Check your timezone.

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

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

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

»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

25 minutes left to start!

»
19 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Did someone manage to solve "Nasty Queries" using a Segment Tree?

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No and I didn't even try. Hashing is the way to go — check if the xor of all edge endpoints in the given range is 0 and if some other prefix hashes (for example polynomial hash of vertex degrees) are equal. Fast, simple, fairly reliable.

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

      I had an approach like give each vertex a prime and its inverse for the sake of hashing.

      for l to r. ans[l] *inv(ans[r-1]) . if it is 1 yes else no

      Is it hackable??

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    They intend to kill an easy solotion with MO. :(

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

      Well I got Mo's solution through, so I guess killing Mo's is not so easy :)

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Here is my solution 13704547.

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

        MO was intended to be killed. I think all people except you got TLE :D

        I think we should have set the TL to 1second :P

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

          Nope :) My MO is got AC Too: 13702714

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

            Even before seeing comments here I checked the submissions page and I saw a lot of TLE based on sqrt and MO and these stuff.

            Anyway this problem turned to be the 3rd easiest , so I don't really mind :P

        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Question for you, in these short contests on Codechef is the Java time limit indeed 2x? I am certain that in the long contests it is because I can see runtimes on cases, but here I am not sure.

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can anyone point out the bug in my code problem:Nasty Queries , I used MOS,

        code

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach Nasty Queries?

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The degree of any vertex must be even.

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

      Yes but why does the solution use hashes? Sorry if this is a stupid question.

      • »
        »
        »
        »
        19 months ago, # ^ |
        Rev. 3   Vote: I like it +7 Vote: I do not like it

        The degrees are even means all the endpoints in the given query range appear even number of times. So your query basically is to check if there's any element with odd frequency in given range.

        You can do that by checking if the xor of elements in that range is zero (if each number appears even number of times, they cancel out in pairs). This solution might give wrong decisions for some set of values like: 1, 2, 3. Even though their xor is zero, all of them have odd frequency.

        The idea is to hash each number from 1 to n to distinct and very large numbers chosen randomly so that the probability of such sets occurring becomes very small. Then you can simply check for zero xor.

        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks! :)

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

          I got it, but what if you are submitting such a solution on codeforces where you will not be able to know whether your randomization failed or not till the end of the contest ?

          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
            Rev. 4   Vote: I like it +18 Vote: I do not like it

            Yes you can't know but you can take safety measures to reduce the failure probability to almost zero. On CF I'd probably use 4 - 5 different hashes (in fact, you can take around 50 hashes in this constraint). I'd answer "Yes" only if all of them gave zero. It's close to impossible for such solution to fail.

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

          Could you tell how to design such hash function.Any resources would be useful.

          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            Just assigning a large random number to each value from 1 to n suffices. I did the following.

            const long long MOD = 1e14 + 7;
            
            for (int i = 1; i <= n; ++i) {
              hashValue[i] = (rand() * 1LL * rand()) % MOD;
            }
            

            There's no need to "design" any hash function here. You just need the numbers to be scattered enough so that there's no range with xor zero. For the xor to be zero you need even number of ones in every bit position, the probability of which gets smaller as the number of bits increase.

            Here's my code if you need reference.

»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

That deceiving scoreboard submissions got me again. For 2 hours i was trying to squeeze C with either bitset+sqrt -_-. And then read D in last 30 mins. Solution to D appeared so easy to me with just Deque use (Submission)

Btw did anyone do C without hashing? I really hope there exists some solution without hashing.

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    here. Can this idea be hacked with some clever test case??

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

      Yes, it is very much like hashing only so hackable. Infact it is very easy to generate hack cases if prime numbers aren't random.

      Your solution fails on this case:

      1986 4
      1 3
      1 6
      1 276
      1 1986
      1
      1 4
      
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody tell bug in my code of nasty query

simple approach through xor code

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

    Try this case:

    10 3
    1 2
    1 4
    3 5
    1
    1 3
    

    Your code would give "Yes", but answer is "No".

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fails if the numbers in range are 2, 3, 4, 5.

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

    thank you both of you i got my bug. can you suggest one method two overcome it?

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Hussain set, some solutions with 10*N*log(10*N) also passed. Mine not among them :(

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for Hussain Set?

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    First of all sort numbers in asc order , then group them by the most significant bit. Iterate on the buckets from the most significant to the least. After you finish a bucket divide all its elements by 2 then merge it with the previous one in O(n) (merging 2 sorted sequences).

    complexity N log N + 64 * N

»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve E ?

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

    An editorial will be posted soon I think. The idea mainly was to keep data about only some potential nodes, in this problem It's necessary only to keep data about ancestors of deleted nodes. And when deleting a node you just need to go and update its ancestors, and update their data based on the time shift occurred since the last update. Afterwards just iterate through them and make changes due the deletion of the node.

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "Soon"...

      It is really annoying when the editorials for a contest are not posted. This is also the case for CodeChef's recent long challenge. Only the editorials to easier problems were posted, I am still waiting for an editorial to the KILLER problem. Similar thing has happened before too. I wonder when CodeChef will fix this problem of incomplete or no editorials.

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am also waiting for the editorial of E. mathecodician, How many days more?

        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I am not writing for E. I wrote the other 4. The problem required tries which I do not know yet so I asked Praveen Dhinwa. He said he'll write it for that problem.

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Any updates on the editorial? Or can anyone share their approaches?

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I submit after the contest?

»
19 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Is there any deterministic solution for problem D?