Pepe.Chess's blog

Invitation to CodeChef December Cook-Off 2018 sponsored by ShareChat!
By Pepe.Chess, history, 6 years ago, In English

Hey Codeforces community,

You are invited to CodeChef December Cook-Off 2018 sponsored by ShareChat. This is a 2.5-hour competition with 5 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 Cook-Off.

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

  • Tester: Deemo (Mohammad Nematollahi)

  • Setter and Editorialist: Pepe.Chess (Hussain Kara Fallah)

  • Statement Verifier: Xellos (Jakub Safin)

  • Mandarin Translator: huzecong (Hu Zecong)

  • Vietnamese Translator: Team VNOI

  • Russian Translator: Mediocrity (Fedor Korobeinikov)

  • Bengali Translator: solaimanope (Mohammad Solaiman)

  • Hindi Translator: Akash Shrivastava

Contest Details:

  • Start Date & Time: 23rd December 2018 (2130 hrs) to 24th December 2018 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone

  • Contest link: https://www.codechef.com/COOK101

  • 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
  • +45
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Will this contest have editorials ? Just asking because it's more than 1 week since December Long challenge has completed but the official editorials are still not published ! :(

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

no collision with technocup....YAY..

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

How to solve CSUBSQ?

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

    Divide and Conquer. calculate mid to every r and every l to mid. Now take prefix sums for finding answer with constraint.

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

      As an alternative, calculate prefix sums and suffix sums for all possible "division points" with a step of W; after that, you can say that every segment of length W touches/crosses some division point, so you can construct it by combining results for prefix and suffix which start at this point.

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

        SO you count each segment based on its first division point or last division point it contains.

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

          Sorry for not being clear enough in my initial comment.

          I'm saying that the answer is "all subsequences minus bad subsequences". I am counting all subsequences with trivial DP and then doing this "division points" stuff for "bad subsequences".

          In this case, I need to find number of sequences which are lying withing a segment of length W — in order to avoid counting something twice I can say that first element of the segment should always be taken. After that, the segment that I work with contains exactly 1 division point (or starts right after division point and ends right before the next one).

          My code from the contest: link.

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

How to approach last one?

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

    use inclusion exclusion so instead of having A <= x <= B you will have x <= Y

    for each mask you will have y1,y2,y3... you need to count how many ways you choose

    x1 <= y1 , x2 <= y2 ... and S = x1+x2...

    Digit dp after you extend all to 9 digits

    [which digit][mask][sum][carry][number_you_are_on]

    mask says for each number whether it's less than or bigger than its corresponding y

    I think you can continue from here

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

      For sum I think you need to store it special format right. I was thinking of some which has 10^3 states Like previous digit, number of 9's from second previous digit onwards and one more non 9 digit. Or just mapping or something work?

      Also when you have sum why carry is needed?

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

        oh no, imagine all numbers stacked

        xxxxx

        yyyyy

        zzzzz

        #########

        sssss

        you start from least significant digit, and build your sum as you go forward, so you build your sum digit by digit from least significant to most significant and after you finish each digit you check if it's included in our desired bounding interval

        [digit = 9][mask = 2^n][sum = 0..9][carry = 0..n][n][2]

        You need to handle zeroes in the sum because they could be leading (so you shouldn't break always with 0 if A > 0) I do it with 2. Mohammed solution doesn't need it (just few cases handling) but I just wrote it the less ifs way

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

      Am I right that we can also improve complexity by substituting 2^7 inclusion/exclusion DPs each having 2^7 states for current state of numbers with a single DP having 3^7 states for numbers? Something like "Prefix of i-th number either matches prefix of L, or matches prefix of R, or is already in-between"?

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

Can SOSTD be solved by sorting two arrays with respect to one array and applying divide and conquer on the other array?

UPD: No. I was wrong. Sorry. I realized my mistake.

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

How to solve YVSTR?

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

    nikesh04 you see all the good non-empty substrings are in the form of (a)+ or (a)+(b)+, where a and b are two distinct characters.you just need to count the distinct substring of this form.

    I will tell you my approach. for all the substrings of (a)+, we can simply calculate the prefix array and take max for each character. for a substring of type (a)+(b)+, you can take array max[26][26][N] where max[i][j][k] represents maximum continuous character(j) after continuous k character(i) . for memory issue, just use map.

    you can look at my solution : https://www.codechef.com/viewsolution/22068155

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

      "max[i][j][k] represents maximum continuous character(j) after continuous k character(j)".What does this line meant to stay?

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

        if there are k number of continuous character 'i', how many maximum numbers of continuous character 'j' are present in the given string. i.e. if the string is aaabb,

        max[0][1][1]=1; after 1 continous 'a',there are maximum 2 continous 'b'.

        max[0][1][2]=1; after 2 continous 'a',there are maximum 2 continous 'b'.

        max[0][1][3]=1; after 3 continous 'a',there are maximum 2 continous 'b'.

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

How to solve SOSTD?

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

    Editorials are ready to be published, I am just waiting for the admin to do it

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

All editorials are posted in discuss.codechef

→ Reply