isaf27's blog

By isaf27, 5 years ago, translation, In English

Hello, Codeforces!

I'm glad to invite you to Codeforces Round 559 (Div. 1) and Codeforces Round 559 (Div. 2), which will be held on May/12/2019 17:35 (Moscow time). The round will be rated for both divisions (I hope).

All problems were written and prepared by me. Thanks to Aleks5d, TLE, sunset, Sulfox, peltorator for testing problems and good advice, 300iq for round coordination and help with preparation and MikeMirzayanov for great systems Codeforces and Polygon.

You will be given 6 problems in both divisions and 2 hours to solve them. Please, read all the problems. Good luck, have fun and I wish everyone high ratings!

The scoring distribution will be announced closer to the beginning of the round.

UPD

The contest finished, contgratulations to the winners:

Div1:

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

Div2:

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

Editorial

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

| Write comment?
»
5 years ago, # |
Rev. 4   Vote: I like it +11 Vote: I do not like it

Orz Sulfox, wish I will be red too!

»
5 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Orz Sulfox

»
5 years ago, # |
  Vote: I like it +104 Vote: I do not like it

I'm not peltorator, I'm peltorator. Fix it, please.

»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Please,No MathForces !!!

»
5 years ago, # |
  Vote: I like it -41 Vote: I do not like it

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?

»
5 years ago, # |
Rev. 2   Vote: I like it -99 Vote: I do not like it

Okay! Thank u for your unreasonable voting :V

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      FYI Ramadan is not about eating but fasting.
      By the way, they don't eat Biryani in Russia :V

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

    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.

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

I like the weekend contest, thank you isaf27.

»
5 years ago, # |
Rev. 3   Vote: I like it +27 Vote: I do not like it

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".

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

    Hope is a good thing.

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

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -61 Vote: I do not like it

      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.

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

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -68 Vote: I do not like it

          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?

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

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

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              what's twix? what's the volume of Lipton? Could you give some links?

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

                Never mind, local jokes :)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Have I misunderstood you? Do you want Mathforces?

»
5 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Sulfox is our red sun!

»
5 years ago, # |
  Vote: I like it -65 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

looking forward to Sulfox 's contest!

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

    This is not my contest. I just test these problems for the correctness.

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

      Will your profile picture change to megagnar when you're angry

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

      Maybe he is looking forward to the one in the future.

»
5 years ago, # |
Rev. 2   Vote: I like it -41 Vote: I do not like it

Bad schedule for Man City & Liverpool fans! :p

»
5 years ago, # |
  Vote: I like it -27 Vote: I do not like it

help me pls :(

»
5 years ago, # |
Rev. 6   Vote: I like it +63 Vote: I do not like it

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 :(

»
5 years ago, # |
  Vote: I like it +61 Vote: I do not like it

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

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

    Maybe we can finally switch to using dynamic cloud providers instead of fixed hardware in the ITMO basement?

»
5 years ago, # |
  Vote: I like it +69 Vote: I do not like it

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. :(

»
5 years ago, # |
  Vote: I like it +101 Vote: I do not like it

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.

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

    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.

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

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

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

        Neither was anyone else, which at least is fair.

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

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

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

      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.

»
5 years ago, # |
Rev. 4   Vote: I like it +16 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +110 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it -14 Vote: I do not like it

    .

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

      Main site was down at the start for less than 10 minutes. All the mirrors were still up. Rounds have been rated in more drastic cases, if I remember correctly. So please make this rated, even if the participant count was lower than usual because of technical issues.

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

        Last week we got an unrated round because of weak pretests on problem A lol.

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

          That round being unrated was one of the worst disappointments I have ever faced

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

            I agree. That contest was all right except problem A.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for me the page didnt work normaly for like 45 min

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That's unusual. I had no downtime on the mirrors and only like 10 minutes on main site.

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

      Neither did anyone else.

»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    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.

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

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

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

        There are almost 24 hours that can register. When did you register?

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +104 Vote: I do not like it

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

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

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

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

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

»
5 years ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

Good tasks, thanks!)

»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
5 years ago, # |
Rev. 3   Vote: I like it +54 Vote: I do not like it

Me: Reading the problem statement of Div 2 C

made wild assumptions and passed for some reason

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

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

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

      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."

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

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

      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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

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

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

      You uploaded Div2 C code, but T1duS asked Div1 C.

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

        I already got it. I forgot that there is a div1 in the same with div2

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it -8 Vote: I do not like it

    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

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

      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 . . .

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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);
    }
    
»
5 years ago, # |
  Vote: I like it -65 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve Div2D?

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

    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

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

    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

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

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

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

        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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

    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)

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

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

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

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    I repeat my comment, but anyway : "You can see my greedy solution (but i cannot prove it). Answer my comment if you have questions. " 54046042

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe he means Div1 ???

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

      If you see a purple or a red guy asking for C, its probably not Div2 C that he's asking for.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    make $$$nxt_i = i + 1$$$ for each $$$i$$$ $$$(nxt_i = -1)$$$

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

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.)

»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

How to solve div1D?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    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.

»
5 years ago, # |
  Vote: I like it +161 Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think olny the last one accepted in pre test.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the first sumbissions are skipped, only the last one is valid.

»
5 years ago, # |
  Vote: I like it -29 Vote: I do not like it

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

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

    I did terribly, but I still think it was a good contest. Although CF going down all the time is really annoying, there are m1/m2/m3 sites that work pretty consistently. Also div2c/div1a wasn't that unclear. They explained anything that might be confusing under the samples.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Learn Russian :)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    div2c was rather clear
    but there are some noobs who cant read

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

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

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

    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.

»
5 years ago, # |
Rev. 3   Vote: I like it -23 Vote: I do not like it

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
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      omg its true... Thank you for the information!

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

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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%

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

      You've got a good point, perhaps I_Didn't_Do_Enough_Things_For_WA

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div1C pls?... :)

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

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

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can we see the tests pls?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 Σ(  ̄□ ̄||).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem B?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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|) ?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 .

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    Edit nvm I read it wrong

    as tfg said 0{1068}1 i completely overlooked that mybad

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For t="0{$$$1067$$$}", I think we have at least two $$$l$$$s in problem statement, $$$l=1$$$ and $$$l=1069$$$...?

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

    0{1067}10 appears more than once

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    0{1068}1 happens only once.

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

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.

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

    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.

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

      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

»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

English editorial anywhere?