Блог пользователя antontrygubO_o

Автор antontrygubO_o, 2 года назад, По-английски

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!

  • Проголосовать: нравится
  • +136
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
»
2 года назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    how to solve e?

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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 года назад, # |
Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Prime gap is how I came up with it.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

can anyone give some hint for Max Minus Min

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve SPILT AND SUM.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
        Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится

        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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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.