mgch's blog

By mgch, 8 years ago, translation, In English

Hello CodeForces Community!

The monthly programming action takes the centre stage once again after SnackDown 2016 Finale. I hope you all are ready to get back to your weekly dose of programming. So, let’s start.

I’d like to invite you to the CodeChef July CookOff 2016 CodeChef July Cook-Off. This time, the Cook-Off will happen as per its usual time i.e., on the second last Sunday of the month. Joining me on the problem setting panel are:

  • Problem Setter: mgch (Misha Chorniy)

  • Problem Tester: karanaggarwal ( Karan Aggarwal)

  • Editorialist: pushkarmishra (Pushkar Mishra)

  • Russian Translator: CherryTree (Sergey Kulik)

  • Mandarin Translator: huzecong (Hu Zecong)

  • Vietnamese Translator: VNOI Team

  • Contest Admin and Language Verifier: PraveenDhinwa (Praveen Dhinwa)

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below after the contest. You can find the rest of the details about the contest below.

Time: 24th July 2016 (2130 hrs) to 25th July 2016 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK72

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

»
8 years ago, # |
  Vote: I like it +46 Vote: I do not like it

When will the laddu system start ? It's been months -_- .

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

Reminder, contest just started !!

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

How to solve Chef and Sort?

»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I'm surprised the last problem wasn't solved more often.

An expected value problem like this one is clearly solved by finding linear formulas for expected values of some states.

In this case, the states should be cycle lengths, since a swap either merges 2 cycles or splits a cycle into two. The order of cycle lengths doesn't matter, which reduces the number of possible states to S = 42 for N = 10. We can find them by some optimised backtracking and map arrays of cycle lengths to integers in O(S4).

The rest is just computing the number of ways to go from any state to any other — again in O(S4) and GEM in O(S3) to find the expected values. The time complexity should be something like O(S4) with a good constant.

»
8 years ago, # |
Rev. 8   Vote: I like it +66 Vote: I do not like it

Solution for Chef Land by romanova:-
Update : Even the tester's solution is random output :D
Update : Fixed username xD
Update : This just keeps getting better and better. The same solution when resubmitted in practice gives WA ----> Link

ProStuff
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    is a counter case for this even possible?

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

      Apparently it is about some luck as well — as you can see, there is 15% chance to not even reach the end s-shaped path when starting from its beginning and doing this kind of random walk for 1e5 moves.

      Can anybody tell me how to calculate chance to pass such figure from all positions? The fact that string is good for starting from first position doesn't mean it is good for reaching finish from second cell of s-shaped labyrinth, but I have no idea how to find probability of random string being good for all possible starting positions in given labyrinth at the same time.

      Just in case, I mean something like this:

      ####################
      #C.................#
      ##################.#
      #..................#
      #.##################
      #..................#
      ##################.#
      #..................#
      #.##################
      #..................#
      ##################.#
      #..................#
      #.##################
      #..................#
      ##################.#
      #..................#
      #.##################
      #..................#
      ##################.#
      ####################
      

      And even this particular case can be made harder with some small modifications.

      Upd. And now I think I had some bugs while considering pairs/groups of cells, because after some thinking if looks like for this particular map starting from 2nd cell is strictly better than starting from 1st — in case you can reach finish from 1st cell, you can make it from 2nd as well, as first path can't simply outrun second somehow.

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

    Embed related.

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

    I was curious why nobody is solving it instantly, and also it sounded like expected hitting time for worst case is rather high (O(N^2) for a line of length N, right?), so I started to code other problem instead, and even after seeing AC solutions on this problem I decided to add while(true) with checker there :)

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

      My solution is even worse. Atleast you are printing 105 characters, I'm just printing any arbitrary dfs tree with the root of the dfs as the capital city — The length of the answer string is  < 2 * N * M.

      Code
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    When you solve a problem in a nice way and your boyfriend gets all the credit (see rev. 4).

»
8 years ago, # |
Rev. 2   Vote: I like it -20 Vote: I do not like it

I used a simple approach which guaranteed to give a solution which satisfy given constrain but i am not able to prove char constrain. Let say you have string 'ans' which stores char sequence. From any cell having '.' , first traverse the 'ans'. If during traversal if it passes through the capital city then no string need to append to 'ans' but if it will not pass then keep the last position of cell after traversal through current 'ans'. Then do a simple dfs from last position to capital city and append this path to our current 'ans'.

code