When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

soumya_27's blog

By soumya_27, history, 3 years ago, In English

Invitation to Codelicious'21

Hello Codeforces!

“Craving for tasty algorithmic programming problems?”
With no language barrier, Codelicious'21 is a Competitive Programming event that will be conducted globally. With tasty and tricky questions, Codelicous'21 will surely satiate your hunger for good quality algorithmic programming problems.

I, on behalf of PICT ACM Student Chapter (PASC) would like to invite you all to Codelicious'21.
We have a huge prize pool of 400 USD (30,000 INR) for top 2 Global and top 2 Indian participants.

Contest Details:

Please register via the google form to be eligible for the prizes.

Global Prizes:

  1. Rank 1 from leaderboard: 175 USD
  2. Rank 2 from leaderboard: 100 USD

Indian Prizes:

  1. Rank 1: 6000 INR
  2. Rank 2: 4000 INR

Good luck to everyone, hope to see you all on the leaderboard!

Also note:
- Prizes are inclusive of all taxes.
- Prizes are subject to change under unavoidable circumstances.
- Management is not responsible for the change in the pool.
- Final decision lies in the hands of the organizers.
- In case any country has any restrictions on prize money transfer we shall not be responsible.

Update: Contest begins in a minute. All the best!

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

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

Auto comment: topic has been updated by soumya_27 (previous revision, new revision, compare).

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

Looking Forward to this event!!

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

As a tester, I really recommend playing this round!
Tasty problems with amazing prizes!!

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

As one of the tester of this contest, I will definitely recommend everyone to play this contest and get ready to solve some really good problems. Good Luck Everyone! See you guys on Leaderboard :)

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

Great going PASC. Looking forward to play this contest!

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

is it rated?

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

    No, it won't be a rated contest.

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

      thanks,anyways i will participate ,hope problemset is good

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

Reminder: contest starts in ~1 hrs! (9 pm IST)
We have Global as well as India-level prizes, so be sure to participate!

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

How many problems

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

Auto comment: topic has been updated by soumya_27 (previous revision, new revision, compare).

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

In the problem CDS05, should the answer be printed modulo some value?

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

    I also have the same query. Did you get the answer?

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

      I just got AC by submitting modulo 10^9 + 7.

      Honestly, this is a pretty bad preparation error, and I have no idea how it wasn't caught during the testing process.

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

    We are sorry for the inconvenience caused.

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

Could a sample explanation be provided for CDS07? I don't think I understand the procedure described, and I'm not even sure what the answer to the sample is supposed to be as a fraction.

UPD: I think I'm following the sample input now, but an explanation would still be helpful to confirm that my interpretation of the problem is correct.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it
    2 2
    aa
    aa
    Subsets are
    {} => Lose 
    {aa} will be converted to {a#} or {#a} or {#} => Win Probability = 1 / 4
    {aa} will be converted to {a#} or {#a} or {#} => Win Probability = 1 / 4
    {aa, aa} will be converted to
    a# a# Win
    a# #a Lose
    a# # Lose
    #a a# Lose
    #a #a Win
    #a # Lose
    # a# Lose
    # #a Lose
    # # Win
    Win Probability = (1 / 4) * (1 / 3)
    Total Probability = 7 / 12
    
»
3 years ago, # |
Rev. 3   Vote: I like it +57 Vote: I do not like it

Thanks for the round--I thought the problems were quite nice! I do think the round could perhaps have done with a bit more preparation: in particular, the modulus in Count the Count wasn't initially specified, and a few of the problems had very weak and/or unexplained samples (which is relatively common on Codechef but can make it somewhat harder to understand the problems). In particular, I found the game theory problem a bit ambiguous because it was unclear from the problem statement whether we would select $$$Y_i$$$ for each string and then pick a random substring with that length to erase, or if we create a list containing all possible substrings to erase and pick one of those at random. Overall, though, I enjoyed the contest, and I'd definitely encourage the authors to keep writing problems.

Brief outlines of my solutions, in increasing order of problem difficulty (judging by solve counts):

Array Subarrays: A naive solution works here. Just split the array into $$$\frac{N}{K}$$$ subarrays of length $$$K$$$, reverse the ones in odd positions, and build the resulting array using the first subarray and the last element of all subsequent subarrays.

Count the Count: We can prove that the only way in which the resulting permutation can differ from the identity permutation is by swapping two adjacent elements. Therefore, in order to construct an array of N elements, we can either take a valid array of N-2 elements and add N and N-1, in that order, or we can take a valid array of N-1 and add N to the end. This means that if ans[i] is the answer to the problem when N = i, we have ans[N] = ans[N-1] + ans[N-2]. We can precompute these values (which are simply the Fibonacci sequence) for all possible values of N in O(maxN) time.

Soumya Wants to Buy a Tree: This is a relatively standard rerooting DP problem. We root the tree arbitrarily and first compute the answer for the subtree rooted at each vertex. Then, we traverse the tree again in order to compute answers for the whole tree. See my code for details. It's helpful here to observe that we can color the vertices black and white such that all edges connect a black vertex and a white vertex; then, the power of $$$-1$$$ in the cost function will be positive for exactly the set of vertices with the same color as the root.

GCD Operations: The answer must clearly be less than $$$A[i]$$$ for all $$$i$$$, so it is bounded by $$$10^6$$$. We check whether all GCDs from $$$1$$$ to $$$10^6$$$ are possible individually. The trick here is that we can compute the minimum number of operations necessary to achieve a given GCD $$$G$$$ in $$$O \left(\frac{\max A_i}{G} \right)$$$ after $$$O(\max A_i)$$$ precomputation using prefix sums (basically, for each multiple of $$$G$$$, we count the number of elements of $$$A$$$ for which this multiple of $$$G$$$ is the greatest multiple of $$$G$$$ less than $$$A_i$$$). Then, we can check if the total number of operations necessary is less than or equal to $$$K$$$, and update our answer if so.

Weird Divisibility: This problem has a fairly standard DP solution. Our state is the number of digits we've processed and the current sum, modulo $$$K$$$. Then, there are ten transitions from each state (ten possible values for the next digit). We can verify that $$$10NMK \leq 8 \cdot 10^7$$$, meaning that this approach should comfortably fit within the time limit.

Equation: The key observation is that if there is any valid solution $$$P$$$ for a fixed $$$Q$$$, then taking $$$P = 1$$$ must also work. This is because if $$$K P 2^Q \leq N < KP2^Q + K$$$, then we can replace $$$K$$$ with $$$KP$$$, at which point $$$KP 2^Q \leq N < KP2^Q + KP$$$ must hold. In other words, we only need to check that powers of two work. This allows us to implement a reasonably straightforward brute force solution, as finding the largest multiple of a power of two less than a given integer is relatively easy.

Special Event: First, if $$$A = B$$$, then the answer is yes if and only if $$$K = 0$$$. Similarly, if $$$K = 0$$$, the answer is yes if and only if $$$A = B$$$. Now, suppose $$$K > 1$$$. We claim the answer is always yes. If either value is not yet zero, then we make one of the values zero by, if $$$A > B$$$, setting $$$A = \lfloor \frac{B}{A} \rfloor.$$$ Then, assuming $$$A = 0$$$ and $$$B \neq 0$$$, we repeatedly set $$$B = A-B = -B$$$ until we've used $$$K-1$$$ moves, after which we set $$$A = B-A = B$$$ as our final move. Thus, the answer is always yes when $$$K > 1.$$$ It remains to deal with the $$$K = 1$$$ case, but here, we can simply check directly if any of the four moves work.

Is This a Game Theory Problem?: First, notice that we can compute hashes of all possible output strings corresponding to a given input string in $$$O(|H_i| \log |H_i|)$$$. Then, we process the input strings in order, maintaining, for each possible hash, the probability that all strings chosen so far have resulted in this particular hash. This probability can be updated using some relatively straightforward calculations; check my code for details.

Happy to answer questions about my solutions below! Obviously, these are very hasty/incomplete writeups, so if you're confused about my approach, checking my code may be helpful. I don't think my code for any of the problems got overly messy, so it hopefully shouldn't be too hard to follow.