chokudai's blog

Panasonic Programming Contest (AtCoder Beginner Contest 195) Announcement
By chokudai, history, 3 years ago, In English

We will hold Panasonic Programming Contest (AtCoder Beginner Contest 195).

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

Comments Comments (16)
| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why it's called Panasonic contest? What is the benefit for Panasonic and participants?

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

Starting soon!

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

How to solve B and D ??

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

How to solve E,F?

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

Can someone please tell me what's wrong with my approach in E? (getting wrong answers on 15 test cases :( )

link to submission.

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

    Did you find the mistake in your solution? My submission is also failing on those 15 cases.

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

      no, i still couldn't able to figure out till date why my submission is failing on 15 cases:((

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

Hints for problems :

A. Check if H%M is zero.

B. Assuming that mangoes can provide all values between A to B inclusive, we can buy, say i mangoes only if i*A <= W <= i*B. So range of mangoes that can be bought is [ceil(W/B), floor(W/A)].

C. Count how many numbers for each digit count are there that lie between 1 to N inclusive. Say there are K numbers for D digits. Then answer gets incremented by ((D-1)/3)*(K).

D. For each query, find the respective available boxes and keep a sorted array of baggages on the bases of value. Then try to add the most expensive baggage by value to an available box that has size just more than the baggage size. Time Complexity would be O(Q*N*log(W)).

E. Let us build dynamic programming from the right of the string for the game. The states are (position, previous result modulo 7). For transition, consider if it is Takahashi, he tends to visit a new result (only 2 possible new results for a current previous result, ie, taking 0 or S[i] as the current digit) so that the next state's winner is Takahashi and the same for Aoki. Time Complexity would be O(7*N) or O(N) only.

F. Consider reading about SOS dp and meet in the middle as it is a prerequisite for the same. Since we are given, say N(<=73) numbers, so nearly half of them would be even. And among all even numbers, final set can only consist of a maximum of 1 even number. So that leaves us with nearly 36 odd numbers. So for each even number, find set of all odds that is coprime with the even number. For each such set, we need to solve the same problem. In order to solve for 36 odd numbers, we can partition the set into 2 sets of nearly 18 odd numbers. Calculate all valid subsets of both the newly built partition sets that are viable among themselves. For each element from first set, lets denote it by mask, we can obtain a supermask that corresponds to the set of allowed elements from the second set for that mask. To get the count of sets corresponding to a supermask in the 2nd set, we can build a SOS dp over the second set's mask. This gives us all possible valid masks from second set for a particular mask from first set. We can add the answer for each such element from first set to the final answer. Do not forget the case when no even number is chosen. Time Complexity would be O((N/2)*(2^(N/4))*(N/4)), where N = (B-A+1).

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

    .

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

    Neither SOS DP nor meet in the middle are required in problem F. A simple bitmask DP is enough. Just consider the primes up to 72. There are 20 such primes. Now consider dp[i][mask] = number of ways of choosing the a subset of first i numbers and having used the primes present in mask. Transitions in this dp are O(1) for complexity O(72*2^20)

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

      You're right, didn't consider that any other prime only appear once in the range, Thanks for the solution!

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

Is that only me or someone else also found B more difficult then A,C,D

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

    I did acde but not b lol. Later realised the weight doesnt need to be integer

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

      And even later realised that the weight being an integer does not change the problem

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

Problem A was so easy still I did w.a(in hurry to solve it fast).by printing "no" in lower case. Ended up only solving a,b,c this time. :(

→ Reply