Andrei1998's blog

Invitation to CodeChef December Long Challenge 2018 sponsored by ShareChat!
By Andrei1998, history, 6 years ago, In English

Hello Codeforces community,

You are invited to CodeChef December Long Challenge 2018 sponsored by ShareChat. This is a 10-day competition with 8 problems and it’s open to programmers across the globe. The contest problems will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

Participants will also be in the running for some exciting jobs at ShareChat — India’s fastest growing social network. To apply, all you need to do is fill the application form on the contest page and participate in the December Long Challenge.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

Contest Details:

  • Start Date & Time: 7th December 2018 (1500 hrs) to 17th December 2018 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
  • Contest link: https://www.codechef.com/DEC18
  • 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. First to solve each problem except challenge — 100 laddus. 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!! Happy Programming!!

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

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

How to solve CBFEAST?

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

    Let's try to solve an easier task first:

    We start with an empty set and have three types of queries:

    1. insert number in the front
    2. insert number in the back
    3. say what is the maximal subarray sum

    We can solve this by maintaining four integers for the given set:

    1. maximal prefix sum
    2. maximal suffix sum
    3. sum
    4. maximal subarray sum

    Now when we insert a number in the front:

    1. the new maximal prefix sum will be equal to max(0, old maximal prefix + inserted value)
    2. the sum will be equal to old sum + inserted value
    3. the new maximal suffix sum will be equal to max(sum, old maximal suffix)
    4. the new maximal subarray sum will be equal to max(old maximal subarray sum, max(maximal prefix sum, maximal suffix sum))

    When we insert a number in the back it is similar.

    Ok so we solved that easier task. For the original task we just need to maintain a segment tree with such a structure in each node (the four numbers). We keep two lazies — one for queries which insert in the front and one for those queries which insert in the back.

    When we have an update query we will do a range update in the interval [c - K; c + K]. And when we have query to print an answer we just do a index query on c.

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

hot to solve INT_XOR

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

    First ask 1 2 3 and 1 2 4, which gives you 3^4. Then asking 3 4 5 and 3 4 6 would give you 5 and 6 Then you can ask 5 6 7, 6 7 8, 8 9 10, ...

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

    You can ask these triples: 1 2 3, 2 3 4, …, N–2 N–1 N, N–1 N 1, N 1 2. Then, if you xor these triples you will have a1^a2^a3^a4^ …^aN. If N % 3 == 1 or N % 3 == 2 it’s easy to see that you can find any value of this sequence. But If N % 3 == 0 you can divide your sequence into two and find answer for each subsequence independently. My solution: https://www.codechef.com/viewsolution/21925944

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

How to solve EDGEDIR. I was thinking of greedy approach where I take edge count (in-degree and out-degree both) for each node, then start solving with the nodes having the smallest edge count till the nodes having the most edge count.

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

    My solution is:

    Take a random direction for each edge and after that mark all nodes which currently have odd in-degre with 1s and all the remaining nodes with 0s. It can be easily proven that if M is even there will be even number of 1s after this operation. If M is odd then the answer is -1.

    Now we need to change the direction of some edges to make all the nodes marked with 0 (make those which are currently marked with 1 to 0). We can see that if we take a randon path of the form (1->0->0....->1 (starting and ending with ones and 0 or more zeroes in between)), and we change the direction of each edge in this path the only thing that will change will be that the two ending nodes (the two 1s will become 0s). So we only need to pair the nodes marked with 1 in pairs find a random path between each pair and change the direction of edges on this path.

    One way to do thia is to take a random spanning tree and do a dfs to count subtree sizes(considering only nodes marked with 1) for each node in the spanning tree then for each node if the number of nodes marked with 1 in the subtree is even then we can match them in the subtree itself and we don't have to do anything. Else if the number is odd then we need to change the durection of the edge which leads to the parent of the current node.

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

    https://mirror.codeforces.com/blog/entry/11186?#comment-162599

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

    Can anyone point out in what test-cases mentioned greedy approach will fail?

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

When will official editorials be published ?

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

How do we solve BHD and BICONT?

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

    +1 Specially for Bicont. I have tried going through the solutions but am unable to wrap my head around them. Any hints would be highly welcome. Thanks in advance.

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

      Hint1: Can you compute dp[node][i][...other things...] = how many ways are there to split node's subtree into i node-disjoint biconnected components? (note: this dp may overcount!)

      Hint2: To remove the overcounting, try looking up "Binomial Inversion".

      → Reply