awoo's blog

By awoo, history, 3 weeks ago, translation, In English

Neapolis University Pafos

Hello Codeforces!

The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos.

On Jun/27/2024 17:35 (Moscow time) Educational Codeforces Round 167 (Rated for Div. 2) will start.

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 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
  • +240
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Good!

»
3 weeks ago, # |
Rev. 2   Vote: I like it -73 Vote: I do not like it

Hello hope to reach CM in this round so write me a tip that you think it's useful on rounds :)

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

I hope to be able to solve 3 problems during the competition

»
3 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

Still confused how 1800-2400 rated guys make 3000-3500 problems but mk

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

    Look out for the author's history rating. You can come up with a hard problem despite your rating.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does this contest have open hack ?

»
3 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

I did not steal the code or cheat, why did you skip it?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Now it seems like I will become pupil in 3024

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

    quite a similar graph with me but keep practicing

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

      I already gone into 3rd year.....but still on newbie

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

        After my 3rd year, I became a Specialist from a Newbie. No need to worry.Push yourself hard.

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

          Some tips how you went from range of more than 8k ranks to 1k rank in last round in just 2-3 months?? Did you followed some course or what??

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

            Tbh, I didn't follow any guides for the summer grind. But, what I feel make me enhanced is:

            1. Daily solving of POTDs on GFG, Leetcode.

            2. Participated in almost 20-30 contests in the span of 1.5 months on several platforms such as CodeForces, CodeChef, Leetcode, etc.

            3. Very IMP, UPSOLVE.

            4. Learning very new concepts related to the problems I have encountered.

            The only suggestion I can give... "Be Consistent, Just DO IT."

            Edit: Try to keep up your motivation all the time. For me, It's watching the performance of my friends, fellow CPs, and legends. Don't compare to them.

            Comparing is the thief of Joy. - some random reel

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

      what about me

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck and +delta for everyone

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

Thanks for all ur contribution!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to achieve positive delta in this round at least considering all my recent contests

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

now days some cheap youtubers do live stream in between contest and give answer of the question i think codeforces should do something about it!!

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

    If someone is honest with himself, he doesn't give a shit to them.

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

      No, someone would give... if they won't get +ve delta bcz of them

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

        ya thats my point because of them ranking become influated

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

          shayan did this countless times already, so there's no point telling cf to shut him off.

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

            Shayan, do a live stream after the contest not during the contests.

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

        I know it's a demotivating fact that cheaters get better ranks than you. And the Codeforces team tries their best to find them. That is why the rating gets rolled back sometimes.

        The thing to be mentioned should be the YouTube channel of such streamers. Not just mentioning these facts. So that all such channels get banned.

        But, at the end of the day, these guys will still be there with some new idea to make others cheat.

        Question: Who motivates them to do this?

        It's some of us, who are lazy and greedy and want an easy way of having +delta with literally no benefit. Since they didn't improve themselves, what they did was just to make a fake image to impress someone.

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

          Well! You said the truth. I just pondered this because the channels are rapidly increasing, and viewership is increasing day by day. I have posted a post in CodeChef. I am hoping that someone would come up with a solution.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    shayan did this countless times :)))

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

      He meant during the contest, not after the contest.

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

      Shayan does this after the contest...not during the contest...learnt a lot from him

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

    Disgusting. By the way, which YouTubers?

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

my first contest :)

Edit: Can't give it now :(

Have to go to a teacher's house to meet him. Good luck to all others tho

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

good luck

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping to have fun!

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

It’s frustrating to see live streams sharing answers during contests. This undermines the spirit of fair competition. I hope Codeforces can address this issue to maintain the integrity of the contests.

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

    umm, the stream starts 5 minutes after the contest, so even if you submit using the answer, it won't count to the contest submissions (or something like that idk)

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

      many streams actually start during the contest, which can still impact the integrity of the competition. It’s crucial to address this issue to ensure a fair contest for everyone.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -9 Vote: I do not like it

        If you know some YT channels, it's better to mention them. So, the CF can take action against them. I think only raising the issue is not enough.

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

          Insha Allah. Next time i’ll do that.

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

            Please make sure NOT to mention them during the contest but after or before the contest.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Another Educational, delicious. Good luck everyone

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Bruh, people here hate to read the whole problem statement calmly. As stated by one of our time’s finest minds, zenigata23, “why should I read the documentation while I can watch 1 second of a YouTube video, then change window again and still haven’t understood anything”.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

today please consider looking at B submissions from 38th minute many will likely have cheated solutions as again got shared in a telegram group. awoo MikeMirzayanov, i will share the links soon for many of those cheated one which already i previously mentioned in older contests.

»
3 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

what's wrong with D without fast io it's not getting AC

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

    I had the same issue bye bye CM_

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

    Input and output are one of the slowest parts of any program. It is good if you add fast io as a template.

    In problem D, we have n, m <= 10 ^ 6, which are huge and require fast io. Another thing, is to use "\n" for the next line, don't use endl for it. Sine endl also flushes your output and is slower.

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

worst contest for me :( problems are good

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

Could someone hack my Problem B solution? The complexity is O(t*len(a)*len(b)) which is O(10^7) which should not pass but it does and I don't understand why. The system tests might be too weak (or I'm too stupid to understand why what I did works)

The idea of my code is, for each test case:

def solve() -> None:
    a: str = get_string()
    b: str = get_string()

    longest_b_in_a: int = 0
    for i in range(len(b)):
        longest_tmp: int = 0
        i_tmp: int = i
        j: int = 0
        while i_tmp < len(b) and j < len(a):
            if b[i_tmp] == a[j]:
                longest_tmp += 1
                i_tmp += 1
            j += 1
        longest_b_in_a = max(longest_b_in_a, longest_tmp)
    
    print(len(a) + len(b) - longest_b_in_a)

Complete source code: https://codeforces.com/contest/1989/submission/267692337

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    $$$10^7$$$ is supposed to be $$$0.1$$$ seconds as I estimate. Just think about $$$10^8$$$ ~ $$$1$$$ second.

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

      Oh, I thought 10^5 operations per second was the limit in Python. Damn. Good news I guess?

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

        Oh sorry, I didn't pay attention that you are using Python :v. So maybe I estimate it wrongly.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

another contest of "testcaseforces"

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

WtF prob A?? solved B in 15 min but couldn't do A bye bye Pupil :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell me whivh corner case Im missing in B my approach was lena+lenb-lcs . also tell me the correct approach

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

    even i thought the same untill i thought some thing like

    if a ="qwerty" b = "qwft"

    then ur ans will be 7 but actual answer 8

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

      did something like this def max_match(j): i=0 ji = j while i<len(a) and ji<len(b): if a[i]==b[ji]: ji+=1 i+=1 return ji-j for _ in range(II()): a= I() b= I() s = 0 n,m = len(a),len(b) for j in range(m): s = max(max_match(j),s)

      print(n+m-s)

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

      oh damn was upsolving this and thought exactly same. Thank you so much for the example.

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

    i tried lcs but failed

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

      Just brute force the sh*t out of the problem LOL(as the constraints were literally so small).

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

        when i want to be fancy Contest make me remember "now die noob "

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

    u cannot take LCS. think of this example string a = acdfe string b = bde

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

    tried this during contest but got wa

    Spoiler

    after contest removed dp[i][j+1] and subtacted ans insetad of dp[i+1][j+1] which got accepted

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

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

    Use binary search on the max minimum -- the choices are predetermined unless the pairs are {1, 1} or {-1, -1}, during binary search, decide which movie to assign it to

    Code
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      overkill

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

      That's way too complicated for the problem, see my submission (python) which follows roughly the same logic: all choices are predetermined except (1, 1) and (-1, -1). At last, we assign each of these a movie based on what maximizes the minimum among both movies, which can be done in O(1).

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

    Observation 1: If $$$a[i] \ne b[i]$$$, it's always optimal to take the review of the bigger of the two.

    Observation 2: If $$$a[i] = b[i]$$$, you can't greedily assign yet. However, since they are equal, you can apply this decision to either of them.

    Keep track of the 1 == 1, -1 == -1, and then distribute those plus and minuses after you've totaled what you were forced to take from each in Observation 1.

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

      I did something similar, I took the sum of both the movies in both cases and changed the sign of the review and tried to make both the sum equal. And printing the minimum of them. It gives WA, I can't find what wrong with my logic.

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

    The main objective is making the smaller rating movie's rating as bigger as possible.At first all the 1 0 and 0 1 pairs can be counted(If 1 0 then first movie gets +1 if 0 1 then second movie gets +1) because increasing rating of a particular movie will be always good as here both smaller and greater count rating movie get positive rating.We can avoid -1 0 and 0 -1 pairs as decreasing a movie rating is not efficient at all.Then we can come to the calculation of 1 1 pairs.If already counted first movie rating is smaller then we can consider this movie otherwise the second movie will be considered.For -1 -1 pair we can always consider the movie the rating of which is greater so that it doesn't reduce the value of smaller rating movie.

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

      Can you tell me an example test case where my code will fail. I was simply alloting the max out of a[i] and b[i], if max was -1 then allot it to the movie with higher rating and if max is 0 or 1 then allot it to the movie with lower rating. 267755402

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

        When the ratings are the same for maxi = -1 you allocate it to the first movie. This may not be optimal. For example:

        -1 0 
        -1 1
        

        you should pick movie 2 for both to get ratings 0,0. Instead your algorithm chooses the first movie for the first person and 1 for the second, yielding -1,1.

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

          But I ran your given test case and my output was 0 for it. When after choosing -1 , we get 1 as maxi in next then I assign that 1 to the movie with the lower rating which is movie 1 bcz it has rating -1 while movie 2 has rating 0.

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

        The problem is in some cases you're calculating -1 -1 pairs before calculating 1 0 pairs.As 1 0 pair is fixed rating increase chance for a particular movie,it should be calculated first then you can subtract always from the higher rating movie!

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

          Can you please tell me a test case where my code is giving wrong answer.

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

            For -1 -1 1 1 your code should give 1 but output should be 0 if you consider 2nd movie for 1st person and 2nd movie for 2nd person then 0 should be answer.

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

            4 1 -1 -1 -1 1 1 1 1

            your answer: 2 actual answer: 1

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

    you can distribute evenly when a[i]==b[i], otherwise maximize for rating a, b

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

    Consider each pair of $$$(a_i, b_i)$$$. If $$$a_i \ne b_i$$$, then it's always advantageous to take the larger one, because the smaller one is either $$$0$$$ or $$$-1$$$, which does not improve the final score if chosen. The pairs $$$(a_i, b_i) = (0, 0)$$$ are meaningless, so we're left with $$$x$$$ pairs of $$$(-1, -1)$$$ and $$$y$$$ pairs of $$$(1, 1)$$$, and we want to assign those pairs to the first group and the second group, which can be done greedily.

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

It is so hard! I want to cry....

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Desperately waiting for tutorial. waiting to see which test case didn't pass my sol for problem c. Argggghh!!!!!

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

    For example, this test:

    1
    2
    -1 0 
    1 1 
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro can we do dp to solve C? i mean my first thought was dp then it got so confusing how to do transitions. Any help is appreciated

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

        Maybe it's possible (it's certainly possible in $$$O(n^2)$$$) but I wouldn't think too much about it. Also read this — if the transitions become confusing, don't try to force DP on it.

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

    Same for D.

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

The contest was the best ever, but the conditions were the worst ever for me. Started 15 minutes late and got the most wrong submissions in my cf history!!! I didn't even have time to read D. I just hope don't be cyan.

»
3 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

I thought B was a.length() + b.length() — lcs(a, b) :skull:

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Fuck problem A, worst A ever!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what's wrong in my solution in problem B? please someone help. my solution

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

C was easier compared to a standard div 2 but any hints for D???

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

    Its always optimal to melt a tool after forging (gives x experience and bi additional units of that metal).

    Now, if we forge ith tool k times using metal j, we would use — ai+(ai-bi)+(ai-bi)...-bi = k(ai-bi) units of metal j

    (the last minus comes when we melt after last forging) __

    So for each metal, we can start forging in the increasing order of (ai-bi). Still figuring out how to bring this down from O(n*m) :(

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

      dp the first 1e6 values, if greater then apply min(a-b) repeatedly in o(1)

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

      I read problem D in the last minute and thought of the same thing but thought of a heap approach, like we can have a min heap for ai-bi and another max heap for metal nodes, using this the minimum ai-bi will always match with maximum metal nodes. Will this approach work? I still haven't implemented it.

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

        no, it will tle

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

          But why? As n,m <= 10^6, so the TC for heaps will be nlogn which i guess should come under the time constraints, i am new to CP so I don't know what the problem with this might be.

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

      maniac_0112 can you pls tell how do you find how many weapons(i) can we make with metal(j) in O(1) so that your time complexity turns out to be O(n*m).

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

        In order to forge k weapons,

        we would need -> k*a-(k-1)*b = a + (k-1)*(a-b).

        This should be less than cj (ingots of metal j). a + (k-1)*(a-b)<=cj So k <= 1 + (cj-a)/(a-b).

        We can simply take the highest k = 1 + floor((cj-a)/(a-b)).

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

    I explained my solution in this comment https://codeforces.com/blog/entry/130882?#comment-1164494

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I literally complicated things too much on C by thinking of DP.

It was so simple. :(

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

    its okay. In ranking you will see many oranges and reds also got wa on dp submission and all of them had to re-submit a non-dp solution. Very deceptive problem.

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

How to solve D faster than O(mn)?

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

    You can make a dp vector of size 1e6+100 which represents the number of experience if you have i ingots. For c <=1e6 you can print the answer, otherwise you can make it smaller than 1e6 by forging and melting as much as possible with the pair that has the smallest a-b and smallest a among them. My solution: https://codeforces.com/contest/1989/submission/267753254

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

      woaah that's a cool solution, thanks for sharing it. I was either thinking of either calculating for all 1e9 (which would TLE and MLE, ofc) or calculating for each metal by checking with each weapon all the way till it exhausts. Never thought of this holy middle way.

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

      I still don't understand it, could you provide a detailed explanation

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

        Firstly, if there are pairs with the same a-b, you can leave 1 pair among them with the smallest a. Then I created vector ans to make dp. The transition is: ans[i]=ans[i-v[l].first]+2; where v[l].first is a-b and l is index that i is bigger than v[l].a. You need to add 2 because you gain 2 points of experience for forging and melting the weapons.

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

          so how could you get the v[I] which suits the requirement to do the transition?binary search?

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

why does official standings show div1 participants ?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone else read B as subsequence of string a and string b? Got 3 WAs and wasted 20 min because I missed that lol

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

    Happened with me... I spent 40 minutes on B with 35 thinking about lcs due to this..Realised it very late that insertions in the resulting string could only be made at ends or the beginning so we had to check the max length of substring of b present in a as a subsequence..

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone hack my Problem D solution? The complexity is O(n*10^6) which should not pass but it does and I don't understand why. The system tests might be too weak (or I'm too stupid to understand why what I did works)

The idea of my code is: - Handle each c that is > 10^6 to bring it under 10^6 in O(m) - Handle them again but now that they are all under 10^6 I can use a direct access array to do memorisation. But each call to know how to bring a given int to below min(a) is O(n) so in the worst case it should be O(n*10^6)

Complete source code: https://codeforces.com/contest/1989/submission/267752822

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

    Bringing $$$c$$$ to less than or equal to $$$10^6$$$ only takes us to choose on type of weapon with min(a[i] — b[i]), it will be O(1) for each $$$c_i$$$. Maybe the tests are weak here, as I saw that you choose it by iteration.

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

      Exactly I chose by iteration (and i don't really know how to choose the correct one without iteration) which is why I was hackable. Do you have any hint how I could choose without iteration? I thought about doing binary search but I sorted according to a[i] — b[i] and if binary search was done it would have to be according to a sorted array on a[i]?

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

        That's exactly what it is. Find the position $$$i$$$ such that $$$a_i$$$ is less than or equal to the current $$$c_j$$$ and $$$a_i - b_i$$$ is minimum, which can be done through binary search.

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

          So you would need to sort on a[i]. How would you find the minimum a[i] — b[i] if it's not sorted on it? That's what confuses me :/

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

            That's implementation issue. Create a vector of pairs, where each pair contains {$$$a_i - b_i, a_i$$$}. Sort this vector and that's what you need.

            My implementation: 267751542

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

    It is correct, i did the same thing . why do you thing worst case is n*1e6 ?

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

    Done :)

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

      Thank youuuu so much, I really appreciate it. Can you walk through how you made it? I've never hacked anyone neither did I ever hack myself so I'd like to know (both practically and how to come up with the worst case)

      EDIT: also how can I see the input of your hack?

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

        I tried to ensure you will iterate n times for every c[i], so I just generate a bunch of large b[i] and small c[i], so every c[i] will be judged n times to determine that the answer for this c[i] is 0;

        hacker
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone else thought in A that we had to collect all coins in one go?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The fact that the sample case for B is enough for us to think about LCS and got WA on test 2, interesting.

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

I have a feeling that a lot of cheaters are watching ind vs eng. Hence the less number of people who solved c and d.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I fuck up.

bye bye Specialist QQ

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

OK failed to solve B :(

bye bye CM (:_;)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with why this logic is wrong for problem C:

https://codeforces.com/contest/1989/submission/267749013

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 'C'?

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

    Greedy works well. If one of $$$a_i$$$ or $$$b_i$$$ is $$$1$$$, and the other is less than or equal to $$$0$$$, then just take $$$1$$$. For example $$$a_i = 1$$$ and $$$b_i = 0$$$ or $$$-1$$$, then we take $$$a_i$$$ because if we take $$$b_i$$$, the answer will be worse. Now we need to decide for the rest of the cases, which is $$$a_i$$$ and $$$b_i$$$ is both $$$1$$$ and $$$-1$$$. Then as we want to maximize the minimum between two types of movie, we take $$$1$$$ at the lower rated type and take $$$-1$$$ at the higher rated type.

    Submission: 267713316

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

      So if both are -1 and -1 the max(movie_a, movie_b) will take the bullet i.e (-=1) and if both are 1 and 1 the min(movie_a, movie_b) will take the cake i.e (+=1) keeping this in mind i was trying but failed, what is wrong with my approach/code : 267733477

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

        You only said about the case when $$$a_i$$$ and $$$b_i$$$ are both $$$1$$$ or $$$-1$$$, but what about the case when $$$a_i$$$ and $$$b_i$$$ are not the same?

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

          I'm sorry i don't even understood the problem correctly, Thnx anyway, i'll have to upsolve this now.

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

    You can observe that in any case, instead of $$$( A[i] == B[i] )$$$, it will be known which one will be chosen, which is the option of making one of the scores increase or at least stay constant. So, you can loop over them, then calculate the score of each initially, and discard the cases of equality for now.

    Then consider the cases of equality in the following way:

    • If both $$$( A[i] )$$$ and $$$( B[i] )$$$ equal $$$1$$$, then give the point to the film which has a lower score (which was computed initially).
    • If both $$$( A[i] )$$$ and $$$( B[i] )$$$ equal $$$-1$$$, then give the point to the film that has higher points.
    • Finally, if $$$( A[i] )$$$ and $$$( B[i] )$$$ are both zero, nothing will change.

    This approach focuses on making both scores as maximum as possible and minimizing the difference simultaneously.

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

    Waittt, Wait, Wait "and for every person, you can choose which movie they will review" doesn't this mean movie_a += b[i] is also possible?

    or i just misunderstood the question? if i did, then, I'll have to learn 'English' first LOL

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

      for every $$$1 <= i <= n$$$, you can either choose to add $$$A[i]$$$ to MovieA or $$$B[i]$$$ to MovieB.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve E? I tried many dp approaches but none worked

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

    I used the method of generating functions to solve this problem. If the first block of identical elements in $$$a$$$ has length $$$r$$$ and the last length $$$s$$$, then $$$b$$$ will be $$$r, r-1, \dots, 1, c_1, \dots, c_q, 1, 2, \dots, s$$$, where $$$r\ge 1$$$, $$$s\ge 1$$$, $$$q\ge k-2$$$ and the $$$c_i$$$s correspond to blocks of identical elements in $$$a$$$, so they're selected from the set $$$S$$$ which contains the block $$$1$$$, the block $$$1, 1$$$, the block $$$1, 2, 1$$$, and so on. You can replace the block $$$1, 1$$$ with two blocks $$$1$$$ without changing $$$b$$$ or decreasing $$$q$$$, so you can remove the block $$$1, 1$$$ from $$$S$$$. Then there is a bijection between different $$$b$$$s and their block structures, so the answer will be (modulo $$$998244353$$$) the coefficient of $$$x^n$$$ in

    $$$ (x + x^2 + x^3 + \cdots)^2 \sum_{q \ge k - 2} (x + x^3 + x^4 + \cdots)^q = (x / (1 - x))^2 f^{k - 2} / (1 - f),$$$

    where $$$f=x + x^3 / (1 - x) $$$. After a little algebra, this gives that the answer is (modulo $$$998244353$$$) the coefficient of $$$x^n$$$ in

    $$$ (x^2 (x - x^2 + x^3)^{k - 2}) / ((1 - x)^{k - 1} (1 - 2 x + x^2 - x^3)).$$$

    Since $$$k$$$ is small, you can expand the numerator and denominator of this rational function and then work out the coefficients of $$$x^i$$$ in the reciprocal of the denominator one at a time, in the order of increasing $$$i$$$. After that, you just have to add a few terms together to compute the answer.

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

      There exists a simple $$$O(NK)$$$ solution.

      Imagine your original array as contiguous intervals of same values. Let's imagine the corresponding $$$b$$$ array. Let the first interval (which begins at the start of the $$$a$$$ array) be of length $$$l_1$$$, and the closing interval of length $$$l_2$$$. Now let's imagine that we are given only the $$$b$$$ array, which information about array $$$a$$$ can you infer? You will know the lengths $$$l_1$$$ and $$$l_2$$$, and you can know the lengths of contiguous intervals between them except for one case — you cannot discern a segment of length $$$2$$$ from two segments of length $$$1$$$.

      As stated in previous comment, it is not useful to get one block of length $$$2$$$, so just discount that case. Now the problem is reformulated as "count number of ways to cover the array with segments, so that:

      1. There are at least $$$k$$$ segments.
      2. There cannot be segments of length $$$2$$$ except the first and the last segment.

      Now it is a simple dp.

      Code: https://codeforces.com/contest/1989/submission/267733341

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem F is this right?:

Create an empty digraph with a unique node corresponding to every row, column.

For query $$$(x, y, c)$$$: If $$$c$$$ is red, add edge (node of column y, node of row x). Otherwise, add edge (node of row x, node of column y).

After every query, the answer is the sum of the squares of sizes of all SCCs except singletons.

Maintaining this info can be done using this radewoosh blog.

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

    This is correct.

    I am so dissapointed that I solved it just three minutes after the contest has ended, but that's part of the game...

    I used this implementation to maintain SCCs.

    The changes we have to make are:

    1. Parsing the graph differently, as you mentioned.

    2. Adding to the DSU an array that stores the size of each connected component, and updating it when merging two connected components in the DSU.

    Here is my implementation: Implementation

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

cryforces

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C by dp? I tried to calculate the answer recursively but failed to memoize it :(

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

    c is greedy not dp.

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

    i also start thinking about dp but simple greedy as if (1,0) =>choose 1,similar for (1,-1)=>choose 1 , if(0,-1)=>choose 0 but the cases left is just (1,1) and (-1,-1) then after that do as low and high . you can check submission 267710687

»
3 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

Thank you Indians for making it Cheatforces and ruining cp

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    bro indians are very honest, what are you saying

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

      i can see their honesty on telegram where 1k+ indians view the solution during contest...even the group/channel owners are Indians..and they are ruining literally every coding platform ...be it leetcode ,atcoder or codeforces ..just ruining the cp environment

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

        I am an Indian but I still very much agree with you :(

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

    Well I mean I'm not even Indian but that's a tad racist and there is no money or whatever on the line, it's not gonna change your life if you ranked $$$i+70$$$ instead of $$$i$$$

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

    There's always somebody bad on either side, lol.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this a Div 1+2 contest? Because the official ranklist is showing Div 1 members too!

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

    In educational rounds div1 memebers without being counted as participants

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

      Yeah, so they shouldn't be in the official preliminary standing right?

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

        technically it is a round for everyone, but it is only rated for div 2.

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

In B, we only need brute force insert A to B and delete B's char existed in A, right ?

»
3 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

Translation of problem E:

There are how many binary arrays of length n-1 with k-1 or more ones without "101" as subarray?

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

    But how do you prove that for each such binary array there exists such $$$b$$$-array?

    UPD: Yep, that works. Wow! Still wish for a proof though.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +16 Vote: I do not like it
      Spoiler
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +13 Vote: I do not like it
        Proof of the last claim in the previous comment
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Segments of size > 2 are obviously unique by the maximum number and its frequency.

          isnt this enough?

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

            I used this proof for the model approach (which is almost the same as the translation from your comment), but for some reason I thought that it's not easy to apply for the binary string version of the problem.

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

          A detailed explanation of 267686019 of tourist for E would be much welcome. Thank you!

          I consider it very educationally worthwhile to understand that code since 1) I've tried a fair bit without success 2) it was done in 4m in comparison to 10m for jiangly and over 15m for a significant portion of the top contestants.

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

            This is very similar to the model solution to this problem. It will be described in the official editorial for the contest, but I can give an "early access" version of it:

            Spoiler
            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              Thank you! And for those who are interested, 267865673 is my modification such that one does a recurrence from $$$k$$$ to $$$k$$$ (in addition to also $$$k$$$ to $$$k-1$$$). In contrast, tourist went about it more indirectly via a recurrence from $$$0$$$ to $$$0$$$ (which actually made it harder to figure out what he was doing, though it is in some ways more simple).

              I feel a bit bad about taking up more of your time with such a long answer. Before I posted that comment regarding the submission of tourist, I had understood the submission of neal as well as the idea behind solution.

              In contrast to

              Trivial to code a dp for this

              as Dominater069 commented,

              I felt like the idea was rather straightforward and the hard part was actually coding the dp, which involves a clever packaging and usage of a prefix sum. It was the $$$0$$$ to $$$0$$$ recurrence trick that eluded me for quite a while, and once I believed I had "deciphered" that, I set about to AC it in the aforementioned different yet similar way to confirm; only after the AC, did I see your answer. 😀

              Extremely high quality problem that presumably you composed, and I am happy to give my feedback on it.

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

                This hasn't actually taken a long time for me because, well, I just copypasted it from my editorial drafts

  • »
    »
    3 weeks ago, # ^ |
    Rev. 4   Vote: I like it +47 Vote: I do not like it

    My translation : how many ways are there to split a segment of size n into >= k segments such that each segment (except the first and last which have no constraints on them) is not of size 2

    Trivial to code a dp for this

    Nvm i just notice, yours is the exact same too

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

      Hi, can you explain the logic for your translation as well? Thanks

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

        every segment of equal elements is uniquely identified by being like [1, 2, 3, ...., 3, 2, 1] (first and last are [1, 2, 3, ....] and [..., 3, 2, 1])

        the only exception is a segment of length 2 [1, 1] which can be split into [1] + [1]. Segments of size > 2 are obviously unique by the maximum number and its frequency.

        Thus, all reachable b-arrays are exactly like i stated, >= k segments constraint due to each number occuring atleast once.

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

          Thanks

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          if (j == k){
                      dp[i][j] += psum[i - 1][j];
                      if (i >= 2 && i != n) dp[i][j] -= dp[i - 2][j];
               }

          why did take this transition dp[i][j] only for j == k? Thanks;

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

      I came out with the same translation, but i suck at dp and didnt manage to solve it:))

»
3 weeks ago, # |
Rev. 4   Vote: I like it +14 Vote: I do not like it

Interesting Problems! Without too many complex algorithms,using some basic skills to solve them is quite cool.

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

D timelimit is hard

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

problem d accepted 2 min before the contest ends, hoping to reach expert this time

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really, it was too much hard for me :)

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

give Hints for A my thoughts on A
(Correct me ) - 1. always move along the diagonal and abs(y) should be atleast 2

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, why does len(a) + len(b) — lcs(a,b) subsequence not work?

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

    abcd bfd The answer is 6.

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

    no you cannot use subsequence concept of choosing in s

    counter test for your logic

    s="abc" and t="adbec"

    according to your logic answer should be =3+5 — 3=5(wrong)

    it should be 7

    you can look at my submission for better clarity

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

    hack data:

    1 bdf abcdef

    8(abdfcdef)

    The correct sol is to find the longest substring of B in the subsequence of A

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

      "Longest substring of B in subsequence of A" totally explained it to me.

      Thanks!

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

        If that was sarcasm, that actually does explain it exactly. You need to find the longest substring of B that is also a subsequence of A. The answer would then be size(a)+(size(b)- this length). What you're finding instead is the longest subsequence of B that is also a subsequence of A.

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

problem D was great

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Insane Div.2 !! Thanks for the authors

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

The problems used only basic techniques and were great!... Except for that fact that I bricked on each and every one of them T_T

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem B (Substring and Subsequence) Video Editorial : Link : --Click_HERE

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

It was a massive contest !!

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

now way, 2 silly wrong submissions for D costed me CM

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please have a look at my code for problem D, it's giving wa on test 11.
submission

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i made a submission with code but it was wrong can anyone tell an eg where this code is failing

include<bits/stdc++.h>

using namespace std; int main(){ int t; cin>>t; while(t--){ string a,b; cin>>a>>b; int x = 0; vector m(26); for(int i=0;i<a.size();i++){ if(a[i]>='a' && a[i]<='z'){ m[a[i]-'a'] += 1; x++; } }

int ct = 0;
    for(int i = 0;i<b.size();i++){
        if(b[i]>='a' && b[i]<='z'){
            m[b[i]-'a']--;
        }
    }
    for(int i = 0;i<26;i++){
        if(m[i]<0){
            ct += abs(m[i]);
        }
    }
    cout<<ct+x<<endl;
}

}

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

May I know where and when the solution will be posted after the contest?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Somebody please provide a proof for A please

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it
    Spoiler
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      when moving up each second we will have 2 increment in y so. total y/2 + y%2 seconds required right?

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Please see the D solution I think it should not give tle on test case 9 for n*logn solution

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

    I would say putting $$$10^6$$$ element in a map would be too much, also there exist linear solution.

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

      ya but I submitted it at 4 seconds before the contest so I couldn't optimize it

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

      I have successfully tried 1e6 elements in a map before though. Can't exactly seem to recall the question but why exactly does it fail in this case? Codeforces judge performs about 5e7 operations per second right?

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

        That's a rough estimation for checking whether certain complexity $$$O(f(n))$$$ would probably pass or not, but in reality, constant factor need to be considered and std::map has huge constant factor. Like, $$$O(nlgn)$$$ by fenwick tree would probably pass in 1 sec but $$$O(nlgn)$$$ by std::map won't given $$$n = 10^6$$$.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

could somebody explain d please.

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

    Yeah it is optimal to take A[i] minimum for a particular difference A[i]-B[i] as c[i] should be greater than A[i] and make C[i] less than A[i] with diff=A[i]-B[i]; It can be done as (C[i]-A[i])/diff<steps do steps++ as we want C[i]<A[i] and then keep the ans+=2*steps; as both melting and forging should take place make a thing such that {diff,A[i]} should be monotonically decreasing with A[i] and increasing with B[i] and remove other pairs in between them so update the dp[new_c[i]]+=dp[c[i]] as dp[c[i]] is nothing but count this can be done by two pointers simply.

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

queue rip

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder wtf a 3000+ rated problem is doing in a Div2 round.

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

C was easier than B.

»
3 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

Actually really liked the C on this one. (Not just because I was able to solve it)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why was my submission skipped during contest ????

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

Could the open hacking phase be extended if the queue issue won't be resolved shortly? We've already lost more than 5 hours of the phase and still have no idea when it will come back. There are many people who were trying to hack and they can't even see if their input is valid or not. I think at least a few more hours to hack should be given after the queue becomes normal again.

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

    Now we only have less than an hour left...

    I hope it doesn't end up with no response and just starting system test. Open hacking is an official phase that can affect official results, so it really shouldn't just be "whatever, nobody cares about hacks and rather wants earlier rating updates" and be wasted like this. We were announced that we will be given 12 hours, so everyone deserves to have that time as a whole and not just 2 hours.

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

      Yeah the testcases for D seem to pretty weak as well and there are not many hacks. I am not sure if the hacking phase will be extended though.

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

      I submitted a hack like 10 hours ago, and lastly when I checked after seeing your message it was still in queue, and now system test running

      this is really annoying that coordinaters dont care about it :/ starting the system test after not giving a reliable chance of hacking to participants. 2 hours of hacking, 10 hours of queue

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

can someone explain why this code gives tle for D?

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

    I guess sort by a list key is slow in python. Also min is slow.

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

      the bucket sort is kinda necessary for the soluion and i don't know how else i can do it

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

    Using tuples as comparison key is slow. Packing the key into a single integer will usually make the code run noticeably faster. For example, try to replace (a[x],-b[x]) with (a[x] << 32) | (10 ** 6 - b[x]) (it's easy to see this conversion keeps the sorting order).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem B why finding Longest Common Subsequence(len1) and Longest Common Substring(len2) and calculating answer = min((n1+n2-len1), (n1+n2-len2)) does not work?

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

    String a needs to be a substring (so it can't be broken apart) and b needs to be a subsequence so you need to just find 1 longest subsequence and that is the longest subsequence of b inside a. Once you have it's lengh, the answer is simply len(a) + len(b) minus the length of the subsequence.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorial when??

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved the problem A , and it got accepted , but now its showing that I haven't attempted it at all , its not showing up in my submissions as well. Can someone help ?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain why my logic for B is wrong. I am getting wrong answer in test case 578 in test 2. here is my submission-267713310

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

    consider the test case

    1
    bab
    ab
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks, but i think doing abs(v[i+1]-v[i])==1 should fix the problem

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

        it would not, consider the test case

        1
        bcabc
        abc
        
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why my problem D solution failed system tests at test 14? I used DP over the starting number of ingots, sorted a[i] while "keeping b[i] aligned with it" (using pairs) and used prefix-min of a[i]-b[i] to efficiently get the best offer, and binary search to find the biggest one I can craft.

https://codeforces.com/contest/1989/submission/267730392

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D test cases were too weak

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

rating changes when?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know, has system testing already ended?

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

My submissions for the problem D are in queue for a long time now. Does anyone know what's happening

267829615

267824112

267822352

Update: issue got solved, got verdict wrong answer tho :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem B:

a.length + b.length — longest common subsequence

for what particular test case it will fail

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why this contest is showing unrated even i have rating less than 2100

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

    Because it always takes a bit to update ratings even after system tests, your rating should probably be updated by today's evening

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

That moment when you only need one more simple "idx++" line to get AC, but somehow miss it for two hours. I really didn't deserve specialist rank damn.

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

NOTE: To respond to this, please go to https://codeforces.com/blog/entry/130882?#comment-1164822, an identical comment located near other comments regarding problem E.


A detailed explanation of 267686019 of tourist for E would be much welcome. Thank you!

I consider it very educationally worthwhile to understand that code since 1) I've tried a fair bit without success 2) it was done in 4m in comparison to 10m for jiangly and over 15m for a significant portion of the top contestants.

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

Can someone explain why only top 500 got their rating changes?

And this contest is marked as unrated for me even i'm under 2100.

Is this just a bug or it haven't been totally updated?

Thanks in advance!

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

    Not completely updated. Happened in last contest too with second half of the ranklist

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

      Do you recall how long it took to update last time?