wwwwodddd's blog

Invitation to CodeChef February Cook-Off 2018!
By wwwwodddd, history, 7 years ago, In English

Hello CodeForces Community!

As rightly said, ‘practice makes perfect’. Therefore, to help keep your programming skills in great shape, Chef is back with another contest in the form of February Cook-Off 2018 sponsored by ShareChat. In addition, there are some exciting job/internship opportunities by ShareChat for Indian programmers in the February Cook-Off 2018. For more details, you may visit the February Cook-Off contest page.

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

  • Problem Setter: mgch (Misha Chorniy)
  • Problem Tester: wwwwodddd (Ke Bi)
  • Problem Editorialist: Mamedov (Rashad Mammadov)
  • Statement verifier: Xellos ( Jakub Safin)
  • Russian Translator: CherryTree (Sergey Kulik)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: VNOI Team

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 18th February 2018 (2130 hrs) to 19th February 2018 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

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

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 [email protected])

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

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was nice contest

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

While we were doing dp + bin search on CARRAY : wtf but correct.

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

    Even I did something similar. First sort the array. The first element has to be included in the subsequence. Then if the next element along with the previous is on or above the line, we directly include it or else we have to select a larger number. Any idea on how to prove such a greedy formally. I generally rely on intuition which is not a good idea :/

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

      This is a very common greedy approach and can easily be proved using exchange argument. Search 'exchange argument' on google.

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

How to solve CSUBSEQ?

It's easy to calculate 'chefness' and contribution of each character in O(4 * N). But I couldn't figure out how to form it into subset sum problem. Since deleting say, a character 'h' will impact contribution of every 'c' before it.

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

    do dp and maintain states such that number of ['c']['ch']['che']['chef'] seen so far.Observe that k<=32 so we do not need exact value if some value crosses k so . we can do dp in k*k*k*k*n if naively implemented.
    is it expected or any speed ups are required??
    How to solve last one??

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

      How O(nk4) solution can run in 2 sec in this problem?

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

        Isn't it 3*1e8.I think it should pass.unless your implementation is very bad.

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

      For the last one, the task turns out to disconnect an edge and calculate the minimum cost for each component.

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

      For the last one, google 2-median on tree. There are multiple papers, solving it in n log(n) time. I couldn't finish the implementation though.

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

        Hmm.. I didn't know about that. Anyway, my solution is more programming one. The hardest thing in my solution is to count the sum of numbers <= K on the segment L..R in DFS-order. You can take a look, if you can't find google paper for such method I'm going to write it.

        https://pastebin.com/d67zctRX

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

I am a beginner in CP. What will be tge approach for solving CTHREE(2nd problem)

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

    We can find all divisors of a number in . We also notice that the maximum divisors of N for N <= 10 ^ 9 is 1344. So once we have a list of all divisors for a number we can just vary the parameters x,y(as given in question), fixing x,y gives us z as N / (x * y) and we can just count the triples which satisfy the given conditions.

    → Reply