By awoo, history, 13 months ago, translation, In English

Hello Codeforces!

On Oct/09/2023 17:35 (Moscow time) Educational Codeforces Round 156 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov, Alex fcspartakm Frolov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Please note that the problems of this round partially intersect with the problems of the Qualification stage of the Southern and Volga Russian Regional Contest. If you took part in the qualification, please refrain from participating in the round.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Harbour.Space
FULLY FUNDED SCHOLARSHIPS for Masters in Data Science and Computer Science

Scholarships for Master's students in Computer Science and Data Science are available in Harbour.Space University Barcelona campus!

Scholarship Summary:

  • Fully funded scholarship (29.900 €/year) to study a Master’s degree in Data Science or Computer Science for two years
  • Successful applicants will become part of the University’s “Talent pool” and will be shown to the sponsoring companies. In case the candidate is picked for the Work&Study Program from our industry partner, the student starts an internship with a commitment to study 3 hours/day and work for 4 hour/day

Please note preselected candidates will be requested to pay a non-refundable application fee of 85€ to study at Harbour.Space University.

Candidate’s commitment:

You will complete 15 modules (each three weeks long) in one year. The daily class workload is 3 hours, plus homework to complete in your own time.

Candidate’s requirements:

  • Bachelor's degree in the field of Mathematics, Statistics, Data Science, Computer Science or similar
  • English proficiency
  • Advanced knowledge and experience in Python, SQL, Spark/Scala, and bash
  • Experienced use of Big Data technologies: Spark, HDFS, Kafka, etc.
  • Hands-on experience with Data Science techniques: feature engineering,
  • Strong ML knowledge
  • Strong Software Engineering Background
  • Problem-solving aptitude

Note: These scholarships are only available for qualified applicants with a bachelor’s degree.

Apply here →

UPD: Editorial is out

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

| Write comment?
»
13 months ago, # |
  Vote: I like it +21 Vote: I do not like it
Spoiler
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is the contest delayed? It is time but it is still saying 23 minutes left

»
13 months ago, # |
  Vote: I like it -28 Vote: I do not like it

Excited

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

As the person who preordered this contest (i.e. took part in the qualification), the problems are actually good.

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

Alex fcspartakm not a writer on the contest page. I don’t know how I noticed that :)

»
13 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Why do all educational contests have the same authors?

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

    The term "Educational Contests" specifically refers to the initiative by Harbour Space University, so it's organized by the same individuals, with a few occasional variations.

»
13 months ago, # |
  Vote: I like it -39 Vote: I do not like it

Educational Rounds are usually mathforces af. Will skip this one.

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

    I agree with you.

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

    bro you have already skipped all the contest in the last 6 month , i don't think so you should be saying that when you are not active

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

      I am planning to make a comeback but on a positive note. Will start with Div3. I am regular on Leetcode Contests.

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

    Lol you were right with this one ^^

»
13 months ago, # |
  Vote: I like it -15 Vote: I do not like it

No offensive but I have a bad feeling about this round T.T

»
13 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Classic huge difficulty gap between C and D.

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

    Even C is really annoying binary search problem.

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

      I like C actually

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

      You can also solve it greedily using stacks

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

      I think my implementation is quite clean.

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

      Can you please tell how to binary search?

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

        I haven't solved the problem. Based on the above replies I think I might have overcomplicated my approach. First I found out the indices where the string characters decrease with respect to preceding character. If the indices are say i1,i2,..,ik then s_{ik} is the suffix of s upto starting from ik. The length of s till s_{ik} is n+(n-1)+...+(n-ik+1) So like this I tried to binary search the index upto which we much consider to obtain the index pos. I faced much trouble in implementing this approach due to plenty of corner cases.

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

    What difficulty gap are you talking about? In my opinion, D was easier than C

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

brickforces

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

For me, this is one of the toughest div2D's for sure

  • »
    »
    13 months ago, # ^ |
    Rev. 3   Vote: I like it -15 Vote: I do not like it

    For me, this is one of the harders Div2Cs ever, but D seems ok if you have seen the trick.

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

How to solve D?

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

    It can be noticed that the answer of a string $$$s[0..n-2]$$$ is the product of the indexes with letter '?', thus the problem can be solved easily.

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

      I still didn't quite get the intuition behind the approach. Let's use this string for example :

      <>?<

      The third index is ?, so there will be three possibilities to fill the slot. What are those 3 possibilities?

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

        I use 0-indexed string, so there should be 2 possibilities.

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

      Thank you for clean explanation. The intuition is so cool, I love this question.

      (and I'm simultaneously depressed for not solving it lmao)

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

      Thankyou very much, understood it very well!

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

    Consider the relative order of all the elements, a single "order sequence" corresponds to a permutation. We consider how many of these sequences are achievable by iterating over [1, n]. If a[i] = < or a[i] = >, then we can only place it in the front or back of the current sequence, resulting in an *1 to the answer. Otherwise, the previous i — 1 numbers have i — 2 spaces between then, we can just randomly insert a[i] into one of these, since any two ways of insertion is equivalent, this would result in an *(i — 2) to the answer.

    For the operations (i, c), we notice that every single one of them only result in the change of ways to insert a[i], thus we can make our answer /(i — 2) if it is not ? before the operator and *(i — 2) if not ? after it. We can prework inv to speed the process up to O(n).

    btw, note that if a[1] = ?, the answer is 0.

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

    You can have an order from the first i chars of the string. Now if you get a '>' then a new element has to be put at the end of the order and if you get '<' then put it at the beginning. If you get a '?' then you can put a new element at any position except first and last. There are i-1 such positions. So total possibilities is the product over all (i-1) such that s[i] == '?' (one based indexing).

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

      Thanks Here we are not concerned about which elements will come at a specific postion, rather we are concerned about how many ways are there to place the a fixed element a[i] in the ongoing set Am i correct?

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

      Could you explain what do you mean by "order" and use some example if possible?

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

        Nevermind. I think I've got it. Thanks for the insight. Let me share an example to help other readers.

        Say our final permutation will named $$$p_i$$$

        Assume we have another sequence of order named $$$ord$$$ where $$$ord_i$$$ is the relative order of $$$p_i$$$

        for example, an order sequence $$$[2, 3, 1, 5, 4]$$$ means $$$p_2 < p_3 < p_1 < p_5 < p_4$$$

        Then from string $$$s$$$, we can "build" the order sequence one by one

        For example let's use $$$s = $$$ <?>? and process each character one by one

        • Put $$$p_1$$$ somewhere in the order
        • $$$s_0 = $$$ < then $$$p_2 < p_1$$$
        • $$$s_1 = $$$ ? then $$$p_3$$$ can only be put between $$$p_2$$$ and $$$p_1$$$ so $$$p_2 < p_3 < p_1$$$
        • $$$s_2 = $$$ > then $$$p_4$$$ can only be put in the end so $$$p_2 < p_3 < p_1 < p_4$$$
        • $$$s_3 = $$$ ? then $$$p_5$$$ can be put at $$$3$$$ different position that is between $$$p_2$$$ and $$$p_3$$$; $$$p_3$$$ and $$$p_1$$$; or $$$p_1$$$ and $$$p_4$$$ (it cannot be placed on either left/right end because otherwise will make the $$$s_3$$$ not equals to ?

        Therefore because there's $$$i$$$ possibilities to place $$$p_i$$$ on the order sequence, we multiply the result by $$$i$$$

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

    Why is it that the problems I don't solve always have the most elegant and easy solutions...

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

loved B. (definitely didn't waste 2 hours on it dealing with precision errors)

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

Can someone offer me the test case 2 of C? I think my code is true but WA in the case 2

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

    The case that broke my attempt was:

    dttkjvzob
    34
    

    Output should be o

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

      I can pass this test case. But I still don't know why I can't pass the 2nd case

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

        I found a problematic test-case:

        1
        npnnpx
        20
        

        The output should be n, but your program outputs p

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

          can you pls help me

          consider below tc

          pbdtm
          8
          

          my solution, s1 = pbdtm, s2 = pbdm, output = d

          jury's solution, s1 = pbdtm, s2 = bdtm, output = t

          pbdm < pbdtm

          why my solution is incorrect?

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

Anyone has done B I find it tricky and difficult. If anyone was able to do please help me...

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

    You have to consider 3 cases:

    1. O and P are closer to B than they are to A. That means that both O and P are both in the circle around B, so the radius is chosen as the bigger distance of the two to B

    2. O and P are closer to A than they are to B: Similar as case 1

    3. One of them is closer to A and the other is closer to B: That means the circles are going to intersect, so you take the distance between A and B into account as well, while making sure that the points P and O lay in the circles

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

      In case 3,is that perfect to just take distance from a to b and divide by 2? Because the points are inside them this is not guaranteed. The only thought for which i Didn't solve it.

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

        No, because if you take the distance between A and B only, it might be the case that P doesn't lay in those two circles.

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

    I was able to get AC with binary search, which was very obvious.

    The tricky part was writing code to check if your radius (w) was valid. There are only two cases; if both the origin and the point P can fit in the same circle, and if they are in separate circles. If they are in the same circle, (i.e if the distance of (0, 0) and (px, py) to the center of the circle is less than your radius), then yes, they fit.

    If they are in different circles, then both circles must touch each other or overlap (i.e 2 * w must be >= the distance between the centres of the circles).

    Then you can binary search. Instead of incrementing/decrementing by 1s, do so by 0.0000001

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

    I did some case work :

    Case 1 : starting and ending points will lie in circle having 'a' as center i.e. dist(a, origin) <= dist(b, origin) and dist(a, p) <= dist(b, p) then only lantern a is relevant so we can set ans as max(dist(a, origin), dist(a, p))

    Case 2: starting and ending points will lie in circle having 'b' as center similar to case 1 but lantern b is relevant

    Case 3 : the starting and ending points lie in different circles, so we take the answer as the maximum of the distance between origin and the closer lantern, distance between target and closer lantern and half the distance between the lanterns (as this time we need both the lanterns so their circles must intersect or touch each other)

    Maybe Case 1 and 2 are irrelevant but I came up with this during contest so no optimisations :)

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

    IMO it's even easier than A

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

is D some well known trick?

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

Skipped D, solved E, after seeing submissions on D I am very confused on why it works

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

    Just consider how the answer changes when a new character is appended to the end.

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

    Read the string from right to left instead, and figure out how many possibilities there are.

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

    How you solved E. Is there a well-known technique? Help me out.

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

How to solve E? QAQ ~

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

    Sort the programmers in decreasing order by their strength; if we want to complete a subset of projects, it's optimal to use a prefix of the best programmers. Let $$$dp(S)$$$ be the minimum prefix needed to complete a subset of projects $$$S$$$. Let $$$nxt(i, j)$$$ be the minimum number of programmers needed to complete project $$$j$$$, if we're starting at the $$$i$$$'th best programmer in decreasing order (i.e., we use programmers $$$i, i+1, \dots, i+nxt(i,j)-1$$$).

    Then for $$$j \not \in S$$$, we can update $$$dp(S \cup {j})$$$ with $$$dp(S) + nxt(dp(S), j)$$$. The values of $$$nxt$$$ can be precomputed in $$$O(NM)$$$, and computing $$$dp$$$ can be done in $$$O(M 2^M)$$$ using bitmasks. There's a bit more work to be done since we have to reconstruct the answer, but that's entirely routine.

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

      How do you precompute the values of $$$nxt$$$?

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

        For a programmer $$$i$$$, let's find the minimum value $$$x$$$ such that programmers $$$i-x+1, i-x+2, \dots, i$$$ can complete project $$$j$$$. The inequality $$$\frac{B_j}{x} \leq A_i$$$ must hold, so $$$x = \lceil \frac{B_j}{A_i} \rceil$$$.

        This tells us that $$$nxt(i-x+1, j) \leq x$$$, since it takes at most $$$x$$$ programmers if we start at $$$i-x+1$$$. In addition, $$$nxt(i, j) \leq nxt(i+1, j) + 1$$$. Therefore we can compute $$$nxt(i, j)$$$ for a fixed $$$j$$$ in decreasing order of $$$i$$$.

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

is E bitmasks again?

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

What a pity, got WA on problem D because I forgot to judge s[0] == '?' in the first output...

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

    i got 2 WA for that one mistake. Luckily fixed in the last minute

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

imho ABC harder than usual. And can anyone please tell how to solve E, thanks a lot!

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

What's the idea behind C? How to solve it?

Can someone please explain in detail. (I was halfway there.)

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

    what is ur thought process?

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

      the String can be divided in inc,inc,inc,dec,dec,dec parts. Then we can find the right part to search in using basic maths.

      Then just simulate the process.

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

      What's the right approach??

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

        lets stimulate the deletion: traversing from left to right, for each element we'll remove the elements(which are not already removed) to it's left which are greater than the current element. While removing we'll store the indexes of the deleted in order of their deletion. Note that the above part can be done using stacks

        Now we'll see the length of the segment for the given n and build that string by using the indexes in the reverse order, and then just print the element at the required index in the new string.

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

          Hmm. This is how i exactly implemented it. I knew the approach but lack implementation part.

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

    I did it using stack. Coz what you care about is the elements at the front. While your current element is less than last element of stack , keep poping it out. Finally your stack will be of length l or you may terminate in middle if length is reached.Just add index of string to the answer. For finding length and index you can use an O(n) loop which adds i where i goes from n to 1 and compare it with pos each time.

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

      Yeah makes sense.

      Why the heck, stack didn't came in my mind.

      Guess this is what happens when you give contest after months.

      Thanks though!!

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

In my opinion, B and C are harder than D.

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

Why was C so hard? Even my O(n) solution gave TLE.

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

    std::string::erase is linear in time complexity.
    https://cplusplus.com/reference/string/string/erase/

    This means your code is $$$O(N^2)$$$

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

      Yeah just realized that was the problem. How do I do it without std::string::erase?

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

        Use std::set for the indices of the string? Think more about this

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

        Another idea, use a prev array, where prev stores the element before the current idx. So at the start prev[i] = i — 1. When element prev[i] (which is the element before i) is deleted, prev[i] will then become prev[prev[i]]. Make sure you move on from the current element when prev[i] < 0.

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

        Maybe you can use crope,it is $$$O(\log n)$$$

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

        Maybe you can use stack.

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

Anyone know how to solve F ?

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

    Turn back time and assume that at moment $$$0$$$ diamonds $$$2$$$ are stolen and at moment $$$d$$$ diamonds $$$1$$$ are stolen.

    For $$$t=1,2$$$ cameras, the time interval to turn it off is determined. For each $$$t=3$$$ camera, it has $$$2$$$ choices:

    1. Turn it off in $$$[d+1,s]$$$.
    2. Turn off in $$$[1,s], [d+1,d+s]$$$ respectively.

    Note the left endpoint of each interval $$$\in { 1,d+1 }$$$. If a decision has been made on what to choose, by Hall's theorem, the illegitimate $$$\Leftrightarrow$$$ appears in at least $$$1$$$ of the following cases:

    1. $$$\exists r$$$, $$$>r-d$$$ cameras need to be turned off in $$$[d+1,r]$$$.
    2. Think of stealing diamond $$$1$$$ as adding an interval $$$[d,d]$$$, then, $$$\exists r$$$, $$$> r$$$ cameras need to be turned off in $$$[1,r]$$$.

    Let's assume, $$$t=3$$$ are turned off in $$$[d+1,s]$$$ by default. Each time, find $$$\min r$$$ such that $$$>r-d$$$ cameras need to be turned off in $$$[d+1,r]$$$. At this point, we need to pick a $$$t=3$$$ camera in the interval and change it to $$$[1,s],[d+1,d+s]$$$. It can be found that the larger the $$$s$$$ chosen, the easier it is to satisfy all the $$$2$$$ restrictions imposed by Hall's theorem. Scan $$$r$$$ while maintaining the stack of $$$s$$$ of $$$t=3$$$ cameras in $$$[d+1,r]$$$, taking the top of the stack ($$$\max s$$$) each time.

    If $$$1$$$ of Hall's theorem is satisfied by this scan, it is straightforward to determine $$$2$$$ once. This is because changing any $$$t=3$$$ makes the $$$2$$$ restriction tighter. Thus the problem is solved by enumerating $$$d$$$ at the beginning and sweeping $$$2$$$ times, with total time complexity $$$O(n^2)$$$.

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

I'm ashamed of myself for accepting without thinking that in problem D, I fixed '>' as N, N-1, N-2, ... and '<' as 1, 2, 3, ...

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

OMGOGMG IM REACHING SPECIALIST YAYYYY

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

The problems were actually good. Got stuck in B itself, and took almost an hour to solve it..

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

I tried solving B with Binary Search, but was getting wrong on Test Case 2. Any hints? https://codeforces.net/contest/1886/submission/227399641

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

Can anyone help me with problem B why I am failing on 2nd testcase 227433725

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

    double num3 = ((px - bx) * (px - bx) + (px - by) * (py - by)); variable error. u did px-by not py-by.

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

      Thanks,after submitting for 15 times I don't realise this silly mistake

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

Can random work for E? I basically tried to shuffle the projects and even though I did a silly mistake in the contest, I'm wondering if this idea would work in the end 227434343.

Thank you.

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

What was the intent of making the answer be output on a single line in problem C? Was it to make implementing the checker easier?

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

    The checker for this problem wouldn't have been a difficult one to implement imo. And I don't think printing in the same line would had have any impact on it..

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

    it's actually very convenient to test your program, since you can query for all positions of the same string and get the resulting concatenation.

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

    Personally, I found it very convenient for testing purposes. I would start with a string, delete $$$x$$$ characters, and then I want to check if my program handled this correctly, so I set up my input to write all characters of that resulting string (so the test cases involve the same original string with the position range corresponding to my desired reduced string). I even wrote a separate program to generate such input text, given the original string and position range.

    I don't know if this relates to the reasoning behind why the output was in one line, but I definitely appreciated this!

»
13 months ago, # |
Rev. 5   Vote: I like it -10 Vote: I do not like it

mathforces

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

Could anyone tell me what i am doing wrong with problem C, my logic is that we always have to remove the first i where s[i]>s[i+1] if there is no such i, remove the last character in the string repeatdly until you reach the ans, i implemented it using linked lists My code

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

    Found the error i was taking the pos in an int variable fml

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

Could someone assist me in debugging problem C? I'd like to understand what went wrong with it.

My approach is quite inexperienced.

Problem C

Thanks.

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

    You don't always remove the maximum character. For example, if your string is baz, removing b gives you az, but removing z gives you ba. Here, az is lexicographically smaller than ba, so you remove b instead of z.

    The correct character to remove is the leftmost character which is bigger than the character in the next index.

    That being said, even if you remove the correct character, your approach of manually finding the character to remove and appending the string would take $$$\Theta (n^2)$$$ time. For $$$n$$$ as high as $$$10^5$$$, this will definitely result in Time Limit Exceeded in later tests.

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

      Hello I have followed the same idea, removing leftmost s[i] when s[i] > s[i+1]. It runs in O(n) time. The no-spaces-bw-testcases rule makes it impossible to find where I'm going wrong. Please help me if you can.

      My Code

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

        I checked the submission details and found one problematic test case:

        1
        klzpdakb
        31
        

        Your program outputs k, but the correct output is a (reduced string is akb at that point)

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

          aw nuts, messed up with the loop condition. Accepted now :). Thanks so much!

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

Why did my submission for E fail on test 16?

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

    Here you need to find the real "lowest" one, not from the first one, because the first one might be dropped.

    for (int i = dp[subCur] + 1 ; i <= dp[cur] ; i++) {
         res[p].push_back(a[i].second);
    }
    
»
13 months ago, # |
  Vote: I like it +2 Vote: I do not like it

For Prblm D we can go like this, We will start filling from backwards.

Initially we will have n elements in our hand,

Suppose at a position i, we had x elements in our hand left to be filled somewhere, Now if s[i]=? Implies that we can't fill the ith position by the maximum or minimum among the x elements which we have, so we have x-2 choices

else if s[i]!=? Then we have to either fill it by the minimum or by the maximum hence only 1 choice

Simulating the above logic finally boils down to

at ith position we have either i-2 choices if s[i-1]=? else 1 choice

Considering 1-based indexing.

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

The solution to D is intended to be done in reverse, which makes everything far simpler, but how is it equivalent to doing it normally?

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

    So for reversed approach, while you are not seeing a ?, your permutation is fixed. The moment you see a ? You cannot remove first and last element which means you can remove any of the remaining i-2 elements.

    In forward approach, as you go on filling your array , you set some unknown numbers in your set. The moment you see a ? you are like I can fill this number in any position in my set except the first and the last position so in total again i-2 options

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

    It's not about Monocarp performing the operations in reverse; we still assume Monocarp performs the actions in the order specified, but our analysis considers the number of possibilities in reverse order.

    Consider the last character; when Monocarp added the last integer at the end of the activity, what could this integer have been? If the last character is >, then this means that the last number Monocarp added must have been $$$n$$$ (only one possibility). If this last character is <, then this means that the last number Monocarp added must have been $$$1$$$ (only one possibility). If this last character is ?, then this means that the last number Monocarp must be between $$$2$$$ and $$$n - 1$$$ ($$$n - 2$$$ possibilities). We can then extend this argument to all indices in reverse order.

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

      Yeah I later realized that looking at the operations in reverse is equivalent to looking at them normally. It doesn't change the answer at all and is far simpler than doing it normally

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

If you have solved the basic DP tasks from atcoder, the D is a no-brainer problem. 😶 https://atcoder.jp/contests/dp/tasks/dp_t

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

great!I get +70 points!

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

And i will get candidate master only +9!

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

it was a really great contest and i learnt a lot from it

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

The problem D in this contest is very interesting