okwedook's blog

By okwedook, 4 weeks ago, In English

The problems were named after songs of my favorite musical group, Hippie Sabotage. Give them a try!

1826A - Trust Nobody

Hint1
Hint2
Solution

С++ Implementation: 204718333

1826B - Lunatic Never Content

Hint1
Hint2
Solution

С++ Implementation: 204718497

1826C - Dreaming of Freedom

Hint1
Hint2
Hint3
Solution

С++ Implementation: 204718535

1826D - Running Miles

Hint1
Hint2
Solution

С++ Implementation: 204718553

1826E - Walk the Runway

Hint1
Hint2
Hint3
Solution

С++ Implementation: 204718603

1826F - Fading into Fog

Hint1
Hint2
Hint3
Solution

С++ Implementation: 204718641

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

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

instant editorial

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

What? Hints are in Russian and solutions are in English.

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

    Sorry, fixed!

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

      In your solution for Lunatic Never content you used n-i+1 when it should be n-i-1.

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

        This is not a mistake
        The difference comes from 1-enumeration against 0-enumeration

»
4 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

I'll add implementations as soon as system testing finishes.

Thanks for participation, I hope you liked the contest even though problem A was kinda hard.

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

    It was very hard that first time users of codeforces can't sleep tonight

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

    Hey! Can you please add implementation for Problem E?

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

      A little late, but I added all of them:)

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

        Thanks a lot man!

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

        I am unable to open the solution links it seems

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

          Yeah me neither. It says I don't have access to view the page. Take your time tho. Thanks for the hard work.

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

            Damn access rights, will ask my coordinator for help here

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

              if you are the manager of the contest while submitting, your submissions wont be visible.

              In normal gym, there is the option to disable manager mode and then submit, im not sure if theres a similiar one here. Alternatively, you can ask somebody else to submit your codes for you, or use a third party website like pastebin.

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

        Excuse me. Could Problem E get "Accepted" by Python or Pypy? I tried for a few times, but I failed.

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

          Probably not, since problem E is tight on time limit.

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

            Gotcha. Thanks. Poor Python :(

»
4 weeks ago, # |
  Vote: I like it +68 Vote: I do not like it

In Problem F, was the inaccuracy 1e-4 in projection set deliberately? Maybe the projection point is fairly accurate, but the judge adds a random number smaller than 1e-4. Otherwise It's simple to find all points by y=0, y=-0.001x (2 queries).

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

    Yes, it was set deliberately The interactor simply adds noise to the answer

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

    By the way, can we add line $$$x=0$$$ here and be alright? This way, we will have precise enough values of candidate ys (which are well spread apart), and then we can just match.

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

      Right. That's one of the solutions.

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

    Does a 2 query solution pass? I am not sure why you needed to add weird constraints and inaccuracy

    +) I think the editorial for 'getting rid of noise' part is needed

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

      May be because getting rid of noise is a part of the problem difficulty, otherwise, the problem is too easy to be placed in F.

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

I wrote a strange solutino for E and not sure if it will FST.

I notice that the bottleneck is calculating the relationship of (i, j), it's O(m) originally. The whole algorithm is O(n^2m). So I add two optimization strategies:

  • When the transition can be from F[i] to F[j], I ommit the nodes of the solution chain of F[i]. This may be hack by this array:

1 2 3 4 5

1 2 3 4 5

...

1 2 3 4 5

1 1 1 1 1

  • So I add another strategy: If [line x] causes j to be unable to connect to i. The next link judgement will start from [line x].

https://mirror.codeforces.com/contest/1826/submission/204635663

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

shit as predickted

»
4 weeks ago, # |
  Vote: I like it -58 Vote: I do not like it

Worst div.2 that I've ever participated in.

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

    nice, you cant solve proplems and and you say its the authors fault

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

      I have given quite a few contests(60+) which is more than twice of what you have given and yet it's my first time commenting something like this. There has to be a reason for this no?

      I did not say it because of my bad performance, I said it because of the imbalance in the problems.You can see that B has more accepted solutions than A and the number of accepted solutions of A and C are comparable. This is not the usual case.

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

        I have given more contests than you and I say it was a good contest and a nice problem set. Thank you authors for the nice problems.

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

          I don't trust your nickname

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

            Haha. It's just personal preference. Though I suck a lot at math I still love it.

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

          It's not about giving more contests , I said it to show that I don't do comments like these after every contest. And I have given quite a few.

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

        There are about 7000 solutions on a and about 6000 on c, maybe its really hard for a div2, but everybody can solve it, maybe not for 5 minutes as usual. As for c it is easier than usual, and you also could solve it, but you didnt and now you tell me that there is something wrong with the contest.bruh

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

Is D can be solved using ternary search ?

Isnt it f(len) = max1+max2+max3+len for all length a convex function

I tried during contest but couldnt do. Can somebody let me know whether i am correct or not

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

    Why would it be convex?

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

      Sorry my bad, intially i got intuition that it should be convex. But now i realized it is not necessary.

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

        100 1 1 100 1 1 100 1

        Function has local maximum at length = 4 and length = 7 so it is not convex

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

Problem B is from past contests.

Problem Link: https://mirror.codeforces.com/gym/102035/problem/I

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

In $$$B$$$, it should be "which basically says $$$x$$$ divides $$$a_i−a_{n−i+1}$$$"

»
4 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

You can solve problem 1826E - Walk the Runway in $$$O\left(n^2 \times m\right)$$$ in C++ without bitsets. Based on naive $$$O\left(n^2 \times m\right)$$$ approach, you need to apply next optimizations one-by-one for getting 1872 ms.

Optimization 1
Optimization 2
Optimization 3
Optimization 4

Accepted 1872 ms submission

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +19 Vote: I do not like it

    Optimization 1 is redundant, this part of solution takes less then 100 ms.

    __restrict keyword is also unnecessary, your code doesn't change arrays.

    I tried to use similar approach but didn't came up with genius optimization 2.

    I changed your check function a little bit, now solution is 1263 ms :)

    204651252

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

      Thank you, idea with unsigned difference instead of comparison is very cool too.

      I think 1263 ms is not so fair, because during system testing a lot of solutions are running simultaneously on same cpu with common L3 cache (L2 and L1 are isolated and are private for each core) and more likely that someone will push out your data from L3 cache, then it will be pushed out of L2, then will be pushed out of L1, because it is required for data to be in cache of higher level. But I can be wrong.

      I remember that runtime of my original solution was 1200 ms in the custom invocation during a contest with m = 5000, n = 500 and each row is sorted permutation, but it became 1700 ms after submit (pretests) and 1872 ms during system testing.

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

        I tried to submit both versions within a second (obviously not during contest). I even tried to return back "restrict" keyword in my version. I repeated it 3 times. Here are results. Rather unstable but highest bit trick tends to be faster.

        Screenshot

        I think cache is not a bottleneck here. The main optimization is SIMD usage. uint16_t helps to do more operations per vector instruction.

        Why highest bit trick is faster? Well, I guess sometimes bool type behaves in other manner. Like a widely known fact that construction "if (a && b)" for many compilers is actually "if (a) if (b)". I remember in some video a guy explained if you want your SIMD to work properly use bool very carefully :)

        About 1200 ms on sorted max test — maybe branch predictor memorized this simple pattern and helped to reduce time in some way (I'm not sure, just an assumption).

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

I think my solution for D is different, and slightly over-complicated comparing the editorial.

I thought of the array being empty first and then I put the elements from higher to lower beauty in their position, at each iteration, the answer is to choose the best three consecutive sights, they are consecutive because the answer has the three most beautiful sights in some [l, r], when the minimum of them is put in the array, they are consecutive because there is nothing between them. Finally adding one sight to the array creates only three new trios of new possible consecutive sights, (e. g. m is the index of the new sight [a, b, m, c, d], the new three consecutive trios are [a, b, m], [b, m, c] and [m, c, d]), so I represented the dynamic array with sets, and check the three new possible trios after I put an element in the array.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it
so the total time complexity would be O(n2m/64)
, which is fast enough.

So why my solution of E 204620376 got TLE?

Update: Now I optimized it in 204648297

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

To my mind, if there was problem E instead of problem D (but with smaller constants,like m<=100, n<=1000), this contest would be much better. Cause D is too easy for this position, and E is quite easy too (comparing to other "E" problems)

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

Why is this submission getting Idleness Limit Exceeded on Test 120?

EDIT: replacing 0.0002 with 0.0002004 gives AC :(

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

You can solve problem D even if instead of finding 3 best elements we had to find k best elements in time complexity of O(k*nlogn). For finding best two, you can do the following : For all i, first insert a[i]-i in the set. Now iterate on i from left to right, erase a[i]-i from set and find maximum value in set(mx) and set b[i] = a[i]+mx+i. b[i] now contains the answer for maximum 2 values. Now you repeat this by inserting b[i]-i and setting as c[i] = a[i]+mx+i again. Repeating this allows to pick k best elements in O(k*nlogn)

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

    Nice variant!

    I think this can be optimized into O(NK) time: define $$$s(j, l) = max (A[i_1] - i_1 + A[i_2] + A[i_3] + ... + A[i_l])$$$ for any $$$i_1 < i_2 < ... < i_l < j$$$ (that is: the maximum value of a subsequence of length $$$l$$$ using elements before $$$j$$$ and baking in the $$$+ l$$$ term). Then the answer is $$$max(s(j, K-1) + A_j - j)$$$ over all possible values of $$$j$$$ ($$$1 < j < N$$$).

    We can go through the array from left to right and calculate $$$s(j, l) = max(s(j - 1, l), s(j - 1, l - 1) + A_j$$$ in O(K-1) time, for an $$$O(NK)$$$ time and $$$O(K)$$$ space solution.

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

      i did it in linear time by computing prefix and suffix maximums of of a[i]+i and a[i]-i respectively. and then iterating from 2nd to last second sight 204718856. i wonder how can we solve this using DP, not very good at it ;-;

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

What is the fairly straightforward solution using DP for D mentioned in the editorial?

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

    DP method uses the same idea: two of the three biggest values are in left and right boundary. Otherwise we will shorten the range and get smaller cost.

    f[i][j] is the answer of choosing j numbers in first i of n numbers. 0<=j<=3.

    the cost -(R-L)=L-R can be added into calculation in running process.

    When the first number is selected, left boundary L is fixed to its index. This is f[i][0]->f[i][1], add index i(=L) to answer additionally.

    When the third number is selected, right boundary R is fixed to its index. This is f[i][2]->f[i][3], subtract index i(=R) to answer additionally.

    The method can be expanded to selecting k numbers rather than 3 numbers, with time O(nk).

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Thank you for preparing for this round, despite the A problem is hard than B,C hh:)

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

    It doesn't matter because it's easier to solve than to find the original problem.

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

Wow, editorials come so fast...

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

In problem C,

First we need to notice, that in order to keep some amount of options indefinetely, this number has to be at least 2 and divide n.

How to prove that number d divide n ?

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

    Each person casts exactly $$$1$$$ vote. If there are $$$m$$$ options and $$$n$$$ people voting, then for all options to be kept, they must all receive an equal number of votes, $$$k$$$. That means $$$km = n$$$, or equivalently, $$$n$$$ is a multiple of $$$m$$$, or equivalently, $$$m$$$ is a divisor of $$$n$$$.

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

      Thanks! i misread the problem and wasn't considering no matter how people vote, now i got it.

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

      In this i am doing same but then also i got WA why?

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

I have a different solution for D. I solved it using the divide and conquer method. I must select three elements that maximize the answer from 1 to n. At first, I divided the range into two equal segments 1 to n/2 and n/2+1 to n. Now, there are four cases. 1. All three elements are on the right side. In this case, we have to solve it for the range n/2+1 to n. 2. All three elements are on the left side. In this case, we have to solve it for the range 1 to n/2. 3. Two elements are in the left segment and another one is in the right segment. 4. Two elements are in the right segment and another one is in the left segment. I have to take the maximum of these four results. For case 3 one element is on the right side. I have iterated over the right segment for the element. If I take ith element it will make profit li and to take this element I have to travel i-n/2 miles. So, the ultimate profit is li-(i-n/2). I took the element which makes the maximum profit. For the left segment, there are two elements. I have iterated over the left segment. If the ith element is the first element of the two elements then I have to travel n/2-i miles. I will take the maximum two elements x and y from the i to n/2 range. Then it will make a profit of x+y-(n/2-i). I have chosen that make maximum profit. Case 4 is similar to Case 3. The complexity is O(nlogn). Here is my solution. https://mirror.codeforces.com/contest/1826/submission/204653388

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

19k registrations and only 5k participants nice A ;)

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem D can be solved easily without precalculating anything. In fact, it can be solved in O(1) space and O(N) time: https://www.codeforces.com/contest/1826/submission/204656798

The logic is similar to the editorial. We rewrite the problem as: maximize $$$(A_i + i) + A_j + (A_k - k)$$$ subject to $$$i < j < k$$$. Then we can run the values $$$k$$$ from 1 through N, and keep track of the maximum values of $$$A[i] + i$$$ and the maximum value of $$$(A_i + i) + A_j$$$ (see the code for details) at each position.

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

    It's the same DP but you used k-1 = 2 variables to store dp[i][1], dp[i][2] and "answer" to store dp[i][3]

»
4 weeks ago, # |
  Vote: I like it +59 Vote: I do not like it

Problem E has weak tests because some AC submissions used random or checked if 50-100 comparisons were ok, while there are 500 needed.

I've added one test to hack these submissions but its still not ok, i guess.

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

in Ques A why not l(i)>=x as at least x can be no of liers ,, as in editorial its l(i)>x

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

okwedook I still don't understand why 2 queries aren't enough in F. Is it not ok to get the x coordinates through projection on y = 0 and y coordinates through projection on x = 0? It is also written that ans should be correct till 3 decimal places and since the noise is < 10−4 for each point through the query, shouldn't we be good?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 5   Vote: I like it +8 Vote: I do not like it

    From the statement:

    In one query, you can ask some line ax+by+c=0 and get the projections of all n points to this line in some order

    The points are not nescessarily returned in the same order every time. Thus, the two following cases are indistinguishable from each other with just queries $$$x = 0$$$ and $$$y = 0$$$:

    For both of these cases you could recieve the following answers:

    $$$x = 0 \ \Rightarrow \ 0\ 1\ 0\ 2$$$

    $$$y = 0 \ \Rightarrow \ 1\ 0\ 2\ 0$$$

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

Am I the only one not getting the solution of A? :(

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

    This much is obvious that the number of liars can range anywhere between [0, n] inclusive. Say the no. of liars is L.

    From the statement: Some of them might be liars, who always tell lies. The i-th person says "There are at least L liars amongst us".

    Since liars always tell lies, they will surely say that the no. of liars are atleast L+1. So these people will always report a value >= L+1

    So, if for some value of liars = L, if you are able to find exactly L people who say liars are > L then that means that L is actually the correct no. of liars.

    You can iterate over all all possible values of L and check.

    AC submission: 204649911

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

      4

      2 2 2 2

      plz explain this test case nksrivastava18

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

        Let's break it down into 2 subcases.

        Claim 1: Let's say the 1st person is not a liar. Therefore his statement is true. So out of the leftover 3 people, the number of liars should be atleast 2. So either 2 of them are liars or all 3 are liars. If only 2 of them are liars, they should lie and report atleast 3 as their answer. Since this is not the case, all 3 of them should be liars. Because all 3 are liars, they should lie and report that there are atleast 4 liars. Since even this is not the case, therefore our claim 1 is false.

        Now we are only left with the option that 1st person is a liar. Let this be claim 2. Since he is a liar, his statement is false. Therefore the no. of liars should be strictly less than 2. But since we are still left with 3 people who are saying the no. of liars should be atleast 2, therefore these 3 should also be liars. This is a contradiction and hence claim 2 is also false.

        Hence we can conclude that all of them are contradicting each other and return -1 as the answer.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But isn't it always possible that everyone lies? (No. of liars is N)

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

    Which part don't you understand?

    Assume the number of liars is $$$x$$$. Then all people who said that the number of liars was greater than $$$x$$$ were lying! So to count how many liars there actually are, you need to count the number of $$$A[i] > x$$$ (note that $$$A[i] = y$$$ means the i-th person claims there are at least $$$y$$$ liars).

    It's easy to turn this into an $$$O(N^2)$$$ solution. The challenge is then to optimize this into an $$$O(N log N)$$$ solution.

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

      Still not getting the logic. Why do we need to count A[i] > x?

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

        People can only speak a falsehood by overestimating the number of liars, not by underestimating, since each person only makes a claim about the minimum number of liars there are.

        Let's look at a concrete example:

        • Anna says: at least 1 person lied!
        • Bernd says: at least 3 people lied!
        • Charity says: at least 0 people lied!

        Then there are four possibilities:

        • Maybe 0 people lied. But that cannot be true, because if 0 people lied, then Charity was speaking the truth, but Anna and Bernd were both lying about the number of liars, so there are 2 liars, not 0.

        • Maybe 1 person lied. In that case, Anna and Charity are speaking the truth, and Bernd is the sole liar, which is consistent.

        • Maybe 2 people lied. But that cannot be true, because in that case, Charity and Anna are speaking the truth, and Bernd is lying, so there is only 1 liar, not 2.

        • Maybe 3 people lied. But that cannot be true, because in that case, all three people are speaking the truth, so there 0 liars, not 3.

        So the only valid choice in this case is $$$x=1$$$.

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

          Yes now I understand. Thank you so much for taking the time to explain ^_^

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

      4

      2 2 2 2

      plz explain this test case

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

Petition: set at least 2.5-3 seconds time limit when the intended solution requires >1e8 operations. :)))

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

    Which problem are you referring to?

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

      Problem E surely, where the correct solution is $$$O(N^2 M)$$$ with N=5000 and M=500, which makes for $$$125 × 10^8$$$ operations, though processing 64 bits at a time is supposed to bring that down to $$$~1.95 × 10^8$$$.

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

        That's the problem with this type of tasks
        You can't cut off all the unintended solutions without cutting off some of the slower intended ones
        My fastest solution was faster than 500ms, so a 2s TL is only fair

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

          First of all, thanks for the wonderful round.
          I just wanted to say that solving the problem shouldn't be about being "risky" enough ddd.

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

For A, in the case that everyone says that nobody lied, then everyone may have lied, but that is not an accepted answer.

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

    The people cannot say that nobody lied. They would be saying "at least 0 people lied" which is obivously always true (it's impossible for less than 0 people to lie). Thus if everyone says this, everyone must speak the truth and the number of liars must be 0.

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

Can anyone give submission link for recursive dp solution of problem D?

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

I had a somewhat different solution for Problem B, which I'm not sure whether it was intended to pass or not.

Like the official solution, I consider the pairs of numbers that must be made equal (first and last element of A, second and second-to-last element of A, etc.), ignoring the numbers that are already equal (if all are equal, the answer is 0). For the first pair {a, b}, calculate all possible divisors of $$$a - b$$$. Then for each other pair {c, d}, filter down the possible divisors by checking if each divisor is also a divisor of $$$c - d$$$. (submission source code).

This solution is $$$O(sqrt(10^9) + N×k)$$$ where $$$k$$$ is the maximum number of divisors of a number below 10^9 which is around 1000, for an overall ~100,000,000 iterations.

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

bad contest

problems were not clear or understandable

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

Task E is cool, thanks!

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

May I know if it's possible to do problem A faster than brute force and how to do so?

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

    You can do it in n log(n). The idea is that if someone saying that there are at least 10 liars is saying the truth, then everyone else saying there are 1,2,...,9 liars will also be saying the truth. So you can iteratively check if exactly the first n people are saying the truth or not in O(n) after sorting.

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

E can be solved in O(nmlogn). we can build a binary index tree for every city.First, we sort all the models by their beauty in every cities(the first city has the largets weight the second has the second largets ...). then, we can do dp with this order( any reverse in this order is invalid!). When dp, for a model i,we can query every binary index tree for every city to get their previous max dp. for those maximum dp values we choose the minimum one for that one is the valid one.(unfortunately I fst cuz I for got that std::sort is weak sortings qwq)my code

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

What a WAnderful contest, I gained so much~

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

What is wrong in this this method for C

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

for problem F, the output format of my code is correct in my computer, but I get a WA because "wrong output format Unexpected end of file — double expected". what's up?

204643420

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

If I try to see the implementation it says: You are not allowed to view the requested page. What should I do?

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

Unable to open C++ implementation

"You are not allowed to view the requested page"

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I was not able to solve B. Now my rating is a palindrome too xD

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

Can D be done without dp??

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

Hey, the C++ Implementation's link in problem A is blocked.

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

What is the distinction between a lie and a contradiction?

6
3 3 3 5 5 6

The above test case gives 3 as answer even though what the 4th element is saying is never possible.

In the same sense:

9
0 1 1 2 2 4 7 8 9

The last 2 says there are atleast 2 liars, and he's right, there are 4 liars, because what the first 4 is saying can never happen. But here the answer is -1. Can somebody explain? TIA

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

    In your second example statements of the first 5 people stay consistent with the previous statements, but the 6th person, who is saying that at least 4 people are lying contradicts himself and the rest of the statements, he can't either be lying or telling the truth.

    If the first 5 people are telling the truth then it means that there should be at least 2 and at most 4 liars in the group. Then if the 6th person is telling the truth that actually means that he should be one of the 4 people lying (a contradiction). If he is lying that means that there should be less than 4 total people lying in the group, therefore out of the last 3 people in the group at least 1 should be telling the truth (in turn meaning that there is at least 7 people lying or more, a contradiction).

    Hope this helps!

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

why still I can't see the authors implementation?

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

My nlogn solution for A with a map: 204718789.

For the life of me couldn't figure out the brute force approach for A (although by looking at constraints it was obvious to me that n^2 should pass).

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

    I wrote also nlogn solution after contest (Virtual Contest) is over Just now after seeing your comment I just checked and saw n is 100 only :p.

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

Where does the number 64 come from in time complexity of Problem E. O(n^2m/64)

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

    The number of bits used by one number in a computer. In a 64 bit machine this number is 64. This number is often referred to as $$$W$$$, or wordlen.

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

    The operations on bitset has a complexity of O(N / K) , where N is the length of the bitset and K is the register size of the system (generally 32 or 64). Link

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I am facing a weird behavior in problem F. I will query the 3rd line if the minimum distance between any projection of candidate points is at least EPS. When I set EPS = 1E-6 I get TLE, while EPS = 5E-4 will get AC in 200ms. However this is weird since smaller EPS means it is more likely to achieve the condition.

EPS = 1E-6 (TLE): 204744948

EPS = 5E-4 (AC): 204744799

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

How to solve problem D with the DP method

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I started solving problem A as soon as the contest started. Gave up after an hour. Had dinner. Started again, thought of a binary search solution; didn't work, then i thought of a linear search solution(the correct one); couldn't implement it, i was just off by one line of code. Gave up. After the contest was over and i looked at the answer it was the hardest facepalm moment of my life.

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

Coding style is appreciable !!

»
4 weeks ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

My thoughts on problem F. Please correct me if you find any issues.

Theoretically, if we choose the degree of slope of our line uniformly in range $$$(0, \pi)$$$, the probability that two points fall on the same line should be 0, and choosing some random fixed slope should also work. However, there are about 200 tests. Consider if each one has $$$t=50$$$ cases, and each case has $$$n=10$$$ points, then the total number of vectors that can be formed is $$$200*50*10^4=10^8$$$. Denote our line as $$$w'x = b$$$, then the maximum of minimum angle between any vector and $$$w$$$ is $$$\frac{1}{2}\frac{ \pi}{10^8}$$$, and the smallest distance between projections of two points is $$$\sqrt{2} sin(0.5\frac{\pi}{10^8}) = 2e-8$$$. Now, this might still be distinguishable by double precision, but the problem can add a $$$1e-4$$$ noise to coordinates. If that noise is added in the direction parallel to our line (that is, orthogonal to $$$w$$$), then it is very easy to swap position of two projected points. Similarly, even if we randomize the slope each time, it is still unlikely to avoid all the vectors (I tried).

However, by the same analysis, if for each test case we choose the maximum possible minimum angle, then the smallest distance becomes $$$\sqrt{2} sin(0.5 \frac{\pi}{25^4 / 2}) = 1e-5$$$. Note that this is still smaller than $$$1e-4$$$. My first guess is that, since the $$$O(n^4)$$$ vectors are formed by choosing pairwise among $$$n^2$$$ points, it actually does not have enough freedom to uniformly spread among $$$(0, 2\pi)$$$, so the true gap is much larger than $$$2e-5$$$. This could be true, but the real reason is that, because all coordinates are in the range $$$(-100, 100)$$$, it is actually impossible for any vector angle to fall in range of, e.g. $$$(0, arctan(\frac{1}{200}))$$$, which is $$$2e-3$$$! This makes the problem completely trivial, as we can actually choose some fixed slope, e.g. $$$a=400, b=1$$$ should be the safest as it maximize the minimum gap. However, if this bound of $$$100$$$ is changed to $$$10000$$$, then we should still use the method by the editorial.

The $$$1e-3$$$ constraint does not matter as we can obtain coordinates from first two queries at the precision of $$$1e-4$$$.

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

The editorial says it has a fairly straightforward DP solution, but I feel, most of the people who solved it, skipped the mathematical proof of why it is okay to take the max $$$(b_l + l)$$$, thus converting the problem from find the max 3 elements and subtract $$$(r - l)$$$; to given an array, maximize $$$(b_l + l) + b_m + (b_r - r)$$$.

Proof: Let's say for a given $$$b_m$$$ there exists a $$$b_{l_1}$$$ and $$$b_{l_2}$$$ such that $$$b_{l_1} + l_1 < b_{l_2} + {l_2}$$$; given $$$l_2 > l_1$$$ and $$$b_{l_1} > b_{l_2}$$$. But in our segment, we have to take the maximum element so if $$$b_{l_1}$$$ stays we'll have to accept the value calculated using it. But we safely use $$$b_{l_2}$$$ which returns a higher value.

But this doesn't always work.

What if the question asked you to maximize $$$(b_l - l) + b_m + (b_r + r)$$$? I have seen some solutions for D, where people have tried looking for previous state of DP using LastGreater element, and I thought I am not the only one who doesn't find it straightforward.

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

"A more straightforward one, is checking all the numbers from 2 up to √n"

Hi can you please help me understand why we didn't go till n.

  • Never mind understood.
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please provide the dp approach for problem D. I understood the direct approach, I would really appreciate the help and thanks a lot for the effort.

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

Problem D , DP solution please explain!