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

Автор Supermagzzz, 3 года назад, По-русски

1520A - Не отвлекайся!

Автор задачи: MikeMirzayanov

Разбор
Решение

1520B - Заурядные числа

Автор задачи: MikeMirzayanov

Разбор
Решение

1520C - Не соседняя матрица

Автор задачи: MikeMirzayanov

Разбор
Решение

1520D - Одинаковые разницы

Автор задачи: MikeMirzayanov

Разбор
Решение

1520E - Упорядочивание овец

Авторы задачи: Supermagzzz, Stepavly

Разбор
Решение

1520F1 - Угадай K-й ноль (простая версия)

Автор задачи: Supermagzzz, Stepavly

Разбор
Решение

1520F2 - Угадай K-й ноль (сложная версия)

Авторы задачи: MikeMirzayanov

Разбор
Решение

1520G - Идти или не идти?

Авторы задачи: Supermagzzz, Stepavly, Aris

Разбор
Решение
Разбор задач Codeforces Round 719 (Div. 3)
  • Проголосовать: нравится
  • +125
  • Проголосовать: не нравится

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

There is some issue with the editorials. Supermagzzz pls check.

»
3 года назад, # |
  Проголосовать: нравится -44 Проголосовать: не нравится

Editorial is not perfect. please look into it and upload all c++ solutions with proper explanations.

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

The tutorials aren't visible.

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

you can read this article to see editorials.

Write a new blog on CF (you don't have to post it), add a line [tutorial: <problem id>] (e.g. [tutorial: 1336A]), and preview it.

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

You can read this article to read editorials now.

Write a new blog on CF (you don't have to post it), add a line [tutorial: <problem id>] (e.g. [tutorial: 1336A]), and preview it.

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

My solution to problem G:
The main observation is that we don't ever need to use more than 2 teleportations (because going from point $$$a -> b$$$ and then from $$$b -> c$$$ is strictly worse than going directly from $$$a -> c$$$). Therefore, we can calculate for each portal the cost required to use it as the first one, which is $$$dist(start, portal) * w + a[i][j]$$$ and in similar way the cost to go from a portal to the end as $$$dist(portal, end) * w + a[i][j]$$$ (by using bfs). The solution is either $$$dist[start][end] * w$$$ or the smallest cost to access a portal from the start plus the smallest cost to go from a portal to the end.
Code : https://codeforces.com/contest/1520/submission/115344755.

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

    Sorry cuz I'm not really familier with C++, I read your code but haven't got it. I have a question is How you ensure the nearest portal from start and the nearest portal from end is not the same one?

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

      You don't need to check for that case because going from $$$(1, 1)$$$ to $$$(n, m)$$$ without using any portal will be strictly cheaper than using the same portal twice.

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

Can we solve E with ternary search?

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

    Yeah, we can.

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

    don't know about ternary but did with binary search after long thinking (ofc i m grey) but i should work more to think like how the solution in editorial is posted here is my submission 115389196

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

    Yes, it also can be solved using binary search, look at my submission if you are interested: submission

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

      it's kind of ternary search.

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

        parveen1981 I don't know if I should call it ternary search.Ternary search splits the graph into three segments. In my submission the second mid $$$mid2 = mid1 + 1$$$ is just to determine where the "binary" search should go. The graph is similar to $$$y = abs(x)$$$ and I am searching on the minimum point. if $$$moves2 > moves1$$$ then I know I am on the right of the minimum point then I should go to the left and if $$$moves2 < moves1$$$ then I know I am on the left of the minimum point then I should go to the right.

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

          You are checking for two points in each iteration. In ternary search also, we check for two points. That's why I said. But your approach is slightly efficient. Thanks. From now on, I will apply same binary search as you did.

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

      Hey, could you please explain your solution?

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

        Observation 1: First if we want to make the sheeps in one row then the length of that row has to be the number of sheeps in the given string.

        Now let's call the number of sheeps in the string to be k.

        Observation 2: If we want to move the sheeps into a subsegment of length $$$k$$$ , then the first sheep that appears in the string has to be in the first position of the subsegment and the second sheep that appears in the position has to be in the second position of the subsegment and so on until we put all the sheeps in the string in the row.

        Now to calculate the number of moves that we need to put the sheeps in a row for a subsegment consider a subsegment of length $$$k$$$ , that starts at position $$$x$$$ and let's call the position of the first sheeps in the string to be $$$s_1 , s_2 , s_3 ... s_k$$$ then the number of moves is $$$abs(s_1 - x) + abs(s_2 - (x + 1)) + abs(s_3 - (x + 2)) ... abs(s_k - (x + k - 1))$$$.

        Finally, we have to calculate the minimum of that function you can use ternary search or binary search. Here is My Submission

        It worth mentioning that there is a problem on Atcoder called Linear Approximation which is strongly related to this problem. When I put the equation of the number of moves I remembered this question then I copied my old code for it and edited a few lines and it got accepted.

        If anything is not clear feel free to tell me I will explain more.

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

    Yes,we can.I did this with ternary search.You can see my sol if interested.Your text to link here...

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

$$$F2$$$ and $$$G$$$ has the same codes.

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

Problem E has issues in solution code.

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

problem D was directly available here

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

My DP solution for E: we can find all pref[i] values where pref[i] shows how many moves we need to move all sheep to the left from i to i. If a sheep doesn't stay at i position, then pref[i] = pref[i — 1] + was ( was is an amount of sheep to the left from i), else pref[i] = pref[i — 1]. Same operations we can do for suff (we go from n to 1). Then we can simply check for every i: ans = min(ans, pref[i] + suff[i + 1]).

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

    A similar approach: we can move each '.' either left of all left sheeps or right of all right sheeps. We just need to maintain sheeps till now and total sheeps.

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

Why does my solution to 1520E - Arranging The Sheep gives WA? I did it like this:

Spoiler

Thanks if someone had the goodwill to read :)

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

    U dont have to push them all to the left or all to the right to get the answer

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

    daviyan You made just one mistake..You initialized the value of ans as n,but in reality ans can be greater than that.So just initialize it with some higher value(say n*n) and it will work..

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

      Indeed! It only worked with ans initialized as LLONG_MAX. Kinda sad that the error was only this little detail. Thanks a lot!

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

In C, I just printed odd numbers first and then the even numbers row-wise, I thought this would be the intended solution.

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

    For the last few contests, the topic bicoloring has been used in many problems on cf, so this solution comes naturally to people who are regularly solving cf problems.

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

Submission 115253830

Could someone give a proof (or hint) about the correctness of this simple problem E solution? I solved it during contest based on intuition, but struggle to give a formal reasoning. The solution differs from the one given by the editoral. Any help is appreciated.

Idea:

  1. discard all leading and trailing empty spaces

  2. initialise $$$ans=0$$$

  3. for each remaining empty space at position $$$i$$$, increment $$$ans$$$ by $$$min(sheeps_l, sheeps_r)$$$ where $$$sheeps_l$$$ is the number of sheeps appears before position $$$i$$$, $$$sheeps_r$$$ is the number of sheeps appears after position $$$i$$$

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

    this is the same as claiming that the middle sheep will not move

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

      Could you elaborate on how the two approaches relate to each other?

      UPD: I got it now.

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

        Can you tell how they relate to each other?

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

          As we iterate through the array from left to right. We have $$$min(s_l,s_r) = s_l$$$ before the middle sheep. Hence, it is best to move the spaces that appear before the middle sheep to the left. This is equivalent to moving the sheeps that appear before the middle sheep to the right, until they meet with the middle sheep. The middle sheep does not move.

          Similarly, we have $$$min(s_l,s_r) = s_r$$$ after the middle sheep, so we can apply the same insight.

          Example:

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

    I solved it using the same approach. I don't have any proof too but it makes sense when you look from the empty-spaces' point of view. You want to move the empty spaces out of the sheep so you either move them right or left.

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

      Ah yes, for cases with consecutive sheeps on both left and right like $$$***\underline{.}**$$$, it is clear to move the space 2 steps to the right.

      Originally, my suscipion arises for cases such as $$$***\underline{.}*..*$$$. Instead of considering the optimal position for sheeps (as in editoral), we can consider the optimal position of empty spaces. For this case, the optimal position for the space is 2 to the right.

      Thanks, I think I grasped the concept.

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

interactive problem in cf == Binary Search

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

    No.

    Interactive problem in CF >= Binary Search Because F2 = Binary Search + Fenwick Tree (or Segment Tree)

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

      F1: direct binary search.

      F2: binary search but with extra steps (no need fenwick tree)

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

Finally i'll get 1600+ rating :)

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

Weird solution for "1520A — Do Not Be Distracted!" in Editorial.

Isn't this solution much faster and simpler?

const set = new Set();
let flag = true;
for (let i=0; i<tasks.length; i++) {
	if (set.has(tasks[i]) && tasks[i-1] !== tasks[i]) {
		flag = false;
		break;
	}
 
	set.add(tasks[i]);
}

return flag ? 'YES' : 'NO';
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This idea is simple to write, and maybe I would suggest writing this variant in the contest.

    But set takes O(NlogN) time complexity, and we can remove the logN component by using a map(or vector<int> counter(26, 0)) to store the previous occurrence. This way the time complexity is reduced to O(26*N) which is more optimized :)

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

Let's understand what the maximum number of vertices can be in the tree. We will consider each level separately. If the level number x is less than logt≤14, then we can spend no more than x of vertices (since there are simply no more vertices). If the level number is from 15 to 18, then we can spend no more than t vertices, so each request uses only one vertex per level. By limiting the number of vertices in this way, we get that there are no more than 214−1+4⋅104=56383, which fits into the constraints.

Can anyone explain these lines from the last paragraph of Tutorial of F2 more clearly?

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

    It means that, after building the binary tree, suppose

    1). You visit all the vertices if their level is less than 14, (such kind of total vertices are (2^14-1) )

    2). Also, for every query we will descend the binary tree and we will only travel one vertex at each level at most so, for levels 15 to 18, there are 4 such vertices, hence the total vertices visited would be, 4*(# of queries) = 4*10000. total visited nodes: (2^14-1)+40000.

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

      There is also another way to solve F2, which I found nicer and easy to prove. We can divide the complete array length n into blocks of size m (for ex. m = 32 ). If for every testcase we can find in which block the answer would lie then we can just binary search on that block and it will cost at max 5 queries (if m = 32).

      Now, to find the required block. We can find the number of zeroes in each block during the 1st test case. After that, we can just traverse on blocks and see in which block kth zero will lie. And, finally decreases the count of zero from that block before moving to the next testcase.

      To get no. of zeroes in each block, we will require. n/(block size) no. of queries. This is well within the constraints.

      Here is the link of my submission:https://codeforces.com/contest/1520/submission/115301904

      The above code can be optimized using some sort of data structure to find the required block, but given the TL of 4 sec, it will pass.

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

      Thanks! I get it now.

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

      What about 14-th level?

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

        Sorry, I meant 1st case for levels less that equal to 14 instead of just less than 14.

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

          then won't there be 2^15-1 vertices?

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

            Levels starting from 1, (2^0+2^1+....2^13)these are the 14 levels.

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

              1). You visit all the vertices if their level is less than 14,

              Actually, why will we visit all the vertex level till 14? logt<=14 -- is said in the tutorial. But still now, I am confused why should I visit all the vertex till this level? Can you plz explain details in this point?

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

                We are just showing the worst possible case, ofcourse it is not necessary to visit all the vertices if the 1st condition holds but in that queries total queries would be less than derived for the worst case.

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

In editorial of F2 it should be $$$2^{14}$$$ instead of $$$2^14$$$.

To correct it the editorialist should put 14 between {}, thats how the syntax works

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

G can be solved with dp?

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

weak test cases in d

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

Can I use Dijkstra to solve G?

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

Can I use Dijkstra to solve G?

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

There is a LaTeX problem in the tutorial for F2, $$$2^{14}$$$ is mistyped as $$$2^1 4$$$ and confused me a bit at first.

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

Is the solution only given in C++ ? If no, when will Java solutions be uploaded ?

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

    The solution will most likely not given in all languages. However it doesn't matter. The best approach(to learn, And get high rating in long run) is-

    Step1: try problems yourself(maybe you have done this while the contest is running)

    Step 2: view tutorial(just explanation, and only upto some lines after which you can solve it)

    Step 3: if you are unable to understand ask someone, or ask through a blog.

    Step 4: implement solution yourself.(important)

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

Nice

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

Can anyone tell why this code is giving TLE on test 125?

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

    It has complexity $$$O(portals^2)$$$, which is too slow.

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

      Would this work?

      first sort all the portals by minimum distance of getting their from $$$(1,1) + a[i][j]$$$(value of portal) put them in list-1 say.

      then in list-2 sort all the portals by minimum distance of getting their from $$$(n,m) + a[i][j]$$$(value of portal)

      then we can pick the first item from both the list (if they are not same portal otherwise we will take 1st item from 1st list and 2nd item from 2nd list or 1st item from second list and 2nd item from 1st list and select whichever gives the minimum answer)

      Can you help?

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

        You don't actually need to store the distances in a separate array and then sort it later. You can keep track of the current minimum distance and update it accordingly.

        You also don't have to check whether you picked the same portal twice as the cost from $$$(1, 1)$$$ to $$$(n, m)$$$ without using any portal will be strictly cheaper.

        115297135

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

In problem E:

Note that in the optimal solution the sheep with the number $$$m = \lceil\frac{n}{2}\rceil$$$ will not make moves.

Shouldn't $$$m = \lceil\frac{k}{2}\rceil$$$?

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

    Or $$$m = \lfloor\frac{k}{2}\rfloor$$$ according to the solution code?

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

      The explanation counts the sheep starting from $$$1$$$ ($$$x_1, x_2, \dots$$$), while the code counts the sheep starting from $$$0$$$ (the variable cur).

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

        I see. I'm wondering whether the author intends that the explanation and the code are not consistent...

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

The option to submit file is not showing. I want to solve those probems which i couldn't do yesterday. When will that option be back? anyone knows it?

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

Wanna share my miserable experience during the contest...

During the last 30 min, the queue is too long, I submitted G, but knew the result after the contest ended, so I don't have chance to debug and resubmit!

QQ图片20210506004222.png

What a pity:<

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

In F2 many people have used ordered_set, order_of_key.

Can someone tell the functionality of this, or some source maybe. Thanks.

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

    Ordered_set basically a set but with 2 extra functionality: We can find the kth element in the set and find the number of elements less than k. You can read about how to use it here

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

My solution for C was, if n != 2, print in appropriate way all odd numbers from 1 to n^2 and afterwards all even numbers.

More easy to implement & understand, I think.

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

Please can anyone can explain problem e?Thanks in advance.

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

    the task was to calculate the minimum steps for which all the * will be adjacent to each other, and at each step either you can move any * forward or backward by one position, so it let's assume the string ..*..***...*..*.... here there are 6 * and we what we want is to make their position consecutive so we have our first * at position 3(one's notation) and last one at 15'th position so can make it like ******............. or .******............ or ..******......... or ...******......... or ....******........ and upto .............****** , we can notice it won't make any sense to start before the first * and * after last * . so we can iterate through all positions from where we can start our * and just calculate the steps for each and store the minimum value.(o(n^2) solution)

    //optimizing it in the orignal string so, we can just precalculate the steps needed to make all the * from left of any position consecutive and the steps needed to make all * consecutive to right of any index, and we can just iterate through our precalculated values and take min(steps for left + steps for right) for entire precalculated value

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

A relatively easier approach for problem C (Not Adjacent Matrix):

At first, we try to fill the array with odd elements starting from 1 till n2, then we fill the remaining cells with even elements starting from 2 till n2. The only exception is when n is 2.

For reference, here is the link to my submission.

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

I think problem C can be easily solved by just simply printing the odd numbers till n*n and then the even numbers. For example, if n=4

1 3 5 7
9 11 13 15
2 4 6 8
10 12 14 16
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Would anyone mind explaining E tutorial again to me? I've been trying for a while but I still didn't get the formula for the final position of the sheep

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

    first group sheep with contiguous segment like ******...***.**....****** here we have four groups of sheep.now it is optimal to fix a group and full its left groups and right groups towards it and minimize the answer .for clear clear concept see here 115315773

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

Alternate solution for F-hard if anyone is interested:

Divide the array into blocks of size $$$20$$$. As a preprocess, store the number of zeros in all these blocks. It takes $$$200000/20==10000$$$ queries.

Now, we can answer each query: find the block where the zero is, and use $$$\lceil \log 20 \rceil == 5 $$$ per query to binary search this block.

In total, we use exactly $$$60000$$$ questions in worst case.

115436756 code with some comments

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

Can someone explain why in problem E, not moving the middle sheep and moving other sheep towards it is the optimal solution?

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

    Consider all sheeps have moved. Then there is a position where all sheeps left of it where moved right, and all sheep right of it where moved left. One of both halfs is the bigger one, WLG consider it be left.

    Then it would be a better solution to move all left sheeps one step less, and all right sheeps one step more.

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

Hi, guys! Trying to solve F2 with multiset. I have WA on 9 test. My someone help to find the mistake please? https://codeforces.com/contest/1520/submission/115447429 (Very simple code)

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

    Hello!

    You binary search should return r instead of l, as you only give ok position to r

    But despite that, the interactor's a array changes after you giving you an answer, so there's no need to use multiset.

    The most serious thing is your solution needs $$$t \cdot \lceil\log_2 n\rceil$$$ times to interact, which is much bigger than the limit when $$$n=200000$$$

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

weak pretests in G if you intended to make the dijkstra solution get TLE.

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

In problem C, it's enough to randomize the position of each number until a valid matrix is found. There's a small probability of generating an invalid matrix.

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

There is an block solution for F2.

Let $$$w$$$ be the block size, it will interact $$$\frac n w + t\cdot\lceil \log_2 w\rceil$$$, with $$$w=8$$$, it will interact not more than 55000 times

Uses BIT for prefix sum between blocks, the time comlecity is $$$O(n \log n + t \log^2 n)$$$

115414141

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

solution using Dijkstra's is Runtime error on test 146 ; PLEASE HELP

my submission : https://codeforces.com/contest/1520/submission/115467140

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

115471003

Problem F-2

I can't figure out why it is wrong. It gets wrong at test case 7, can you especially explain that? Because when I try, it seems fine!

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

    Also I realized Jury's Ans != Participant Output but still Verdict is OK.. why is this so?

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

      It shows the number of queries used and not the answer

      If queries will be below 60000 and answers are correct then it will pass it

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

In solution of Problem G:

Here is link to my AC solution. Here is link to same solution that got WA on test case 122 when I used value of LINF as LONG_MAX.

Can anyone explain me this??? I would really appreciate it. Thanks.

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

In problem G:

Here is link to my AC solution.

Here is link to my WA on test case 122 solution, it's exactly similar to previous solution, only difference is value of LINF as LONG_MAX.

Can anyone explain, why this error is caused????

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

укуси меня пчела

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

why this code is giving the wrong answer.

include<bits/stdc++.h>

using namespace std; bool a[26],res; int main() { int t; cin>>t; while(t--) { int n; string s; cin>>n>>s;

for(int i=0;i<n;i++)
   {
      a[i]=false;
   }
   bool res=true;
   for( int i=0;i<n;i++)
   {
      int t=s[i]-'A';
      if(!a[t])
       { 
          a[t]=true;

        }
      else if(s[i]^s[i-1])
        {
          res=false;

          break;
        }


   }
   if(res)
   {
      cout<<"YES"<<endl;
   }
   else
   {
      cout<<"NO"<<endl;
   }

}

}

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

Can anyone explain the logic for G. Thanks in advance!!

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

Anybody had different solutions to F2 and G?

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

    For F2, i think i had a different idea from the one mentioned in the editorial. Basically, the idea is to divide the array in buckets of size $$$32$$$. For each bucket, we'll calculate initially the amount of zeros it contains. Then, for each query, we'll find which bucket contains the given $$$k$$$ and binary search to find its exact position. The number of queries is $$$n/32$$$ for preprocessing and around $$$50000$$$ for all the other queries.
    Code : https://codeforces.com/contest/1520/submission/116861616

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

      oh yess. I had the same idea, but my bucket size was 16. I implemented it and got WA, though. probably just a logic error.

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

For the problem F2-Guess the K-th Zero (hard). It is failing the 4th-test case but my output seems to be correct for the given string 00.

Can someone please help me figure out the issue: Submission link: https://codeforces.com/contest/1520/submission/119638144

Output on my terminal (for the 4th test case: 00):

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

I code a radix heap for my dijkstra's algorithm to solve G directly, but got tle on test 134. Can anyone tell me how to generate a test data like it, or how to hack my submission?

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

For problem F2, I have another solution with block ideas and a segment tree.
Out of 60000 queries, let's spend the first $$$X$$$ queries on preprocessing.

My processing goes like this:

  • Divide the array into blocks of size $$$N/X$$$ and query for each block (i.e., find the number of zeroes in each block).
  • Build a sum segment tree with these blocks as indices and the zero_count as values.
  • We can find which block my $$$K^{th}$$$ zero belongs for each test case using the binary search + range query technique.
  • After finding the block number, we shall binary search as same as the F1 solution, but within the block.
  • This costs extra $$$log(N/X)$$$ queries for each testcase.

So total queries = $$$X + T*log(N/X)$$$
From this equation, we can show that for $$$X = 12600$$$ , $$$blocksize = 16$$$ we get minimum queries $$$52600$$$

Code: https://codeforces.com/contest/1520/submission/211581160

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

In problem D how do you guarantee that i < j?

How does n * (n-1)/2 guarantee that?