hloya_ygrt's blog

Invitation to CodeChef May Cook-Off 2018!
By hloya_ygrt, history, 6 years ago, translation, In English

Hello CodeForces Community!

We always look forward to offering you a fresh set of challenges to test your coding skills upon and we are back with the May Cook-Off 2018 sponsored by ShareChat. In addition, there are some exciting job/internship opportunities by ShareChat in the May Cook-Off 2018. For more details, you may visit the May Cook-Off contest page here: https://www.codechef.com/COOK94

Looking forward to seeing bright minds like yours come together to be the best! Joining me this time on the problem setting panel are:

  • Problem Setter and Editorialist: hloya_ygrt (Yuri Shilyaev)
  • Problem Tester: Pepe.Chess (Hussain Kara Fallah)
  • Statement Verifier: Xellos (Jakub Safin)
  • Russian Translator: hloya_ygrt (Yuri Shilyaev)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: (VNOI Team)

Contest Details:

Time: 20th May 2018 (2130 hrs) to 21st May 2018 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone

Contest link: https://www.codechef.com/COOK94

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://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie

(For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck!
Hope to see you participating!!
Happy Programming!!

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

Comments Comments (13)
| Write comment?
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Starts in 5 minutes.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Cam somebody find counter-test for my solution to SHEFPIC? For some reason it got AC. The idea is to find for each point 5 closest points and from this 5 closest points find 2 of them, that form the smallest square with given point. Now sort this triples of points in order of increasing size of square for each triplet. Go from the triple with smallest square to triple with the highest square and mark used[x1] = used[x2] = used[x3] = true if x1, x2 or x3 are not used or delete this triple otherwise. Now find maximum square from remaining triples. Complexity is O(5·T·N2)

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

How to solve Difficult Choice?

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

    Do 1 dfs run on the tree, keeping track of number of vertices that satisfy the condition in a pair with the root vertex (class 1), and the ones that don't (class 2). It turns out, that all pairs of vertices belonging to the same class also don't satisfy the condition. And then it is just arithmetics.

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

    Define a root and calculate distance from that root to all node with dfs. But Take dis mod 2

    Then define g[i] = v[i]^dis[i] Answer will be #nodes which g[i] has odd 1's bits x #nodes which g[i] has even 1's bits.

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

      Silence_for_Melody Can you please Explain more ?

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

        I will give you the theory behind and you have to figure it out, sorry for my English since now.

        You must know some properties about trees and XOR operation.

        1. Given a rooted tree, a Lowest Common Ancestor of two nodes u,v is a node w which is an ancestor of u and v and its height (measured from root – root has height 0, his direct neighbors had height 1 and so on) is as big as possible. This node w could be equal to u or v. For more information, you can check this tutorial. We will not use this but the concept is part of understanding my solution.
        2. A well know problem to apply LCA is to find distance between any pair of nodes in a tree. You can try it here. The property said that dist(u, v) = dist(root, u) + dist(root, v) - 2 * dist(root, lca(u, v)). Please stop here if you do not completely understand this part. Draw a tree in a paper and prove it by yourself. This is important.
        3. Sum of a list numbers mod2 is the same to take XOR between the mod2 of each of them. Again, to be convinced about this do some test in paper and continue.
        4. A XOR A = 0. This is something that you can apply to get XOR of a continuous subarray of array A. You can preprocess XOR of prefixes in XA, so XA[i] = “xor of all the elements until i”. Then, to get xor from itoj just calculate XA[j] xor XA[i - 1]. Again, do some test in paper to understand why this works.
        5. Now let us combine all above. If we define XORDIS as distance between two nodes where the distance is the xor of the lengths of edges in their path, how would you calculate that using concepts of LCA and XOR of prefixes? (Hint: you will not need to calculate LCA).

        For one moment forget about ages in the problem and try to solve the following: How many pairs of cities are so their distance is even? How many there are so their distance is odd?

        Now forget about the distance on work over ages. How many pairs of cities there are so the bits in their XOR are even? How many there are so the bits in their XOR are odd?

        Last, and what makes this problem awesome, observation: When you want to evaluate parity of bits in the XOR of A and B, does the order of bit in A and B matter? Just think about it. Hope everything is clear

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

Editorials are out on codechef!

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

    Where are the editorials? Can you give me the link? I am not able to find it.

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

For the problem Difficult Choice , in the editorial its mentioned that |au⊕av| % 2=(|au| % 2)⊕(|av| % 2). where |x| be the number of one-bits in binary representation of x

Can someone help me prove the statement ? Thank you :)

→ Reply