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

wwwwodddd's blog

By wwwwodddd, history, 10 months 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 winners@codechef.com)

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

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

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

It was nice contest

»
10 months 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.

  • »
    »
    10 months 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 :/

    • »
      »
      »
      10 months 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.

»
10 months 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.

  • »
    »
    10 months 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??

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

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

      • »
        »
        »
        »
        10 months 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.

    • »
      »
      »
      10 months 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.

    • »
      »
      »
      10 months 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.

      • »
        »
        »
        »
        10 months 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

»
10 months 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)

  • »
    »
    10 months 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.