Akulyat's blog

By Akulyat, 2 months ago, In English

1735A - Working Week

Hint1
Answer to Hint1
Solution

1735B - Tea with Tangerines

Hint1
Hint2
Solution

1735C - Phase Shift

Hint1
Answer to Hint1
Hint2
Hint3
Answer to Hint3
Solution

1735D - Meta-set

Hint1
Answer to Hint1
Solution

1735E - House Planning

Hint1
Answer to Hint1
Hint2
Hint3
Solution

1735F - Pebbles and Beads

Hint1
Hint2
Hint3
Solution
 
 
 
 
  • Vote: I like it
  • +74
  • Vote: I do not like it

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

lol I hopcroft-karp'ed the E

Upd: mine got tle lol. guess it's not my lucky day

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

    YES! I had same solution but i had no time to implement it. Sad :(

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

    I tried and got WA :( dunno how I messed it up.

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

    lmao same, i did dinics. Only took 187 ms too, good flow templates r just too fast.

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

      Could you describe your flows approach?

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

        WLOG, $$$p_1=0$$$ (u can shift at the end to make all the vals in $$$[0, 2e9]$$$). Each element for $$$d_2$$$ that you can match $$$d_1[0]$$$ to gives u two options for $$$p_2$$$, so we want to test a $$$p_1, p_2$$$ pair relatively fast.

        Each $$$d_2$$$ val has two possibilities for a distance from $$$p_1$$$. If we frequency bucket the $$$d_2$$$ and $$$d_1$$$ values, we can setup a flow network which is like bipartite matching except that the edges from S / to T have capacity of the frequency of that element.

        Each flow run has $$$2n=O(n)$$$ edges and $$$O(n)$$$ nodes, so (by a little handwaving that this is basically bipartite matching) it takes $$$O(m*\sqrt{n}) = O(n^{1.5})$$$. We do this flow $$$O(n)$$$ times, so overall $$$O(n^{2.5})$$$.

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

          How to format math like you did in your comment

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

      This comment got me curious. Does Dinic outperform Hopcroft-Karp?

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

        Bro, if u know what is Dinic and Hopcroft-Karp, but u are specialist, u are doing something wrong

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

          Can you explain what you mean?

          BTW Idk either of those two terms

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it -27 Vote: I do not like it

          well I am specialist and I know that dinic and hopcroft-karp are both algorithms for the network flow problems. and also that dinic is usually fast but the optimal algorithm always depends on the problem in question.

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

          So because I am a specialist I shouldn't be learning more about algorithms. I'm sorry but what you are saying is just absurd.

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

            studying more complex algorithms, while not fully working out the easy ones, is not a very good practice

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

              I know flows and graph matchings from reading a book about algorithms, I didn't study them that much. I asked the question because I know that Hopcroft-Karp should be faster than Dinic in unweighted bipartite matchings but it seems that HK got TLE and Dinic passed here. Anyway, thank you for the advice and have a nice day.

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

      As a tester, who solved it using the same technique. I can prove that Dinic is asimptotically correct here. There are $$$m = O(n^2)$$$ edges in total and $$$n$$$ vertices for bipartite matching. Dinic for bipartite matching works in $$$O(m\sqrt{n})$$$ which in this case gives us a solution in $$$O(n^{2.5})$$$ which is fast enough.

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

        Don't u need to run the flow 2n times (for each possibility for p2 given by matching the first d1 to a d2)?

        The trick I did was to deduplicate so $$$m$$$ is bounded by $$$O(n)$$$ cuz each d2 guy only has 2 options in d1. This isn't bipartite matching network anymore (non unit capacities from/to S/T) so the bound doesn't hold.

        I suspect this is asymptotically still $$$O(n^{1.5})$$$ or something close per flow run, but I have no way to show that.

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

          It's important, that there are a total of $$$m$$$ edges, so for each case it will work in $$$O(cntedges_i\sqrt{n})$$$, which in total is

          Unable to parse markup [type=CF_MATHJAX]

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

        I did exactly this but I got TLE on test 48. I learned flows quite literally yesterday so I'm not sure if it's something I'm doing wrong or if my template is just inefficient, could you please take a look once?

        My submission

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

      Hi, I also did Dinic just now and got accepted. But I wonder if the complexility of the algorithm is exacly $$$O(n^2\sqrt{n})$$$. Depending on my approach to conducting the flow, the graph isn't exactly the problem of bipartite matching where Dinic reaches the complexility $$$O(m\sqrt{n})$$$, due to the edges linking verticles to the Sink Verticle may have capacility above $$$1$$$. Maybe the case where dinic behaves worse exists. I will appreciate it if you consider the complexility.(Or maybe u took another way distinct from mine.)

      Thank u!QwQ

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

    I used max bipartite matching from CP4 ch4 and passed :)

»
2 months ago, # |
  Vote: I like it +34 Vote: I do not like it

well-balanced contest. thank you so much. hated it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

logic in A was quite good!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    well tbh it was just maths. let's define $$$k$$$ as $$$\lfloor \frac{n-3}{3} \rfloor$$$ and assume $$$n$$$ is a multiple of 3 then probably the 3 segments are $$$[1,k,2k-1]$$$ and the difference is $$$\lfloor \frac{n-3}{3} \rfloor - 1$$$. Didn't prove more (the minimum wouldn't be getting bigger anyways), and got AC.

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

    idk, i just div it for 3 and minus 2

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What will be the expected rating of this question? like, 1000, or greater than or less than 1000

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

I didn't even understand A... Just needed to find some $$$x$$$ from $$$0$$$ to $$$7$$$ such that $$$\lfloor \frac{1033-x}{3} \rfloor=342$$$

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In editorial of D, what is a "central card"?

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

    It's the card that is shared by both sets in a metaset.

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

    It's a card that appears in two different sets within a meta-set.

    Two different sets can have at most one overlapping card (two overlaps would imply that the third must be the same as well, but then they're no longer different sets), so a meta-set (which has only five cards) can only fit in two sets if they have exactly one overlapping card. This card is considered as the central card of the meta-set.

    (I actually mentally used the term "central card" as well when thinking about this problem during the contest, even though the statement never suggested such a term; I guess the visual explanation kinda screams "central card")

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

    Thanks. I get it now. 2 sets means 2x3 = 6 cards, but we are only considering 5 cards. So 1 card is shared, or in other words, central.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Balanced Difficulties, great Problems, fast Editorial, all in one contest. Rated it as the best contest I have ever participated.

»
2 months ago, # |
  Vote: I like it +18 Vote: I do not like it

0≤hi,p1,p2≤2⋅109 for what?(((

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

    I agree that it could be better to set $$$-2\cdot10^9 \leq h_i, p_1, p_2 \leq 2\cdot10^9$$$, but I don't find it a big challenge. You just need to shift all the values by an easy found constant in the end.

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

      Yes, it is easy. But at last minute of contest I submitted my solution and got wa5 so now I have negative delta instead of top 40 div2. Unlucky...

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

My approach to D involved the key observation that three cards form a set if and only if the sum of values for each feature is 0 mod 3 (i.e., either i + i + i or 0 + 1 + 2). We can find the sum of every possible pair of cards, and count them in a structure (like a map). Then we iterate through each card in our input (to consider it as a potential central card) and subtract this card's value from 0 modulo 3 to get the required pair sum it can form a set with. We can then add sC2 as described in the editorial, where $$$s$$$ is the number of times this pair sum appears.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If we form a circle of size less then 26. Maintain any structure to check it.

Is there anyone who thinks he has implemented a very nice structure to check whether there is a cycle of small length or not?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    a very nice structure to check whether there is a cycle

    well we already have the DSU???????

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

      Writing DSU takes too much time i didn't had pre written code for it.

      And copy pasting code from online sites is not my style.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it -27 Vote: I do not like it

        Oh come on, I took less than two minutes typing it. You didn't even have to apply two compressions here, one compression (path compression is what I used) was more than enough.

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

          actually i was not able to get the solution at that time. :(

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

        having some snippets is really useful. It makes your life easy a lot of times.

        I used a dsu, but it isn't necessary. You can store for each letter the previous and the next. When you make 25 connections in this structure you have a unique set and can connect the ends

        edit: no w8 that's not right. You still have to assign some number to the whole structure each time so you can understand if you aren't connecting a loop too soon. But you can do it the stupid way assigning an id to each member of the sequence you change each time. It's like O(n+alphabet²) complexity if i'm not wrong

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

          You don't need a number for the whole structure; just storing the previous and next is enough, due to the nature of this problem. When we want to consider whether we can assign $$$c_2$$$ to be after $$$c_1$$$, this requires that $$$c_1$$$ doesn't already have a next character assigned, and $$$c_2$$$ doesn't already have a previous character assigned. So you can simply check the previous character from $$$c_1$$$, and then the previous character of that, and so on, counting how many steps this takes. If we took 25 steps, then the chain has all 26 letters, and we only need to complete the cycle. Otherwise, we can only link $$$c_1$$$ to $$$c_2$$$ if $$$c_2$$$ isn't at the end of this predecessor chain from $$$c_1$$$.

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

      A simple while loop will work. 174406487

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

    I used DSU, which is probably overkill when the size is max 26.

    It should suffice to simply store which character precedes another in our circular wheel, using a simple array, e.g., pred[0] = 3 means D precedes A. To check if it's okay to set $$$c_1$$$ as the predecessor of $$$c_2$$$, we can check the predecessor of $$$c_1$$$ and then its predecessor, and then its predecessor, and so on. If we find $$$c_2$$$ at some point, then it forms a cycle, which is only okay if we saw all 26 letters in this chain. You could, of course, store successors instead of predecessors with similar logic.

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

      I also used dsu, and now that I look back it was a dumb idea to do it for this case.

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

In E distance arrays can be sorted just once and then each candidate (distance between $$$p1$$$ and $$$p2$$$) can be checked in $$$\mathcal{O}(n)$$$ with two pointers resulting in $$$\mathcal{O}(n^2)$$$ complexity

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I think Problem A was very confusing.

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

    Some experience and you will solve it very fast

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why was l1 = 1?

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

    you can think of taking equal elements l1=l2=l3=(n-3)/3 and then to increase l2 by one and decrease l1 by 1 as this would make l1 as lower extreme and l2 as upper extreme and l3 as middle element and we can continue shifting 1 ,until l1 is equal to one. Sadly I gave up on A even after getting the main idea.

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

    1,1,1 is the min value for l1,l2 and l3. Now if we want our answer to be max we are needed to maintain the difference l2-l1 and l3-l2. So just add 2 to l3 and 1 to l2. Our n becomes n-3 after we have taken 3 off days. Give 1,1,1 to each l1, l2, l3. n becomes n-6. Now divide the rest of n-6 days in 1:2 between l2 and l3. So we can say (n-6)/3 to l2 and rest to l3.

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

Can someone tell me what's wrong is my approach for A or I read it incorrect? For a 0 based indexing,

I marked index 1 as Off Day, so I have index n-1,1 as Off days and now I need to find one more index which is Off such that my answer is maximum. I did that by finding such possible index b/w 1 and n-1. I can't take index 2 and index n-2 as Off days as they are adjacent to index 1 and index n-1. So I have (n-2-2)-1 possible indexes for the 3rd Off day. I choose this position by finding the middle of middle of that subarray. So the 3rd Off Day should be res/4 + 3 by my logic where res = (n-2-2)-1.

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

    I think you're making it complicated by thinking on indexes. If you think about the way the intervals become it should get more clear. You have this setup: |w-ww...ww-| with a gap of length 1 and a gap of length n-3. Now if the answer is x the ranges are 1, x+1 and 2x+1 long (add the remainder to the last). The ranges x+1 and 2x+1 are in the part that's long n-3, so you can find x by the simple equation n-3 = 3x+2 + 1(this 1 is the day off) => (n-6)/3 = x

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

got FST on pE, at first glance I think it is because dinic but turn out to be map<int, vector<pair<int, int>> being tooooooooo slow :/

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

fix the latex typo in B solution it looks like:

[2 \cdot a_1, 3 \cdot a_1 — 2]

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for HINTS

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

damn these aholes destroy the fun** https://www.youtube.com/watch?v=IZSyj2pTe_I T_T

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D if it is allowed that 2 cards have the same feature set then problem becomes really hard I guess. If anybody has any solution ideas to this

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, I used binary search for A, => a + b + c = n — 3, suppose a, b, c are sorted, then we have to find the min(b — a, c — b), greedily set a = 1. submission

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

    can you bit explain that why you set a = 1(greedily)...?

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

did anybody else find B confusing ?

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

    I found the problem itself easy, but I think the wording of the problem could have been a bit better (the twice part)... Also, one thing in B that threw me off the hook a bit was the test case given where the minimum element changed, but later I just assumed that min will remain same and coded accordingly as it didnt affect anything.

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

    Me

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it -7 Vote: I do not like it

    B_code

    include <bits/stdc++.h>

    using namespace std;

    int main() { int t; cin >> t;

    while (t--)
    {
        int n;
        cin >> n;
    
        long long int arr[n];
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
        }
    
        long long int total = 0;
        long long int p = (2 * arr[0] - 1);
    
        for (int i = 1; i < n; i++)
        {
            long long int k = arr[i];
            if (k % p == 0) //as in the 1st test case
            {
                total += (k / p);
                total--;
            }
            else//3rd test case
            {
                total += (k / p);
            }
        }
    
        cout << total << endl;
    }

    }

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please fix Problem C's "code" link, u posted D's solution.

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

    Please fix Problem B's "code" link, u posted C's solution.

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

SORRY to Bother u by mentioning :"" Akulyat... But i think some links in problems' codes are swapped.

BTW.. A,B,C Problems are great ^_^

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

    Thanks! Fixed
    And don't worry about mentioning, it helps others get the correct information faster.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I assume it was unintended, but a lot of $$$O(K N^3)$$$ solutions passed under the time limit in D.

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

    $$$\mathcal{O}(kn^2log(n))$$$ with vectors was intended to pass freely. Also $$$\mathcal{O}(kn^2log(n) + n^3)$$$ with a low constant is ok.
    Could you share some links to solutions with $$$\mathcal{O}(kn^3)$$$?

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

      From the last page of submissions, sorted by execution time: 174409139,174420917,174438219,174428203,174409139.

      174402025 too, but the amount of pragmas in his template deserves a special mention :D

      UPD: I managed to hack one submission, probably because they didn't even have break statements anywhere. The rest of them pass in >3000ms. Perhaps a TL of 2 seconds would have been better!

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

In B why would you not just half the values at each step rather than removing 2 × a1 — 1 at each step?
Surely if you repeatedly half the value it will get smaller soon which means less number of steps.

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

    Halving each time is not correct. For example, take 2550 -> (halving) -> 2 pieces of size 1275 for those 2 pieces, we again need to use 1-1 operations to make all pieces less than 1200 (600*2), so in total, we used 3 operations while we only need to use two operations if use operations like this 2550 -> 1199 and 1351, 1351 -> 1199 and 152

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

      You are right, but how did you come up with the idea that halving might not be optimal.

      Edit it was in the sample test case. I missed it.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The link to the code for C problem , directs to the solution code for D problem. An update would be appreciated :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

FIX

You accidentally put the link of D submission in the Code section for problem C.

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

The solutions are not at the correct question number.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Provided solution for problem D looks wrong: https://codeforces.com/contest/1735/submission/174443540

Sample testcase: 3 3 0 0 0 0 0 0 0 0 0

Actual answer should be 0. But it gives 9. This is happening because it doesn't take into account that central card should not be part of calculated set of pairs from which meta-set is created.

Akulyat: can you please look into this?

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

    It is given that all the n cards are distinct in the input so the test case is not valid.

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

      I see. This further simplifies the problem btw. Thanks for resolving my confusion!!

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

could someone explain editorial of A problem ... I am fine till "If we increase both values under the minimum scope by one, solutions don't change: maximize min(l2,(n−3)−2⋅l2)" but after that things are above my mind .

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

has someone solved problem A with binary search ?

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

    Yes. Submission

    I just couldnt form any mathematical formulation, and finally binary search was only thing I knew will work for sure.

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

    Submission I figured that L1=1, that means that there are n-4 days to distribute between L2 and L3. So i am searching for L2=mid and L3=n-4-mid, I am looking to maximize L2-L1 while still keeping (L3-L1 bigger than L2-L1) and (L3-L2 bigger than L2-L1).

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

can anyone explain ques C. Its difficult for me to understand whats written in editorial.

»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I got wa on pretest 14 in problem F during the competition, but when I replaced double with long double I got accepted... My error was about 10-5...

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

    Yeah it's a little unfair for languages that don't have 80-bit floating point (and those who may avoid long double out of principle due to architecture specificity). I basically had to hand-roll fixed-point arithmetic just to get it to pass in Rust: 174869219

    Interestingly it is important in this implementation that the multiply be performed before division, otherwise it loses enough precision to fail.

    UPD: I found a way to get 64-bit floats to pass: 174932779, compare with failing submission 174826031. Basically, truncating the convex hull from the "pebbles" axis first apparently gives more accurate results, since that's the result you have to output.

    It may also be more optimal for accuracy if, when interpolating, you reuse the slope values from the input, rather than recalculating the slope from the rounded-off endpoints.

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I don't know why but I felt A to be bit harder than usual.

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

Does anyone have ideas on how to solve D if the cards are NOT distinct?

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

    There is two option :

    1-ABCDE = combine ABC and CDE and ignore clones of them. Use clones just for how many different A can come etc.

    2-AAA??, AAAA??, AAAAA = iterate A over all different cards and let $$$x$$$ be frequency of a card increase ans by $$$C(x,3)*C(n-x,2)+C(x,4)*C(n-x,1)+C(x,5)$$$.

    There's an intersection AAABC and you can calculate it with iteration over suitable ABC's (iterate A and B, find C at $$$O(log(n))$$$) and some combinations using A, B and C's frequencies.

    But this solution can require so much casework.

    (Sorry if this solution is wrong or has missing part, and for my poor English.)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I only dumb who uses ternary search in B

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I cannot even get A.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very good round, I like all the problems!

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

https://codeforces.com/contest/1735/submission/174486190

can anybody tell why my solution from problem D gives me wrong answer ?. I am taking ith card as central card and finding no of sets formed with ith card as central card.

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

    Consider this case:

    case

    It is the same as the first example, only that the card "0 0 0 0" is now the last card. Your code returns 0, but the correct answer is 1.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the key point of problem F?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This round is so great that I cannot understand the meaning of the problem D.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain why in problem B editorial we are doing (i-1)/(2*a[0]-1)

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone explain the flows solution to E?
I get the general idea, there are $$$O(n)$$$ possible values for the distance between $$$p_1$$$ and $$$p_2$$$ and you run a max flow for each of these options, what I don't quite understand is how, for some house $$$h_i$$$ and some candidate distance $$$d$$$, it could be that $$$|p_1 - h_i| + |p_2 - h_i| = d$$$, or $$$||p_1 - h_i| - |p_2 - h_i|| = d$$$, how do I formulate this into a max flow / max bipartite matching problem?

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

    Actually $$$|p - h_i|$$$ is just the distance between point $$$p$$$ and the house, so the above equation can be rephrased as $$$d_{1, j} + d_{2, k} = d$$$ or $$$|d_{1, j} - d_{2, k}| = d$$$ for some index $$$j, k$$$.

    So just let $$$d_{1, 1...n}$$$ be the vertices of left part($$$L_{1...n}$$$) and $$$d_{2, 1...n}$$$ be the vertices of right part($$$R_{1...n}$$$), and for every pair of $$$(j, k)$$$ satisfy $$$d_{1, j} + d_{2, k} = d$$$ or $$$|d_{1, j} - d_{2, k}| = d$$$ connect $$$L_j$$$ and $$$R_k$$$.

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

      Ahh, so you don't need to distinguish between the plus and minus parts. Thank you I'll try that

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody tell why my solution (https://codeforces.com/contest/1735/submission/174557086) from problem E has tle, but https://codeforces.com/contest/1735/submission/174558165 — normal what is the difference?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

a harder version of D with k<=100 or with more than 3 values for a characteristic would be great imo

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really liked problem d

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

174937931 I understood the editorial of C but I am unable to find whats wrong in my solution. I am getting WA in test case 3. If possible can someone tell me the test case where my solution is wrong.

Thank you in advance.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C and D are really good problems, I especially love how D balances implementation and thinking so well.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My E was TLE on #45.

Anyone can tell me why it got TLE?

Submission: 175739035

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

[deleted]