kingofnumbers's blog

By kingofnumbers, 3 months ago, In English,

Hello CodeForces Community!

We’re back with a new and exciting set of coding challenges with the July Cook-Off 2018 sponsored by ShareChat. Plus there are some exciting job/internship opportunities by ShareChat for participants. More details on the July Cook-Off contest page here:

Looking forward to seeing your participation in yet another exciting monthly contest! Joining me this time on the problem setting panel are:

  • Problem Setters: kefaa (Kirill Gulin), kingofnumbers (Hasan Jaddouh)
  • Problem Tester: isaf27 (Ivan Safonov)
  • Editorialist: vijju123 (Abhishek Pandey)
  • Statement verifier: xellos (Jakub Šafin)
  • Russian Translator: Fedosik (Fedor Korobeinikov)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: (VNOI Team)

Contest Details:

Time: 22nd July 2018 (2130 hrs) to 23rd July 2018 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone

Contest link: codechef.com/COOK96

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 winners@codechef.com)

Good Luck!

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

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

STICKS2 was a horrible problem

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    For me only terrible thing is that I am so stupid and couldn't figure what is wrong in my submission for 1.5.hours and after it made again 3 stupid bugs.

    The fourth problem looks easier to me, It is really pitty that I didn't have enough time to code it correctly.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    yes, it's tricky problem (among all 32 people who solved it only 3 got it from first submission). but why is it horrible?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      is Tree question, HLD + auxilary tree ??

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        not really, it can be solved using 1D persistent segment trees in O((sum of K) * log n)

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

How to solve F2NDMAX?

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

    I think you should make DAG with current constraints. After it all elements with in-degree 0 should be merged like segment tree.On that way you can get maximum, after it second element is one over the path of maximum in that segment tree. You will have approximately x log(x) queries, where is x amount of elements with in-degree 0.

    I didn't get AC, but I believe it is correct.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      You should also consider elements which are part of contraints and lost only to those with zero degree to be candidates for second maximum.Now since each vertex has weight. it wont be a segment tree. we want to minimize wt to a leaf from root of the comparison tree constructed which can be done using priority queue,

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

        Maybe I am wrong but I think only one such element should consider — second of the maximum.

        EDIT: I see my mistake, thank you!

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

        Can you please sketch your solution ?

»
3 months ago, # |
  Vote: I like it -27 Vote: I do not like it

?detaR tI sI