antontrygubO_o's blog

By antontrygubO_o, 2 years ago, In English

We invite you to participate in CodeChef’s June Cook-Off, this Sunday, 5th June, Rated for All.

Time: 8:00 PM — 10:30 PM IST

Joining me on the problem setting panel are:

Also, announcing Scholarship for CodeChef Certification in Data Structure & Algorithms — More than 100 Indian participants in Divisions 1, 2, and 3 will win scholarships for the CodeChef Certification exam (discounted prices). Scholarship criteria can be found on the respective contest pages.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

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

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

Reminder: Contest starts in 30 minutes. Please, join!

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

In div2 difficulty was like B < A < E < D < C imo

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

    how to solve e?

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

      Let dp[i] be the answer if we are currently on i-th pile and didn't take anything from, then we can either move to next pile, or start taking from this one. If we take from this one we can get only dp[i+1] or v[i]-dp[i+1], but we can force v[i]-dp[i+1] for other player only in case of odd c[i]. So if c[i] is odd dp[i] = max(dp[i+1],v[i]-dp[i+1]), otherwise dp[i]=dp[i+1].

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

Is it rated?

I think some people are heavily affected for the rejudge in SPLITANDSUM. Looking for a non-existent bug for many minutes is one of the worst experiences if it is a rated contest...

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

    I am sorry for this issue. The checker was correctly set in testing but mysteriously changed.

    We changed this as soon as we noticed. The issue was fixed early, 20 minutes into the contest, so, even though we understand that this might have affected someone, it's rated.

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

.

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

    I have no idea how to solve Two numbers in a normal way. I just brutofroces small values and noticed a pattern.

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

      This is how i solved C: Firstly, we want to maximize lcm(a, b) and minimize gcd(a, b). So lcm(a, b) should be a*b and gcd(a, b) = 1. Now for two numbers a and b, where a + b = n, their product a*b will be maximum if a = b = n/2.

      • If n is odd, then a = n/2 and_ b = n/2 + 1_.
      • If n is even, then we can't take a = b = n/2 since both of them will be equal. So we will search for the nearest odd number on the left and on the right side of n/2. If n%4 == 0, then a = n/2 -1 and_ b = n/2 + 1,_ else a = n/2 — 2 and b = n/2 + 2.
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Prime gap is how I came up with it.

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

      Odd case is more straightforward:

      n1 = N/2, n2 = N/2 + 1;

      cout << lcm(n1, n2) — __gcd(n1, n2) << endl;

      In the even case either taking the numbers closest to each other with a gap of 2 or 4 will be best (depending on if that gap will create even numbers or not):

      n1 = N/2 -1, n2 = N/2 + 1;

      ll ans = lcm(n1, n2) — __gcd(n1, n2);

      if(n1-1 >= 1 && n2+1 <= N) { n1--, n2++; }

      ans = max(ans, lcm(n1, n2) — __gcd(n1, n2));

      cout << ans << endl;

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

can anyone give some hint for Max Minus Min

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it
    1. Print the first 50 elements for a few random sequences and notice that they all eventually get into a simple cycle.
    2. Find sequences that take the longest to reach the cycle. Look at them to find a pattern and figure out how to fast-forward.
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve SPILT AND SUM.

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

    the smallest bit which is set > 1 times in the elements of the array(let's say m) can be set in all the subarrays in the following division of the array into subarrays: just take exactly 1 occurrence of an element with that the m'th bit set in each subarray. this ensures that the sum of each subarray has the m'th bit set. reason: since for all bits j <= m, we have at most 1 occurrence of j in the subarray, there will be no "carry over" when we do the addition.

    also, if there is no such bit, then obviously the answer will not exist since we can't get >=2 subarrays that have the same bit set.

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

      Can you please tell the approach in Throw and Take. I could solve it till here. We only have to consider one coin for each pile having odd number of coins and from that new set of coins we have to play the game and find the value of (coinsA — coinsB). Right?

      How to solve this..some people applied dp but I am not exactly sure how to apply dp here. Can you please tell your approach.

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

        Sure,

        dp[i][0]->optimal score if we start from the i'th pile and it's Alice's turn

        dp[i][1]->optimal score if we start from the i'th pile and it's Bob's turn

        Now, transitions are kind of easy, we just have to make sure that alice tries to maximize the score and bob tries to minimize it.

        You can view my Submission for details.

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

Can anyone explain the Tester's Solution for the Problem Prefix Suffix Distinct.

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

    Apart from the preliminary conditions, $$$p[i]+s[i]$$$ should be greater than $$$p[n]$$$ as $$$p[i]$$$ and $$$s[i]$$$ have one common element ( $$$ith$$$ ) atleast so it is counted twice both in $$$p[i]$$$ and $$$s[i]$$$ and when we merge those segment the number of distinct elements can't be more than their sum-1 (1 of them was counted twice). That gives us:

    p[n]<=p[i]+s[i]-1
    

    So if $$$p[i]+s[i]<=p[n]$$$ we would return false

    Edit: Didn't tried to prove whether they are sufficient. I have a feeling that some additional conditions should have been there (In my solution, I put some more conditions). Is there anyone who has proved that these conditions were sufficient?

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

      I understand this condition is necessary but I am unable to understand why this is sufficient.

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

Permutation Segments was nice, but I feel the "segment intersection is empty" part should have been well defined. I missed AC because I took the definition to mean "length of intersection is zero", whereas the intended definition was that the intersection of the closed intervals should be zero (calling them segments rather than closed intervals threw me off). The different definitions lead to slight changes in the solution (one line). And the only way to realize that the second definition was intended was to analyze the missing permutations of test case 3, which I couldn't do during contest.

Again, nice problem though.

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

    Since there is no editorial yet, can you please share your approach?

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

      Firstly, notice that the condition basically says that each integer $$$i$$$ ($$$1 \leq i \leq n$$$) should lie in at most $$$k-1$$$ segments of the set. This is a necessary and sufficient condition.

      I first consider this method of "building" permutations. Basically, in a permutation, for each element you can make an edge to the next element. And make an edge from the last element to zero, to denote the end of the permutation. We will try to build this graph representation of the permutation.

      Now, think of the subgraph of such a graph if you only consider the nodes $$$[0, i]$$$. This will look like a directed graph with $$$m$$$ chains, with exactly one chain ending at zero. We will basically build the final graph, by adding nodes to the graph one by one, from $$$1$$$ to $$$n$$$. When we add node $$$i$$$, we only have to decide if it has any outgoing or incoming edges to lower numbered nodes. We can see that depending on our choice, the number of chains will increase by $$$1$$$, decrease by $$$1$$$, or remain same. Try to see how the number of ways to cause each of these changes only depends on the initial number of chains $$$m$$$. We must make sure that we never attach a outgoing edge to the node $$$0$$$, as it's supposed to denote the end. Notice that depending on our choice of how we add $$$i$$$ to the graph, and the previous number of chains $$$m$$$, we can exactly determine the number of segments of the final permutation, in which $$$i$$$ will lie. This will allow us to not consider choices in which this exceeds $$$k-1$$$.

      As the number of chains $$$m$$$ in the subgraph $$$[0, i-1]$$$, is the only important data we need, I denote $$$\text{dp}[i][m]$$$ as the number of ways to proceed to build a good permutation, given we have already built the subgraph with nodes $$$[0, i-1]$$$, which has $$$m$$$ chains. Try to form the $$$O(1)$$$ transition. The final answer is simply $$$\text{dp}[1][1]$$$.

      Code

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

No analysis for BOXES? I'll post my linear solution in the meantime.

After thinking and wolframing for a bit, the task boils down to computing $$$_2F_1(-k,k-n;1;\frac43) = F(-k, k - n)$$$ for all $$$k$$$ from $$$1$$$ to $$$n$$$. After googling and reading about this for a bit, we find out about so called "contiguous relations" for hypergeometric functions that let us find in $$$O(1)$$$ the value of $$$F$$$ at one of the "neighbors"(in the 2D-space of $$$(a,b)$$$ pairs) of $$$(a,b)$$$ given $$$F(a,b)$$$ and the value of $$$F$$$ at another of its neighbors. So we naively compute $$$F(-1,1-n)$$$ and $$$F(-2,1-n)$$$ and then kind of "walk down" this staircase. You only need formulae 15.2.14 and 15.2.19 from here.