Educational Codeforces Round 125 [Rated for Div. 2]
By awoo, history, 3 years ago, translation, In English

Hello Codeforces!

On Mar/22/2022 17:45 (Moscow time) Educational Codeforces Round 125 (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, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out.

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

Comments Comments (172)
| Write comment?
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Best of luck

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

Good luck to everyone !

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hope to be specialist after this round

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

    gl

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

    Bruh !! Why after even commenting, you didn't participate. Believe me you would have easily made it to the specialist!. Anyway next round is coming soon. All the Best , don't afraid , just believe in yourself. I am saying this because i was also in your situation a while ago. But Now i am a solid specialist trying for expert... got a +99 delta too in today's round just +100 points away.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      For sorry I get late in colleage and went to the nearest place after 30 minutes of the begining of contest and solve three questions in 30 minutes but with another account, I am sad but i will go up next time isa thanks for advice.

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

    How to prove A?

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

      If (x , y) = (0 , 0) then answer will be 0 because he needn't move Else Sqrt (x * x + y * y) if it is integer then answer will be one Else Answer is 2 and two operations will be Go to (x , 0) from (0 , 0) and sqrt( x * x + 0 * 0) = x is integer Go from (x, 0) to (x, y) and Sqrt ( (x -x)* (x * x) + y * y) = y and also integer

      → Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Hope to become CM tonight :> Good luck for everybody!

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Hope for the best, but prepare for the worst.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck guys!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope my rating's downward trend turns around in this contest.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +80 Vote: I do not like it

I hope there won't be too much fst in this contest :-)

Don't click it
→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck everyone! One day I will be a pupil.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Best of luck to everyone

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hope I will become grandmaster in today's contest

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

    Confident man, I'm sure you'll be the Legendary Grandmaster after tonight's contest.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck to everyone this turn!

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I am less confident in giving first contest just after getting promoted , it been a while since I get back to specialist . How to deal with this ?

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

    Believe in yourself. Even if you are demoted to pupil after this contest, there are chances in the upcoming contests to be promoted again. If you deserve to be a specialist, you will remain a specialist.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +33 Vote: I do not like it

    Take it easy and don't start to panick or get upset if everything is not going well. At the end, it's just a title, skills are more important than titles. And right, if you deserve this title, you'll keep it or achieve it soon later on, if you fail today. Wish you good luck!

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

    Thanks a lot mahirlabibdihan and M_bolshakov for boosting my confidence . And yeah I have seen progress and sooner or later I will achieve it if I fail today .

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

    i became a specialist in dec 2020 and still a specialist

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

      I can definitely see the progress , there is lot of difference when the first time you become specialist and now . You are expert now and Yeah I got your point . Your badge doesnot show your skill set .

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

    Take a look at this post. It talks about the fear of rating loss and shows it's no big deal.

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

      Thanks for the post Deepesson ,that is exactly what I am facing and now after reading it ,I think I can handle it .

      → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Good luck everyone!

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Why 10 minutes delay?

→ Reply
»
3 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Why many people on codeforces are so demotivating? I see many posts with too many downvotes even though it does not deserves downvote

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

why the start time became 10 minutes later?

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

    Probably technical issues. Codeforces was really slow for me 5 minutes ago.

    → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Good luck everybody!!!!!!!!!!!!

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

delayforces REEEE

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

10 minutes delay

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

I Hope to become Pupil,today.

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

It is taking some time to load a page, same to you?

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

    You can use mirror. I use it, when sending A, because very slow loading.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

set easy questions from next time

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Struggling to solve A.

→ Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

A,B,C Done! Good Night Everyone!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

2 consecutive speedforces contests :(

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

speeeeeeeeeeeed forces!!!! :(

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D.

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is F 2-SAT on edges with implications for every consecutive pair in some path, with LCA to find the actual paths?

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

    Pretty much, but LCA is not needed since the sum of path lengths is O(N).

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      right, parent, entry and exit times from a dfs are enough for find path in O(|path|)

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the intended solution for D? Surely it wasn't sqrt decomp with log factor?

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

    Mine was harmonic-like where we notice that units and monsters are basically h * d, group units by cost, and loop over all possible number q of units of each cost (works fast coz sum of C/i for i <= C is O(C log C)); then for each q binary search for max monster that we can kill and compute suffix minimums of costs

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

      Ah that's a lot lot smarter than what I did XD

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

      Can you please explain how that is fast enough in bit more detail

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

      I used a differentiate array storing for each cost c, the max monster H * D we can kill.

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

      Mine was finding all dividers of all numbers <=C (complexity C/1 + C/2 + .... + C/C,)and then doing dp for every k<=C finding the biggest possible h*d, if h is monster's health, d is damage it makes:

      if we did from 1 to k-1, for k: for each dividor x of k we calculate biggest answer with x = cost of 1 warrior. And take the maximum of it and answer to k-1.

      I did this because it is also enough to calculate dp

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

    DP
    We want to select our troops such that (health / my_damage) < (my_health / damage). (Here my_damage is sum of damages).
    Thus we can compute a dp array where dp[i] = max value of my_health * my_damage if there are i coins.
    You can view my submission here 150514511

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

      By the way, instead of implementing binary search yourself, you can use this:

      auto pos = lower_bound(it_start, it_end, needle) - it_start;

      (See my repaired submission: 150532032)

      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    There is a solution with parallel binary search. Essentially binary search on $$$C^\ast_j$$$ for each monster $$$j$$$, the minimum coins needed to kill them.

    If $$$i$$$ kills $$$j$$$ then it must be that $$$H_jD_j < h_i d_i \lfloor \frac{C}{c_i} \rfloor$$$. So you binary search in the range $$$[l,r]=[0,C]$$$. Then consider $$$mid$$$. You calculate $$$g=\max_i h_id_i \lfloor \frac{mid}{c_i} \rfloor$$$. Then you partition the monsters, those with $$$H_jD_j < g$$$ and those with $$$\geq g$$$. For those with $$$<g$$$, you recurse on them in interval $$$[l, mid]$$$ and those with $$$>g$$$ you recurse on them in interval $$$[mid, r]$$$. You stop when $$$l=r$$$. Total work would be $$$O(n\log C)$$$

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is D supposed to be solved with parallel binary search? I came up with an $$$O(n log C)$$$ in the last 10 minutes but couldn't implement it even if my life depended on it.

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

Guys, can someone clear this up for me? I got TLs in C problem on GNU C++20 (64), but the same code passed all testcases on GNU C++17...

150525251 — Accepted (GNU C++17)

150522050 — TL on 4'th test (GNU C++20 (64))

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell why my solution for problem C is giving TLE on test 5 ? My Solution

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

    Your code's time complexity is o(n^2),where as given string size has limit upto 10^5. So expectime time complexity becomes o(nlogn).That's why it gives you tle

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

I made two submissions for D and the first submission appears in the standings currently. What happens if the first one FSTs? will the second submission be used?

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve the 4th (D) question?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it +6 Vote: I do not like it

    This one you can apply similar technique to prime Sieve. presumably, d, h is the type you select and D, H is that of monster, if you select n unit then this is true n*d*h > D*H. it's easy to see that d,h individually doen't matter, what matter is d*h.

    C is at most 10^6, so what if we calculate the maximum d*h we can get for each cost from 1 to 10^6. Turns out this can be precompute similar to Sieve, and the complexity is cheap.

    From there just binary search for each monster to see what's the cheapest cost such that the max d*h you get at cost ith is larger than D*H of monster

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

      I think I get it.

      The precomputation of the sieve is fast because there can be only one useful unit (the one with the largest d*h) for each cost c and so you need at most C/1 + C/2 + C/3 + ... + C/C computations which is O(ClogC) (harmonic series). (the unit with c=1 (if there is one) loops C/1 times, the one with c=2 C/2 times and so on)

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

      Very sad is that I got the idea and confused somewhere in implementation during contest :')

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      Thank you for the explanation. I managed to implement the approach you described 150560762. Correct me if I am wrong, but the maxDH array (where the c'th slot stores the maximum d*h that c coins can get) that results from the prime sieve precomputation will have unvisited slots in some cases. So there is a need to do a pairwise max on this maxDH array from slot 2 to 1000000.

      Also, I had to store units information in units where the c'th slot of units stores the (d,h) all units with the cost per troop c.

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

        Yeah, it is necessary to do a 'prefix max' postprocessing of the maxDH array to make sure it is monotonic so that binary search can be applied.

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

D was based on?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

any hint for E?

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

    DP. The given condition can be rephrased as: for any two vertices X and Y other than 1, the weight of edge X -> Y should be no lesser than the weight of edge 1 -> X and 1 -> Y. We have N — 1 edges starting from vertex 1 which could form (N — 1) * (N — 2) / 2 groups. So, DP from weight 1 to K, dp[i][j] means, when we have assigned weights to j edges from vertex 1 and the max weight of them is i, how many choices we have. The transistion is:
    dp[i][j] = sum(dp[i — 1][l] * C(N — 1 — j, l — j) * power(K + 1 — i, j * (l — j) + (l — j — 1) * (l — j — 2) / 2) for all l < j which means, select l — j edges from N — 1 — j edges and assign them with weight i. combining them we have j * (l — j) + (l — j — 1) * (l — j — 2) / 2 groups of edges, weight of each group should be in [i, K]. The final answer is dp[K][N — 1]. https://mirror.codeforces.com/contest/1657/submission/150515462

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 4   Vote: I like it +4 Vote: I do not like it

      Maybe there is something wrong with your text explanation, but your code is absolutely right. I think text explanation should be fixed as below.

      dp[i][l] = sum(dp[i — 1][j] * C(N — 1 — j, l — j) * power(K + 1 — i, j * (l — j) + (l — j) * (l — j — 1) / 2) for all j < l which means, select l — j edges from N — 1 — j edges and assign them with weight i.

      We have chosen j points (called Vertex Set A) to connect to point 1 before and choose l — j points (called Vertex Set B) this time. Edges between points from A and points from B, as well as edges between two points inside B, should be no lesser than i. That is so called j * (l — j) + (l — j) * (l — j — 1) / 2).

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

      What do you mean by (N — 1) * (N — 2) / 2 groups? What are groups?

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

        Ah, I got it, sorry, but I did not get why did you do j * (l — j).

        → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone please explain me the logic of today's A particularly when the ans is 2. How can we prove it that if the ans is not 0 or 1 it must be 2?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can draw 2 circles, one centered at (0, 0), the other centered at (x, y) such that they intersect and do 2 jumps (0, 0) -> intersection -> (x, y).

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

    Travel parallel to x-axis first to reach the x coordinate and then travel parallel to y-axis or vice-versa to reach the final destination. This way it can be done in at max 2 moves

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

      Cool, I'm wondering if there were other people like me who did DP, after they weren't able to prove it after few minutes

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

    If we can't reach (x,y) in 1 or 2 move then we will first make move such that the x coordinate becomes equal to X coordinate of target(as y coordinate will be same so it will be valid) and in next move we will make y coordinate equal to Y coordinate of target (it will also valid as x coordinate will be same).So in minimum moves we can reach (x,y)

    → Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

It's crazy I used string hash on problem C.

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

    I almost decided to use Manacher's algorithm before I realized that the first time a character re-appears, it must be a palindrome.

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

      x2, but realized it wasn't needed seconds before actually using it

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

    Not worse than using DP in A. That's what i did :(

    → Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Thanks for having the 0 0 test case in the sample for problem A.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why did $$$O(nc)$$$ pass QD pretests... Doing $$$n = 30000$$$, $$$C = 1000000$$$, $$$c_i = 1$$$, $$$d_i = 1$$$, $$$h_i = 1$$$ easily fails $$$O(nc)$$$...

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

    How did you do O(nc)?

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

      It's technically $$$O(n(C/c))$$$... I guess that's why

      Although I admit that I'm just stupid that I didn't see this coming, this is (I think) one of the key elements to the solution, and letting that pass (with 1/10 runtime as well) is just... idk

      Slight modification to my solution that should pass
      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    why did you use O(nC) but ?and your o(nc) runs in 358 ms how is that possible

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

      that's what happypotato said, why did it pass pretests...

      anyway I believe we can expect numerous FSTs

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

        Education round does not have system test. Only hack.

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

          They will run all hacked tests again after the open hacking phase.

          → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is there a better way to solve A other than brute force and dp for all 50*50 square from 0,0? Doing a bfs + dp for all test cases for A seem overkill.

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

    0 , 0 -> 0, integer distance -> 1, other -> 2, because you can always go (0,0) -> (x, 0) -> (x, y)

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

      Wow, that's so simple. I'm retarded today.

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

    0，0 -- a, 0 -- a, b

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

    maximum answer can be 2 if a*a + b*b is not a perfect square because you can go from 0 to x and x,0 to x,y, else ans is 1 or if both x and y are 0 answer if 0

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

    Store all squares till 100^2 in a set. After that simply check if (x*x+y*y) is in the set. If it is in the set answer is 1 else answer is 2 .

    One edges case you'll have to handle is 0 0

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

    same on bfs(dp) + brute force :)

    i got AC on problem A when almost 7k people have passed A. my bad observation skill :(

    → Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Please Tell me randomization will pass F '~'

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

    Only insanity can help you pass F

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

      Actually, once you notice that you need to do some checks and then propagate those checks the only problem is the dependency cycles. and as you can notice it's impossible to make a test with a lot of dependencies without decreasing the number of strings.

      So trying some shuffles is good enough to pass this problem.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I went with a more naïve and straightforward approach for the dependencies, more of a constructive algorithm. Honestly I'm not familiar with how randomisation or shuffling works.

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

Memory limit exceeded on test 169 ^_^.......

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

    I think you have used an array of size N * 26 for 26 characters at each vertex of the tree. I did the same mistake and got MLE on test 169. If you notice, then there will be almost $$$O(\sum{|s_i|})$$$ values required out of N * 26 values which easily gets AC.

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

      Oh, I see. Yes, I did exactly the same mistake on problem F. Thank you, I will fix the mistake :)

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't believe I tried to solve a problem using hashing in a contest two times in a row!

→ Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why my D question got hacked in this round, can anyone help me https://mirror.codeforces.com/contest/1657/submission/150523841

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

    You are using too much memory. In v and pow vector you are using O(C*n) space in worst case.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Someone asked me in a private message how to solve 1657C - Bracket Sequence Deletion.

Don't write private messages, just ask below the contest announcement (or editorial if there is one). There is a greater chance someone will answer and more people can benefit from such an answer.

Despite that, here my attempt at a newbie guide for overthinking 1657C - Bracket Sequence Deletion:

Spoiler
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Applied the same approach, still my solution got hacked link. Can someone look at it? Thanks in Advance.

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

      I guess your s = s.substr(x); is the problem. For a string like ()()()()()[...] this results in a total runtime of $$$\mathcal{O}(n^2)$$$.

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

Educate by FST.

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Solving A B C can give you a rank of 700 as well as 6500

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any one help me out with D...Why is this giving Tle??? 150579927

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

    Think about the case where C=10^6 and n=10^5 with each ci=1 i.e. all the units have cost 1. In this case your Code complexity become $$$O(nC) $$$

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just curious, but I have finished this competition (this is my first ever CodeForces competition). However, apparently, as of 12:13 A.M. (UTC -7), 23 March 2023, I am still unrated. Is this supposed to be a problem? Thanks.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My CM dream come true :>.

Thanks BledDest, Neon, adedalic, awoo and vovuh.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem D is monster attacking all units with D[i] or his damage dividing between all units?

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

    The monster attack one unit.

    And when one of our units was killed, we lose

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

      thanks

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

      https://cfstress.com/status/2406

      can you explane me this?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        You know when we win??

        We win when d1 * h1 > d2 * h2 (d1, h1 is our unit; d2 , h2 is monster)

        When we buy x unit of one type, our d1 become d1 * x, our h1 doesn't change (because we lose when 1 unit die).

        In this test case:

        The monster's power is d2 * h2 = 5 * 6 = 30

        If we buy one unit of the second type we have 2 * 8 = 16 => we lost

        If we buy five units of the third type, we have 5 * 3 * 20 = 30 => draw

        But we have to win the monster, so we have to buy one unit of the first type, or six units of the third type.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, I used the thing that for each type of squad unit. The min number of troops hence the minimum cost required will be, 

troopCost * {floor(HjDj/hidi) + 1}

I calculated this for each type of troop and printed minimum amongst them. However this logic fails for some very high input (wrong answer 36373rd numbers differ — expected: '802914', found: '808376')

Can anyone help me out, What am I missing?

Here is submission, https://mirror.codeforces.com/contest/1657/submission/150576954

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

    May be because u use the float, u should use the ll

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

      Thank you so much, You really helped me. Yes You were right, Now Giving TLE for test 9 instead of WA on test 6. I will wait for editorial now.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E can be solved in $$$O(kn\log{n})$$$. This solution works in 0.5s for test 1000 1000 (or even about 0.3s if ran under 64 bit сompiler).

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

    Also, fun fact. In this comment the word "сompiler" has cyrillic с. It is because if I write the word "compiler" properly, mathjax fails to render the formula. If I misspell anything in this word, everything works fine.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the E time limit at 6 seconds? Is it to let n^2 k^2 solutions pass (they did)? It's an insanely long time especially when most solutions are < 1s.

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

    It's to let $$$O(n^2 k \log n)$$$ pass (my implementation of it is about 1.4s on the maximum test).

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

I've learned so many.

→ Reply
»
3 years 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).

→ Reply