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

Автор awoo, история, 5 месяцев назад, По-русски

Neapolis University Pafos

Привет, Codeforces!

Благодаря поддержке Neapolis University Pafos, продолжается серия образовательных раундов.

В 27.06.2024 17:35 (Московское время) состоится Educational Codeforces Round 167 (Rated for Div. 2).

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов, Максим Neon Мещеряков и Роман Roms Глазов. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

UPD: Разбор опубликован

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

»
5 месяцев назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Good!

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

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

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

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

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

fifth

»
5 месяцев назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

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

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

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

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

Does this contest have open hack ?

»
5 месяцев назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

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

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

Now it seems like I will become pupil in 3024

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

    quite a similar graph with me but keep practicing

    • »
      »
      »
      5 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

            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

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

      what about me

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

Thanks Neapolis University Pafos for educational round.

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

good luck and +delta for everyone

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

Thanks for all ur contribution!

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

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

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

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

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

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

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

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

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

        ya thats my point because of them ranking become influated

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

        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.

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

          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.

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

    shayan did this countless times :)))

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

    Disgusting. By the way, which YouTubers?

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

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

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

good luck

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

good luck

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

hoping to have fun!

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

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.

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

    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)

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

      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.

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

        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.

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

Another Educational, delicious. Good luck everyone

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

Speedforces

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

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

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

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.

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

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

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

    I had the same issue bye bye CM_

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

    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.

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

worst contest for me :( problems are good

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

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.me/contest/1989/submission/267692337

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

another contest of "testcaseforces"

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

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

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

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

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

    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

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

      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)

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

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

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

    i tried lcs but failed

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

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

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

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

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

    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

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

How to solve C?

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

    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
    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      overkill

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

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

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

    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.

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

      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.

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

    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.

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

      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

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

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

          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.

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

        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!

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

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

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

            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.

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

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

            your answer: 2 actual answer: 1

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

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

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

    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.

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

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

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

T.T sooooo nooooob took me so much time for C even though i got idea after some stupid dp try but always failing coz i wasnt thinking that i cant always take difference for granted. Got it at end but bcoz of that cant even read D or E

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

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

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

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.

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

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

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

Fuck problem A, worst A ever!

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

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

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

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

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

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

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

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

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

      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.

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

        no, it will tle

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

          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.

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

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

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

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

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

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

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

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

It was so simple. :(

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

    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.

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

How to solve D faster than O(mn)?

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

    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.me/contest/1989/submission/267753254

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

      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.

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

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

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

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

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

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

why does official standings show div1 participants ?

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

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

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

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

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

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.me/contest/1989/submission/267752822

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

    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.

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

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

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

        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.

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

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

          • »
            »
            »
            »
            »
            »
            5 месяцев назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            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

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

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

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

    Done :)

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

      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?

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

        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
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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.

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

I fuck up.

bye bye Specialist QQ

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

how to solve B ?

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

OK failed to solve B :(

bye bye CM (:_;)

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

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

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

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

How to solve 'C'?

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

    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

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

      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

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

        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?

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

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

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

    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.

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

    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

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

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

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

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

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

    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.

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

      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.me/contest/1989/submission/267733341

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

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.

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

    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

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

cryforces

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

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

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

    c is greedy not dp.

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

    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

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

Thank you Indians for making it Cheatforces and ruining cp

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

    bro indians are very honest, what are you saying

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

      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

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

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

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

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

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

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

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

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

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

Translation of problem E:

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

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

    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.

    • »
      »
      »
      5 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится
      Spoiler
      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится
        Proof of the last claim in the previous comment
        • »
          »
          »
          »
          »
          5 месяцев назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

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

          isnt this enough?

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

            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.

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

          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.

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

            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
            • »
              »
              »
              »
              »
              »
              »
              5 месяцев назад, # ^ |
                Проголосовать: нравится +10 Проголосовать: не нравится

              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.

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

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

  • »
    »
    5 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится +47 Проголосовать: не нравится

    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

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

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

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

        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.

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

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

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

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

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

D timelimit is hard

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

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

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

Really, it was too much hard for me :)

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

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

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

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

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

    abcd bfd The answer is 6.

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

    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

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

    hack data:

    1 bdf abcdef

    8(abdfcdef)

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

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

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

      Thanks!

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

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

problem D was great

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

Insane Div.2 !! Thanks for the authors

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

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

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

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

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

It was a massive contest !!

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

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

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

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

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

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;
}

}

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

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

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

Somebody please provide a proof for A please

  • »
    »
    5 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится
    Spoiler
    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

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

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

      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?

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

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

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

could somebody explain d please.

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

    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.

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

queue rip

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

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

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

C was easier than B.

»
5 месяцев назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

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

why was my submission skipped during contest ????

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

Can someone please explain why my priority queue submission gives tle in problem D? https://codeforces.me/contest/1989/submission/267760710

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

why the long queue it's not a div4 ?

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

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.

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

    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.

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

      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.

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

      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

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

can someone explain why this code gives tle for D?

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

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

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

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

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

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

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

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?

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

    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.

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

Editorial when??

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

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 ?

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

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

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

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.me/contest/1989/submission/267730392

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

Problem D test cases were too weak

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

rating changes when?

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

Does anyone know, has system testing already ended?

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

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

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

In Problem B:

a.length + b.length — longest common subsequence

for what particular test case it will fail

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

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

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

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.

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

NOTE: To respond to this, please go to https://codeforces.me/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.

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

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!

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

Why am I unrated for this content? My rating has not been updated, and the contests page tells me that it is unrated for me.

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

Hi guys! I attended in this contest but my rating isn't changed yet, why?

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

I can solve Div2A easily but in div2B... I am able to think and code brute solutions but not to think of the exact solution...can anyone suggest me the direction to reach ,the level where i can solve Div2Bs

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

    Try to upsolve after contest...and practice B from previous contests and 1000-1400 ratings problem also if you have enough solve in 800-900

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

    The "good" solution is kinda brutish. Due to the small constraints you can try to find the longest SUBSTRING of b that is a SUBSEQUENCE of a and then subtract its length becuase it will be the chars that you "reuse"

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

need help with problem D would really appreciate if someone took time and helped . Cant wrap my head around why one solution gets AC but others are TLE.

JAVA solution TLE : 267801346 (CLEAN CODE but with java template)

C++ TLE : 267867065 (CLEAN CODE)

AC solution 267867170 (CLEAN CODE)

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

    submitted C++ Tle Code just by adding Fast I/O and it got AC (267880403)

    Nvm, a DP approach is much more efficient see here 267864529

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

    Your C++ TLE solution doesn't have fast io.

    • »
      »
      »
      5 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      thanks for the reply Plot_Twist and Neko1i3 , understood the reason. I also checked DP approach , will try that too although I am not pretty sure why is my approach getting AC can you tell me the exact time complexity for the approach , idk why but my intuition is saying this can be hacked if there is a case where the sorted difference of metal used and melted back increases with 1 value per index and the cost of metal used decreases with index. For such a case wont inner loop run more than logN times ?

      Also I think moving back to C++ makes more sense. JAVA solution has fast I/O still got TLE. If you guys have any suggestions you're welcomed.

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

how to solve F?

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

A legit question. Is being able to solve a given problem by all the associated tagged methods or even more, a good practice? And if it is, where can I find the different ways of solutions? Thanks and regards

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

Hi this is the first contest I have participated in and I answered two problems correctly but it still shows unrated on my profile, does anyone know how to get a rating :(

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

    participate in a live contest, virtual participation doesn't affect rating

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

      I think it was, is it live as long as the hacking period hasn't ended yet? I participated yesterday when the judging system was still down.

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

My hacked code passes the testcases. The code gave tle during open hacking phase. But it's passing now after submitting again. In case of tle you do check multiple times about the time it takes.
So please do rejudge all solutions who got tle during open hacking phase(I mean all hacked tle solutions).
MikeMirzayanov, adedalic,BledDest,Neon, Roms, please look into once. I am sorry if I have mistakenly tagged wrong persons.
Thanks in advance:)

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

What is wrong in this code, Smithing Skill, Problem D ? https://codeforces.me/contest/1989/submission/267979244

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

I hvae not copied my solution from anywhere and what can i do if someone can think exactly like in the wat which i am thinking. The A problem was very easy so everyine can do that in same way the shortest one than it is wrong that you are blaming on me that i had done cheating. I just wanna prove that i am not guilty.Please have a look at that.

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

Hello, I recently got skipped in all the 3 questions of this round these much days after the contest. It is really frustrating, The ID from which my code matched have written the same logic as mine but the variable namings were changed. Suppose if there is an easy and short logic to solve a code and more than one user uses it, then why should there be a plag? and there are more accounts who used the same logic as mine but they didn't got any plag? Anyone here who knows some legitimate ways to get the rating back please reply.

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

I am writing in response to the notice regarding my solution 267752043 for problem 1989C coinciding with solutions da.3/267750467 and daksh942/267752043. I want to clarify that I neither shared my code with anyone nor engaged in any form of cheating. I also noticed that I was the first to use this specific logic.

Additionally, I observed that the other IDs solved only the third problem, skipping the first and second, which is unusual for a participant. As I was using an online compiler, it is possible he accessed my code from there, as I noticed he had many failed attempts for that solution. Furthermore, his solution had some extra variables which I had initially included but later removed as they were unnecessary.

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

Educational Codeforces Round lately very difficult ):

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

I am writing in response to my account himanshu_2173 being blocked stating my solution 267729657 for problem 1989B coinciding with solutions vrsth___007/267686783 and bud123/267690766. I want to clarify that I neither shared my code with anyone nor engaged in any form of cheating. I am a honest CP guy being part of the platform since 2yrs.

I used optimized code using LCS which is different from other submission's logic. Looking for an early reply.

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

sometimes your luck is not good

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

I'm scared.

Nope, we can't help you

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

If you want you can go alone, I can't leave my cats