starboy_jb's blog

By starboy_jb, history, 5 weeks ago, In English

Discussion Thread.

Problem A: ATM Queue

Problem B: Metal Harvest

Problem C: Painters' Duel

Problem D: Yeetzhee

Contest Link: here

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

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

How to think about D?

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

    I basically wrote brute force with cache. That was enough to pass hard.

    The main idea is we don't re-throw dice in the turn if we still can get the answer. Then I just kept all groups I could have by current turn and iterated which number I get in current turn. Then honestly update vector, sort it and check that given one is still greater in each position.

    Why that works fast? It seems we don't have that many states.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, in the first sample input, why it takes an average of 1.2 dice rolls "If the first and second dice are the same"? My thinking so far: since the first and second are the same, the third dice has to be one of the other five numbers, sometime it will take more than 2 rollings if bad luck strikes, so EV will be 5/6 * 1 + 2 * (1/6)¹ + 3 * (1/6)² + 4 * (1/6)³ + .... , but this EV is already 1.25 something.

      Thank you.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve B?

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

    It seems the most challenging part was to understand the statements. Basically we need to sort all segments, then take one by one and greedy place robots (you actually use each of robots once, not reuse them). Then you might have some suffix left for the robot. We just take next segment and check if this robot can cover it as well. If it can, we do nothing. If it partially covers it, remove that prefix from the segment and then put new robot as described before.

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

      Agreed!

      Understanding the statement was the most difficult part of the problem.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's wrong with this? https://ideone.com/cVxZmG

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

C was fun! Thanks authors! :)

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

    Could you provide any insight or intuition on why the recursion depth is actually low?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Also can someone help me if there is any non-backtracking solution to the same ?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Intuition was this: I have no idea how to solve it other way, applying profile DP or so. Then another idea is we pretty quickly shrink number of valid moves and there are many states where we have only one option. Having fun I implemented simple brute force and that did not get TL.

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

    Is this joke

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it +4 Vote: I do not like it

      Actually not! I am one of those who thinks that there is a word "programming" in "programming competitions". Sometimes it is nice to have good old-fashioned brute force :)

      But your problems are fun too! Thanks to you for making my old brain thinks sometimes :)

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve C?

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Google kickstart/codejam mostly ask problem based on expected value and i am never able to make it. Just gonna enjoy the fact that i am dumb!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are not alone :P

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, you have an exciting opportunity to learn it. Imo, you cannot find a truly involved problem in terms of probability because a few people would solve it. So you only have to understand basics from probability (and presumably a lot more at coding).

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

    Try this may be it'll help