kingofnumbers's blog

Invitation to CodeChef May Cook-Off!
By kingofnumbers, history, 8 years 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:

  • Problem setter: Pepe.Chess (Hussain Kara Fallah)

  • Testers: kingofnumbers (Hasan Jaddouh) and iscsi (Istvan Nagy)

  • Editorialist: T1duS (Udit Sanghi)

  • Language Verifier : arjunarul (Arjun Arul)

  • Russian Translator : CherryTree (Sergey Kulik)

  • Mandarin Translator: huzecong (Hu Zecong)

  • Vietnamese Translator: VNOI Team

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

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

25 minutes left to start!

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

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

→ Reply
  • »
    »
    8 years 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.

    → Reply
    • »
      »
      »
      8 years 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??

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

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

    → Reply
    • »
      »
      »
      8 years 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 :)

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

        Here is my solution 13704547.

        → Reply
      • »
        »
        »
        »
        8 years 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

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

          Nope :) My MO is got AC Too: 13702714

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years 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

            → Reply
        • »
          »
          »
          »
          »
          8 years 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.

          → Reply
      • »
        »
        »
        »
        8 years 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

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

How to approach Nasty Queries?

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

    The degree of any vertex must be even.

    → Reply
    • »
      »
      »
      8 years 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.

      → Reply
      • »
        »
        »
        »
        8 years 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.

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

          Thanks! :)

          → Reply
        • »
          »
          »
          »
          »
          8 years 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 ?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years 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.

            → Reply
        • »
          »
          »
          »
          »
          8 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years 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.

            → Reply
»
8 years 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.

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

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

    → Reply
    • »
      »
      »
      8 years 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
      → Reply
»
8 years 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

→ Reply
  • »
    »
    8 years 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".

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

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

    → Reply
  • »
    »
    8 years 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?

    → Reply
»
8 years 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 :(

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

Solution for Hussain Set?

→ Reply
  • »
    »
    8 years 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

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

How to solve E ?

→ Reply
  • »
    »
    8 years 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.

    → Reply
    • »
      »
      »
      8 years 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.

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

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

        → Reply
        • »
          »
          »
          »
          »
          8 years 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.

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

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

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

How can I submit after the contest?

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

Is there any deterministic solution for problem D?

→ Reply