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

Автор isaf27, 2 недели назад, По-русски,

Привет, Codeforces!

Рад пригласить вас на Codeforces Round #559 (Div. 1) и Codeforces Round #559 (Div. 2), которые пройдут в 12.05.2019 17:35 (Московское время). Раунд будет рейтинговым для обоих дивизионов (я надеюсь).

Все задачи были придуманы и подготовлены мной. Большое спасибо aleks5d, TLE, sunset, Sooke, Peltorator за тестирование задач и ценные советы, 300iq за координирование и помощь в подготовке раунда и MikeMirzayanov за отличные системы Codeforces и Polygon.

Вам будет дано 6 задач в обоих дивизионах и 2 часа на их решение. Советую прочитать все задачи. Удачи, высокого рейтинга и удовольствия от решения задач!

UPD

Контест завершился, поздравляем победителей:

Div1:

  1. mnbvmar
  2. ecnerwala
  3. ainta
  4. ksun48
  5. ekzhang

Div2:

  1. hbi1998
  2. Nutella3000
  3. calabash_fool
  4. ahgus89
  5. 1207koo

Разбор задач

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

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

Orz Sooke, wish I will be red too!

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

Orz Sooke

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

I'm not Peltorator, I'm Isaf27_loves_me. Fix it, please.

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

Please,No MathForces !!!

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

UPD1: The round is carried over for 20 minutes.

UPD2: The round is carried over for 15 minutes.

UPD3: The round will be unrated.

People who has +200: Why do I participate?

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

Okay! Thank u for your unreasonable voting :V

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

    I guess he will consider, if you give him some RAMADAN special biryani xD

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

    It's hard if not impossible to consider the prayer time. Because the prayer time in every country are not same and people from all over the world participate here. And every minute is a prayer time in somewhere in the world. So when do you suggest to schedule the contest?

    Moreover, this platform have people from many religion, culture and region. The platform must not run by considering any religion, culture or region. The platform should be secularist and International.

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

    Obviously, every hour there is muslims have fast breaking in Ramadan

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

I like the weekend contest, thank you.

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

I like the weekend contest, thank you isaf27.

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

I hope this will be IMO contest from isaf27, not 2 problems like "write a segment tree" and 4 problems like "write a link-cut tree with operations ADD, FIND_SUM and REVERSE_ALL_BITS in $$$ne^{\sqrt{\log n}}$$$ time and $$$n\log^{2.39}n$$$ memory".

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

    Hope is a good thing.

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

    I completely agree with you. Hope there will be some problems like find the equation of Euler line $$$\dots$$$

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

      Actually, I gave the problem about Euler line to isaf27 and he didn't solve it because of its extremely high idea level, so I don't think we'll see it in the contest.

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

        Please, don't discuss the problem from some contest in the future

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

          Yes, I hope nobody runs into this discussion and sees any ideas of problems that are to be used in the future.

          Blah-blah, blah, blah, so, isaf27, does your last statement mean that we can find the optimal length of twix in $$$\mathcal{O}(1)$$$ time per query?

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

            We should find a formula dependent on the volume of Lipton. I can't answer your question now, it's too hard.

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

    Have I misunderstood you? Do you want Mathforces?

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

Smh, All red contest. Hoping it will be balanced.

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

I will solve cookie (0) problems this round too!

All hail cookie

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

Sooke is our red sun!

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

I guess there will be a massive drop in participation from India due to the finals of IPL. (Once in a year).

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

I'm not gonna participate because i have final exams and I'm not gonna study because i wanna participate and I'm not gonna participate because i have final exams Sad ..

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

looking forward to Sooke 's contest!

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

Bad schedule for Man City & Liverpool fans! :p

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

Tanmay Bansal will give contest today

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

help me pls :(

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

Wish my rating will up up QAQ

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

Am I the only one who is facing problem accessing the problems and submitting the solution? Each time I submit the solution I am getting the verdict "You have submitted the same code before" but in "my submission" tab I am not able see the submission :(

It's almost half way and I am facing same problem now even! Can't submit my solution for A and B (or don't even know if they has been submitted successfully or not?) Doesn't matter which problem I am going to submit, I receive the same verdict all the time :(

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

unrated? site was down for the first 30 minutes for some people

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

Why is it impossible to register on m1.codeforces.com? I tried to register 10 minutes before the contest but the main site was down so I couldn't. And I can't even read the problems if I'm not registered. :(

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

I'm doubtful if the round should be rated. Quite a lot of people throughout the world experienced traffic issues. I think that absence of the score distribution in the round announcement post at this moment (45 minutes have passed) indicates the severity of the problem.

Everyone knows that the problemsetters, the coordinators and the Codeforces Headquarters endeavored to deliver the best contest. The same applies to the current participants, who tried to solve the prepared problems despite of the mayhem. But is there any reason to persist a rated contest if the impact of the techincal issues is apparent, for the sake of sportsmanship? Unrated contest is not a total failure; there are things to gain and learn, and the efforts of the contest managers do linger.

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

    Sorry about the technical issues, it seems some misconfiguration happened in process while I jump between servers. I work hard to diagnose and fix it.

    The notice about the micro-sites (green information bar in the header) appeared about 1 hour before the contest. Also I remind it in the official Telegram channel. Am I right that m1/m2/m3 work good without technical issues? I think it means if you follow recommendations you was able to read and solve the problems without any timeouts.

    • »
      »
      »
      13 дней назад, # ^ |
        Проголосовать: нравится -23 Проголосовать: не нравится

      Not everyone saw that notice. I tried to login 5 minutes before the contest starts and the site was already down.

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

      But i wasnt able to know scoring distribution, and i couldn't view standings.

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

      m1/m2/m3 worked perfectly for me. It loaded almost instantly.

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

      It was fine, i didn't know what to do the first 2 minutes but then it was fine just like a regular contest.

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

      Yes , light weight sites worked good ...i submitted 3 problems from there without any unnecessary delay. Thank You!

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

      You can't log in to m1/m2/m3 sites with a google account because of which I couldn't submit for the first 15 minutes.

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

MikeMirzayanov crashed his scooter into a rack of servers,so site was down for 30 minutes .Is the round still rated?

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

There is no reason to make the contest unrated. The technical issue was in the beginning of the contest. Everyone could use m1 m2 or m3.codeforces.com. Participants who didn't use those sites and therefore lost time could still decide not to submit and don't participate in the round. Submitting code means you could use the system well or you accepted that you lost time. Everyone who submitted code made the decision to participate in the rated contest.

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

The main problem was even though I tried to use m1/m2/m3, somehow I wasn't registered(though I was), so I had to wait for 20 minutes to register and then submit solutions to m1. I guess I'm not the only one, who was unregistered without knowing.

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

    Then why didn't you register in advance? It is not that the site has been down for the whole time it has been able to register.

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

      I was registered in advance, but then system unregistered me, so I couldn't enter the contest on m1/m2/m3.

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

Someone posted the solution to div2 A in the blogs already lol.

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

Problem D is Windy Path (Problem L) from the 2016 ACM-ICPC Pacific Northwest Regional, with slightly higher bounds.

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

    Thank you. I was sure that I saw this problem in some contest but couldn't remember the exact contest.

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

    The bounds is not important. I'm sure that almost people have the same solution for both.

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

Good tasks, thanks!)

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

这c真垃圾

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

изи)

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

Div 2C was a little unclear. Spent 20-25 minutes trying to understand what the question meant.

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

TIL you can submit in the mini-sites. I just read the problems :/

Doesn't matter much for me though since it took me so long to solve A that the servers were up when I was ready to submit

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

Me: Reading the problem statement of Div 2 C

made wild assumptions and passed for some reason

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

    Can you please explain why it was so hard to understand? It got two clarifications and I could not understand why.

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

      The statement was confusing. The word "some" was somewhat misleading. I would have separated the key sentence into two sentences as follows: "Boy i gave at least b_i sweets to each girl. Girl j received at most g_j sweets from each boy."

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

      In theory everything was written in the statement, but for example I thought that each boy has to give at least $$$b_i$$$ sweets each girl and I couldn't get it right without asking a question to first sample.

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

      I thought bi is the upper limit for the number of candies the girls received from each boy. Then I figured out that is wrong, so i thought it means the upper limit for the total number of candies received

      Actually the main reason for the problem should be my poor English...

      There isn’t any actual problem about the statement, everything should be alright after reading the samples I guess

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

How to solve C?

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

    Hint: Solve the problem assuming there are no missing values, after that it will be easy to extend it to the general case.

  • »
    »
    13 дней назад, # ^ |
      Проголосовать: нравится -31 Проголосовать: не нравится

    You can see my greedy solution (but i cannot prove it). Answer my comment if you have questions. 54046042

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

    Build a graph for relative order of p : if p[i] < p[j], there is an edge from i to j

    If there is a valid topsort order, there is the answer

    We build an edge from i+1..next[i]-1 to i and an edge from i to next[i].

    However, there are O(n^2) edges.

    To solve the problem, use segment tree to represent a range of nodes build two edges from [l..r] to [l..mid] and [mid+1..r] so there will only be O(n) number of nodes (not more than 4*n)

    EDIT: Hope I won't get TLE on systest :C

    EDIT2: Accepted :D

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

      I think there is an easier solution. For any -1 in the input, use i+1 (point them at the next node); this should not change the existence of a solution. As you read the nodes, keep track of the previous nodes that point at following nodes with a stack, and make sure they nest properly. Finally, sort the nodes using (next_i, -i) and assign values according to this order. I think this works . . .

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

      It is sufficient to add edges of two types:

      • i to next[i]

      • the first index j to the left of i such that next[j] > i (if it exists), where we add an edge from j to i

      So there are only O(n) edges anyway. (Code)

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

    Couldn't get an AC in the contest. I used a greedy algorithm.
    Let us try filling the array smallest to largest.
    We can observe that if next[i] = j, than for any x, i < x < j , next[i] <= j.
    Also, permutation[x] < permutation[i] < permutation[j] . We can just fill the subarray (i+1 to j-1) first, and then fill i.
    We can then go on working on array starting from j.

    int small = 1, flg = 0;
    void solve(int st, int en) {
    
    	if(st > en || flg)
    		return;
    	if(nex[st] == -1)
    	{
    		ans[st] = small++;
    		solve(st+1, en);
    		return;
    	}
    	if((nex[st] > (en + 1)) || (nex[st] <= st))
    	{
    		flg = 1; // determines invalid case
    		return;
    	}
    	solve(st+1, nex[st]-1);
    	ans[st] = small++;
    	solve(nex[st],en);
    }
    
»
13 дней назад, # |
  Проголосовать: нравится -65 Проголосовать: не нравится

How about making the round rated for only positive rating changed users? (This happened previously in codeforce)

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

Div 2E seems to be easier than Div 2D.

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

How to solve Div2D?

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

    Try to write a brute force and observe patterns. ;)

    The key is the number z = (n — k) / 2.

    You build a string with [z zeros, a one, z zeros, a one, ...]

    e.g. n = 14, k = 10, 00100100100100

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

    You can repeat the pattern 0000...001 over and over up to n length.

    The number of zeros in the repeating pattern is (n-k)/2.

    I am actually surprised why there has not been more solves. Makes me doubt the solution

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

      I couldn't figure out this pattern by myself. What was the idea behind it to came up with this idea?

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

        Tried some things with pen and paper, observed the pattern, coded a brute force solution and observation proved valid for all n upto 20. So, went for it : P

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

      Even in the examples, u can see the patterns...

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

    Say you are given $$$n$$$ and $$$k$$$. Set $$$d = \frac{n-k}{2}$$$, $$$l0 = floor(\frac{d+2}{2})$$$, $$$l1 = floor(\frac{d+1}{2})$$$. Now the string of $$$l0$$$ zeroes, $$$l1$$$ ones, repeat works. The special case is $$$k=1$$$, in which case you can only have one 0 or 1, and can use 0111... as your string.

    This works, since the string is cyclic with length $$$l0 + l1 = d+1$$$, and the start-point x (zero-indexed) of some substring mod $$$d+1$$$ uniquely determines its content, and the content for all residues is different. Therefore WLOG $$$x \leq d$$$. Let $$$s$$$ be the length of the substring. We must also have $$$x + s + (d+1) > n$$$, since otherwise the string occurs again $$$d+1$$$  characters later. So now we have: $$$s \geq n - x - d \geq n - 2d = n - (n-k) = k$$$

    Completing the proof.

    Submission: 54040228 (function count is unused, I just used it to test the code)

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

      Is the formula $$$n + 1 - 2 \cdot (\frac{n-k}{2} + 1) = n + 1 - (n - k + 2)$$$?

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

        You're right, the inequality should have been strict. Fixed.

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

          Besides, do we really need to treat k=1 as a special case? I just use the overall implementation and i still got an accepted.

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

:( I was trying to solve C problem (div2) with vector and there was time limit exceeded, i was using vector but i guessed at the end, the problem will be solved with just simple array, vector is too slow.

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

I can not access the site util the contest had passed 20 minutes. Stabilize the main site plz.

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

How to solve C?

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

When I asked why Div2C sample3 's note said the first boy presented 1,2,1 sweets instead of 1,1,2 it just replied me to read the global announcement :(

(The problem has been fixed without announcement during the content.)

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

How to solve div1D?

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

    Problem D is Windy Path (Problem L) from the 2016 ACM-ICPC Pacific Northwest Regional, with slightly higher bounds.

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

    I think traversing convex hull and recalculating it after removing a point each time should do the trick.

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

    Lemma: Given any point $$$P$$$ on the convex hull, there always exists a solution that starts at $$$P$$$.

    Proof: We use induction (with the algorithm below).

    Clearly we can do it for $$$N = 2$$$. For general $$$N$$$, let $$$X$$$ and $$$Y$$$ be the points adjacent to $$$P$$$ on the convex hull. Because the entire set of points lie on one side of both the lines $$$\overleftrightarrow{PX}$$$ and $$$\overleftrightarrow{PY}$$$, we choose $$$X$$$ to be our next point if the first direction is to turn left, otherwise $$$Y$$$ if we want to turn right. Then we can remove $$$P$$$ from the set of points and continue by induction on $$$N - 1$$$ points, as $$$X$$$ and $$$Y$$$ will still remain on the convex hull after removing a point.

    Time complexity is $$$O(N^2)$$$. You don't need to find the entire hull; you can find $$$X$$$ and $$$Y$$$ in linear time using one step of gift wrapping.

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

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

If I make 2 submissions for a question, both correct.. will the first solution be checked?

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

Very Unfair Contest. First Server problem,then Div 2 C not clear and also announcement were not upto the mark.It should be unrated.

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

I am a newbie. How to solve Problem(B) Div 2.?

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

    https://codeforces.com/contest/1159/submission/54032077

    A tutorial will probably come in a few days describing exactly how to solve it, but if you can understand this code, then that's all you need. I personally tried a lot of greedy solutions and I would have never thought about this one. I don't even know why it works to be honest. Anybody have an explanation ?

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

    This is how I solved it. First of all, notice that we can rewrite the $$$k$$$-extension condition for a pair $$$(i,j)$$$ to the following:

    $$$ k \leq \frac{\min(a_i,a_j)}{|i-j|} $$$

    The important observation is that the right hand side of that equation does not depend on $$$k$$$, so for every pair we have an upper bound to the value of $$$k$$$.

    Since this must hold for every pair $$$(i,j)$$$ such that $$$1 \leq i,j \leq n$$$ and $$$ i \neq j$$$, we conclude that an upper bound for $$$k$$$ is $$$\underset{ 1\leq i\neq j \leq n }{\min} \frac{\min(a_i,a_j) }{|i-j|}$$$, since $$$k$$$ should be less than all those upper-bounds in order to be a $$$k$$$-extension. Moreover, by definition we have that all $$$k$$$ that are less or equal than that number work. By choosing the biggest $$$k$$$ as possible (which is the smallest upper bound) we have our answer.

    Now that we know what the answer is, the remaining question is how to calculate it efficiently. An idea to do this is to find a small amount of candidates for those pairs and calculate the upper bound only for those pairs. To do this you can prove that the pair that attains such minimum must necessarily be paired with either $$$a_1$$$ or $$$a_n$$$, this gives us only $$$2n$$$ candidates and we can simply try all of them.

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

1159D - The minimal unique substring

What is wrong??

54043161

int solve(int n,int k){
	lint p=0;
	if(n==k){
		rep(n)cout<<'1';
		return 0;
	}
	rep(k/2+1)cout<<"10",p+=2;
	while(p<n)cout<<((n&1)?'1':'0'),++p;
	return 0;
}
n,k--------------------
output
1,1--------------------
1
2,2--------------------
11
3,1--------------------
101
3,3--------------------
111
4,2--------------------
1010
4,4--------------------
1111
5,1--------------------
10111
5,3--------------------
10101
5,5--------------------
11111
6,2--------------------
101000
6,4--------------------
101010
6,6--------------------
111111
7,1--------------------
1011111
7,3--------------------
1010111
7,5--------------------
1010101
7,7--------------------
1111111
  • »
    »
    13 дней назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Maybe I am wrong as I am from Phone, but it seems for 9, 5 it would give 101010111, which has shortest unique 3

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

    Had the same idea, but realized it would fail for larger n values...

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

    I think that in the future, you should preview your question before posting it, it is badly formatted.

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

какова причина делать мультитест в C?

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

    чтобы ТЛлили все решение не за O(n) / O(n log n)
    имхо

    Ну или для того, чтобы все поучились чистить инфу для каждого отдельного теста

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

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

Ten minutes after the game I saw the surface, sad

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

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

You think the geniuses are those who prove the Fermat's theorem? No, the geniuses are those, who made div2 D )))

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

This round in a nutshell : "I'm just gonna make some crazy assumptions and hope they pass the tests." Also, the difference between C and D was too much.

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

    D was not that difficult. If you can brute force, you will easily find the pattern.

    However, if you are talking about clarity in problem specification, I agree 100%

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

почему после проверки сразу не дают баллы?

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

Can we see the tests pls?

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

How to solve div1C pls?... :)

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

    In this task we just need to check, that topsorted-order of vertices is correct.

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

Can we see the tests pls?

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

Hello,I got some questions with problem C (Div2)

for

2 1

0 0

1

I think the answer should be -1.right?

I missed this situation during the contest.And I think my solution 54038745 will be WA after system test,but it's still accepted Σ(  ̄□ ̄||).

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

How to solve Problem B?

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

    for every item in the array, the value of k for that specific item = value/distance, where distance is maximum distance possible i.e either from 1st or from the nth item, now from all these values of k the minimum one is the answer. Pseudo code : i from 1 to n k=min(k,a[i]/max(n-i,i-1) print(k)

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

      I am not getting why we are taking individual values min(k, a[i]/max(n-i, i-1) ? aren't we supposed to consider the every pair? i.e.min(k, min(a[i], a[j])/|i-j|) ?

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

        We can take individual values because in min(a[i],a[j]) if we take individual values it won't affect our answer in the end, because even if we calculated for the bigger value also, when taking min(k,a[i]/dist) that value will automatically be eliminated .

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

Can you tell me why my submission to Div.1B got WA on test 22?

Test 22 is $$$(n, k) = (5783, 2359)$$$, and my output is '0{$$$1067$$$}10{$$$2357$$$}10{$$$2357$$$}' (0{$$$n$$$} means $$$n$$$ zeros) Judge says minimal unique substring for my output is 1069.

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

In Div2E/Div1C.
Does anybody know why this 54049263 gives MLE? When I change stack to set I get AC in this 54047364

My Approach: Construct a directed graph where edge (u,v) means a[u] < a[v] and then do topological sort on that graph.

The way I construct it is if nxt[i] = j that means there is an edge(i, j), also there is an edge between all elements [i+1, j-1] and i since all of them must be less than i. I only keep track of the least previous element.

Here's an example where ix, jx means nxt[ix] = jx:
i1 i2 i3 ... j3 j2 j1. Edges are (i1, j1), (i2, j2), (i3, j3), (i2, i1), (i3, i2). I don't add (i3, i1) since it's redundant.
In a case like i1 .. i2 .. j1 .. j2 In the MLE submission I exit immediately and say that it's impossible. In the AC submission with set I let the topological sort handle it.

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

    Change vector<stack<int>> Pop(n); to vector<stack<int, list<int>>> Pop(n); and MLE should be gone. This is happening because when you pop elements from the stack, the underlying container (deque is the default) is not actually freeing up space. deque will hold the allocated space during the entire runtime of the program. So just change the underlying container to list, which on the other hand frees up space when an element is removed from it. Now you are maintaining $$$N$$$ stacks which can have upto $$$N$$$ elements, thus requiring too much space if space is not freed when elements are popped off the stacks. list will free-up space and your program wouldn't run into MLE. Also, set will free-up space as soon as your erase from it. Thus your second program doesn't run into MLE.

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

      Thank you so much for the answer! I've changed the internal container from
      vector<stack<int> > Pop(n) to vector<stack<int, list<int> > > once and to vector<stack<int, vector<int> > > once and both got AC without changing the other stack to set.
      However I've got 2 questions.

      1- Shouldn't my total amortized memory be N not N^2? at each iteration I do at most one push_back in some deque in Pop[i]? even if I don't free up memory shouldn't that be fine because the total number of elements in all N deques will still be N? specially since AC solution passes in 27~35KB so I'm not on the edge of running out of memory.

      2- Why does changing the underlying container to vector<int> still pass although the vector doesn't shrink the capacity with the pop_back() calls either? I know that deque requires more memory than vector but is it really that much more?

      Please note that I've only changed the underlying container in Pop. I haven't changed the other stack to set, neither have I changed its underlying container either. I've only made changes to vector<stack<int> > Pop(n).
      Here's the latest 2 submissions: 54094520 , 54094473

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

OMG finally purple! Gonna try not to lose this next contest lmao

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

Thank you for your contest !!!!!!!!!!!!!!! I very love it

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

Please translate the tutorial to English isaf27, can't understand google translation of 1159D - The minimal unique substring's solution

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

I tried solving Div2 E with a solution of complexity O(t*nlogn) and am getting a TLE. Can anyone suggest why? Submission link — https://codeforces.com/contest/1158/submission/54055728.

I basically replace all -1's with a positive value in the following manner ~~~~~ int o = n+1; for(j = n-1; j>=0; j--) { if(inp[j]>0) o = inp[j]; else inp[j]=o; v.push_back(make_pair(inp[j],o)); } ~~~~~ I then sort this v vector and construct the answer array by using the values in the inp array. Finally, for any element if according to the input array, the first element greater than the current element(stored using a stack and array) is at an index before than that in the input array, then the answer is -1. The sorting step might be the time consuming step but I don't get how I am violating the time limit.

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

    I think your problem might be this line:

    while(z<ans.size())
    

    Your ans array is pretty big and never resized, so for every input you're going to be running this loop over all of ans.

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

Can someone help me with Div2-D ? Not able to figure out the greedy approach.

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

English editorial anywhere?