Vladosiya's blog

By Vladosiya, history, 8 months ago, translation, In English

Hello! Codeforces Round #797 (Div. 3) will start at Jun/07/2022 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

take part in at least five rated rounds (and solve at least one problem in each of them), do not have a point of 1900 or higher in the rating. Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University teams: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, DmitriyOwlet, me Vladosiya.

Also many thanks to Kirill22 , Allvik06 , Fortin , Artem_Sukharev , vsinitsynav , yorky , oversolver , majorro , ilya_totl , Undying , olya.masaeva , Kniaz , Golovanov399 , farmerboy , Absyarka , Kavaliro , neeraj_joshi for testing the contest and valuable feedback.

Good luck!

UPD:Editorial

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

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

as a tester, I want to say that I've waited for invite so long... and finally got it!

also, expect interesting problems :)

»
8 months ago, # |
  Vote: I like it -6 Vote: I do not like it

All the best everyone hope everyone gets a positive delta

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

hope a good delta positive this time.

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

As a contestant, I want to say good luck to all contestants

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

Finally Dream come true!! . Now i can finally give div3 as an unrated participant !!. It took 1 year for this moment.

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

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

Well, maybe this announcement is a bit late.

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

div 3 and div 4 are good contests for newbie participants

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

六国は、軍が破壊されていない賄賂秦賄賂秦と破壊の方法の電力損失で良い戦いの欠点はまた、六国は、賄賂秦のはい、強い支持の損失を買収するために互いの速度を失ったと言った賄賂秦の欠点も攻撃して外に取ることは秦が得ると勝利と得るより邑大実際に百倍の死と敗北と死実際にまた百倍の偉大な悩みの領主は最初の祖父 嵐 霜露カット考えるには戦争ではありません初代の祖父は小さな土地を持つために茨を切り、その子孫はそれを草の浪費と見て、今日は5都市、明日は10都市を切り、秦軍が来る間、安心して寝て四領を眺めることができたのです燕・趙の王は、秦に賄賂を贈らず、自分の国を守る遠大な戦略を持っていたので、燕は小国ではあったが、後に滅亡した三国志が秦に付かず、刺客もいないのであれば、勝敗の数、生存の理由も秦に比べれば簡単には測れないかもしれません世界から六国崩しの話を取り上げると、また六国の下になる

»
8 months ago, # |
  Vote: I like it -32 Vote: I do not like it

All the best everyone . Hope all of you get a positive delta

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

    why so downvotes "."?

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

      Dont know . Maybe they didn't like my well wish. Anyways my bad.

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

        All those downvotes are because of you're wishing for positive delta (Covid variant) :)

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

          Ooh . Should I've written plus rating then it would have been the upvotes. Correct?

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

            dont mind them. People will downvote you for the most random reasons in this site. I guess they're trolls/negative people

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

First unrated div 3. Yay:)

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

    disadvantages of being expert.That's the reason i am still specialist.

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

Div3 round yayy !! Is the round really meant for Div3 when we can see no tester who is <1600 ...

Also what is the point in including so many high rated testers and not a single <1600 tester ?

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

    Obviously to make an unbalanced round :D (no offence)

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

Hope good practice and new colors for all rated participants

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

!Unrated for me too :D

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

i am always ready for the div3 with my cup of tea

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

I didn't participate in 5 rated rounds and my rating is below 1600 can I participate??

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

    Yes, you can. If I am correct the round will be rated for you, only you won't appear in the official standings table.

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

    Yes

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

I wish that every Chinese student can get good grades in Gaokao!

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

how to do E?

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

    Try to think about case : how does answer change if we pick such $$$(i,j)$$$ that $$$(A_i$$$ $$$mod$$$ $$$k)$$$ $$$+$$$ $$$(A_j$$$ $$$mod$$$ $$$k)$$$ $$$>=k$$$ .

    For example : $$$k=3$$$

    $$$A:{1,2,4,5}$$$

    matching $$$(1,5),(2,4)$$$ gives answer $$$4$$$ and matching $$$(1,4),(2,5)$$$ gives $$$3$$$

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

    You can see my solution O(N) : 159865328

    Three steps :

    1. All those with value a[i]/k will be included and reduced to a[i]%k

    2. Pair all the a[i]%k first half (< k/2) to other half (>k/2) | so that sum>=k

    3. All those (>k/2) can form pair themselves which are left after pairing first half.

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

    for each value a[i], a[i]/k will always be there in the total answer. So, we can add a[i]/k for all i. Then, in another array we store a[i]%k. Now, the maximum sum of two of the remainders of a[i] and k is 2k-2. And (2k-2)/k is 1. So we have to find the number of pairs that we can form (from the remainders) such that their sum is greater than or equal to k. We can do this using greedy + two pointers. My solution — https://codeforces.com/contest/1690/submission/159852372

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

I think the authors are very much interested in permutation graph this is 4th instance in last one month I find same kind of question F

https://atcoder.jp/contests/abc247/tasks/abc247_f

https://codeforces.com/contest/1678/problem/E

https://codeforces.com/contest/1670/problem/C

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

    If you have some more basic questions of this concept please do share. I didn't knew about this earlier, that such a topic exists. Thanks.

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

How do you solve F and G?

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

How to solve the edge case for F while solving for LCM of each cycle?

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

    What edge case?

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

    Yeah, I got all the cycles and tried to get all the number of moves for each cycle such that all the letters get matched to the correct locations. But I had no idea how to go on from there without brute force.

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

      I think brute force works? Constraints are low enough that for each cycle you can check how many rotations are needed to return this cycle to it's original position (and you can take the LCM of all this)

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

        what happens if there are multiple possible rotations needed to return the cycle to its original position?

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

          we take the first time the cycle returns to its original position as there is no needs to go further

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

          All future rotations are multiples of the first.

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

            Could you please clarify? Edit: Nevermind, I've understood. Thanks

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

              let's say you have string "abab".The first time this string comes to it's original state after rotations is after 2 rotations.

              rotation 1 : baba
              
              rotation 2 : abab

              So from here you can figure out that this string repeats itself after every 2 rotation. Now to get the answer you simply need to find this minimum rotation required for each cycle.

              let's say you have got cycle of "aba", "bba", "abab", "aaa" and each of them repeats itself after 3, 3, 2, 1 rotations respectively. So, the answer for this case would be lcm(3, 3, 2, 1) = 6

              you can checkout my implementation

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

              ^ Ashish mostly covered it. Essentially if it takes k operations to return the string to it's original position, then it will take another k operations to do the same thing again.

              Therefore the string is in its original orientation at time k, 2k, 3k, etc. You only care about k, because all other rotations are just multiples of k.

              You then need to find some number that is a multiple of all other original orientations, and therefore we arrive at our lcm idea

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

    For individual cycle you need to find number of operations after which string will repeat with brute force and then take LCM.

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

    try to check for pattern, like if cycle string is abab you take the lcm of answer with 2(not 4)

»
8 months ago, # |
  Vote: I like it -23 Vote: I do not like it

Speedforces

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

ones who solved C are more than ones who solved B !!

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

    In general A B C D easy problems , I struggled with B due to specific case which I think a lot of people struggled too and that cost me 5 wrong answers for the sake of not testing my solution well

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

    I solved B but not C,D,E

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

    I took more time in A , than (B+C+D) combined xD

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

    Yes! Sometimes $$$B$$$ is more indirect and confusing than $$$C$$$. I too spent slightly more time on problem B than C:

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

      I spent 6 minutes on A, vs 4 minutes on B and 3 minutes on C..

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

    I guess because B was just observation.

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

The pedestal consists of 3 platforms for 2-nd, 1-st and 3-rd places respectively.
it's the first time in cp history to see the above misleading description ,why it can't be 1-st ,2-nd and 3-rd!

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

For problem A, can the problem statement use $$$h_1, h_2, h_3$$$ instead of $$$h_2, h_1, h_3$$$ ? Putting some formal definition helps too like

  • $$$h_1 + h_2 + h_3 = n$$$
  • $$$h_3 < h_1 < h_2$$$
  • $$$h_i > 0$$$ $$$(1 ≤ i ≤ 3)$$$
  • $$$h_2$$$ is minimized

Took me a while to understand the problem statement itself

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

help me solve E,
if it is greddy then write proff of correctness
or give me some tips on how to think on this kind of question

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

    Instead of maximizing values, we want to "minimize" loss. Notice that if we group 2 items into the same package, their sum might not be divisible by $$$k$$$. So we can see here some "profit" are lost (which is the remainder of $$$(a_i + a_j)$$$ $$$\text{mod}$$$ $$$k$$$. Therefore we want to pair items in such a way so our profit loss are minimized.

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

      yep. It was all about minimizing waste.

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

    For each good it is sure that u can get a[i]/k.Then you still have to deal with n a[i]%k. Use f[j] to record the number of a[i]%k that == j. If u can find two things that add up over k,ans++. Even the biggest two goods,still 2k-2,and after /k,it is 1. 159835536

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

    You can see my solution O(N) : 159865328

    Three steps :

    1. All those with value a[i]/k will be included and reduced to a[i]%k

    2. Pair all the a[i]%k first half (< k/2) to other half (>k/2) | so that sum>=k

    3. All those (>k/2) can form pair themselves which are left after pairing first half.

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

How to do math solution in E?

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

Not able to pass E's Test case 3. Anybody has a hint??

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

    Int overflow. Use ll ans = 0; instead of int ans = 0;.

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

    My solution is firstly for each $$$i$$$, add $$$a[i]/k$$$ to the answer, then reduce $$$a[i]$$$ to its remainder divided by $$$k$$$.

    Then for example with $$$k = 6$$$ : we want to pair an $$$a[i] = 4$$$ with something $$$\geq 2$$$ (so not $$$1$$$) to get more cost, this can be done with 2 pointers

    Edit : nevermind, got hacked :d

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

      I did it with binary search on maps

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

    same happened to me

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

why is this giving WA?? what's test 2 :( code

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

What is wrong with my D code? used sliding window Code

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

    You are checking for s[k — i] but this will result in a negative index, instead you should check for s[i — k]

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

    in the second for loop it should be i — k and not k — i since i is always >= k

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

    Your sliding window loop does not actually consider the correct window, instead of:

    ...
        for (int i = k; i < n; i++)
        { 
            // adding next character at right in window
            if (s[i] == 'B')
                ++b;
            else
                ++w;
            // removing previous character from left in window (wrong! should happen after your ans is checked!)
            if (s[k - i] == 'B')
                --b;
            else
                --w;
            ans = min(ans, w);    // Here, your window does not consider the starting character
        }
        cout << (ans > 0 ? ans : 0) << "\n";
    ...
    

    You should have firstly checked for ans= min(ans, w) before removing the initial window character out, just like:

    ...
        for (int i = k; i < n; i++)
        {
            if (s[i] == 'B')
                ++b;
            else
                ++w;
            ans = min(ans, w);      // Correct Place for finding answer
            if (s[k - i] == 'B')
                --b;
            else
                --w;
        }
        cout << (ans > 0 ? ans : 0) << "\n";
    ...
    

    Only Comments are additional, to help you understand dukhi_insaan. See if it helps!

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

How to solve E ?

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

    we need to maximize floor((a[i] + a[j]) / k)

    floor((a[i] + a[j]) / k) = a[i] / k + a[j] / k + (a[i] % k + a[j] % k) / k -> (1)

    => we need to maximize (1)

    a[i] / k and a[j] / k are constants, so we cannot maximize them. Therefore, they directly contribute to the answer.

    => we only need to maximize (a[i] % k + a[j] % k) / k

    The above expression can be maximized when the numerator is maximum since the denominator is constant.

    => now we need to maximize (a[i] % k + a[j] % k). This can be done by an approach similar to two-sum where we try to pair the smallest remaining element with the largest remaining element such that their sum is >= k (because only then the sum can contribute towards the answer)

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

Slowly becoming less incompetent at algorithm coding thanks to these competitions. Thanks for taking the time.

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

Hey guys, could anyone of you help me out real quick? Speaking of problem F...

This is my submission: 159858692. I count the lengths of all cycles and see whether this cycle really changes anything in the string, if so — I include it while LCMing all valid cycles.

What did I miss here? I am thinking of some cycles of substrings like "baba". Is that the case or anything else?

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

    "baba" will become equal to orginal string after 2 rotations and not 4

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

      Yeah thats what I was thinking about, thanks. Any way how I could implement it in my code?

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

        The time constraints allow you to rotate the string untill it becomes equal to original.Otherwise ,for a linear time solution you can implement it using LPS(longest prefix suffix) array.

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

          Alright, thanks again, I'll look into it!

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

            Or you can just use: int period = (str + str).substr(1,2*str.size()-2).find(str) +1;

            Above code works in O(n) time.

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

              How would that work? I guess I apply it incorrectly: 159869936.

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

                Sry my mistake there should be 2*str.size()

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

                  It still seems to be failing if I use correct string for that. Check out my code in the previous comment, please.

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

          "for a linear time solution you can implement it using LPS(longest prefix suffix) array." Can you explain? Or provide any tutorial or documentation?

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

          but it s not written that sum of n over all test cases will not exceed 200.Does that mean that in a single input set, there could be 1000 inputs where n=200?

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

    Yes. The periodic can be something like abcabc for this case, you need to take the length 3 instead of 6 into account

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

      I see, thanks. Any way how I can insert this check in my code?

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

        You can brute force the length of the periodic substring. For a fixed periodic with a length $$$len$$$, we can check for every substring with a length $$$len$$$ are the same substring. So we can just brute force the $$$len$$$ value (make sure that $$$len$$$ is a divisor of the cycle length as well)

        This will runs in $$$O(n^2)$$$. Since $$$n$$$ is small enough, we will be able to do so

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

          Got it, thank you for your time!

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

          This will run in $$$O(n \cdot cnt(n)) \approx O(n \sqrt[3]{n})$$$ where $$$cnt(n)$$$ — number of divisors of $$$n$$$.

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

          ...

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

        you can just brute force on all the factors of the length of the cycle to check the periodicity of each factor and consider the smallest one

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

    Ye that's about it. If you have a -> b -> a -> b cycle then it's rotational value is 2 not 4.

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

Does the time taken to solve questions matter in div 3 & div 4 contests?
Like if 2 people solve the same number of questions, do they get the same rank or does the one who took less time to solve them get a higher rank?

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

    The one who spent less time gets a higher rank.

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

If the equal cycles of a string are its periods then what is KMP made for???
I remember using this above rule in an atcoder contest, but I forgot it today due to knowing what KMP does

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

EDIT : Got the failing test case. Thanks!

Can someone tell me why my code : https://codeforces.com/contest/1690/submission/159863108 is giving index out of bounds, also do tell the test case that is failing. Thanks!

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

    In submission, it is written " 'out of bounds' on the line 128". Probably when rem[k-i] is empty

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

    Assuming that i == k-i then, you might reach a case where the size of the vector only consists of 1 element and you're popping back it twice (for example where $$$i$$$ and $$$k-i$$$ is equal to 0)

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

Hi everyone! Could someone, please, explain me the discrepancy that I see when I click on "Common standings" vs clicking on "Friends standings"? Currently, when I click on common standings I am on the 7040 place, but when I click on "Friends standings" I find that I am on the 8430 place. Why is that?

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

I solve A B C and i got TLE on test 5 on D and F because I just brute forced every thing , sad. but Nice contest !!

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

Nice round! and very educational.

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

    Take a look at Ticket 11095 from CF Stress for a counter example.

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

    You have directly assumed that the number of members in the cycle is the number of iterations it will take to loop back to initial value or 1 in the case of similar characters in the loop. But suppose take the case abab in this it will take 2 iterations only. abab --> baba --> abab.

    What you actually needed to do here was find if the string has a repeating pattern which you can do in two ways as pointed by many people — 1. Using Longest Prefix Suffix — O(n) time complexity 2. Or rotating the array till it is equal to its initial value — O(n^2)

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

      get it thnx

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

      Can you explain "find if the string has a repeating pattern" part? [ I know Longest Prefix Suffix (KMP) or Prefix Function will give me if a prefix has repeated inside the string, but how that help me to find the cycles to return to initial string ?]

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

    You haven't considered if a cycle has string like abcabc, when this is the case, the length of the cycle is not 6 but 3

»
8 months ago, # |
  Vote: I like it -22 Vote: I do not like it

The fiction of G is misleading... suppose trains are [8,5]... as they are initially apart, they stay apart. Now the message (1,5) makes the trains [5,5]. But they are still apart, since they were never together.

The problem would be clear if it was specifically mentioned that separation between trains moving at the same speed does not matter.

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

Emmm....Why I am an official participant with rating 1601?!?

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

For problem F I have counted length of all cycles and also the stored the text string formed for each cycle and then simply use Longest prefix suffix logic to find if there is a repeating pattern so as to find min iterations in which cycle loops back to initial value and finally I have taken lcm of all these values.

But still it is giving WA. Can anyone please help me figure out what's wrong in my approach? :(

Link to my solution

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

can anyone tell me what's the wrong with my code , i tried to stress it but reached 4000 test case without failing my submission :https://codeforces.com/contest/1690/submission/159867066

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

logicforces

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

Hi! Why does this submission 159869794 get AC, but this 159757251 — WA?

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

    This kind of bugs is one of nightmares in java. Remember that ArrayList returns Integer, not int. You should use equals instead of ==, when you are comparing Integer with Integer. In your AC code, you compared Integer with int, so it was fine.

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

      Thanks a lot! I would never think about it.

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

https://codeforces.com/contest/1690/submission/159874958 can someone why this code is failing ?

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

How to solve D??

I tried to iterat through all substrings of length K and count the 'W' cahr and every time update the ans with ans=min(ans,cnt)

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

    It can be solved using prefix sum. You basically count up to each index how many 'B' are there and store them in an array, the loop through this prefix array and check in a subarray of length k how many 'B' are there. I'm not really good at explaining so you can check my code and ask any questions if you want

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

      It's just like when you asked to give the sum of elements from L to R but here the number of 'B' and update answer with k — number of B?

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

image

B WAAAAAA

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

In problem F, how do I find cycle for an alphabet?

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

    If you want to find cycles in permutation then you can use DSU.

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

    dsu works but is kind of an overkill. I usually go for a dfs-like iteration and keep visiting the next element until I reach the beginning from where my iteration started. I also keep a bool array to not run a specific cycle twice

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

I'm gonna become blue now, thx

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

Is there a possibility that the answer for F exceeds $$$10^{18}$$$?

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

    No

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

      $$$\operatorname{lcm}(2^4, 3^2, 5^2, 7, 11, 13, 17, 19, 23, 29, 31) > \operatorname{lcm}(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)$$$

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

can anyone tell me why my code giving WA https://codeforces.com/contest/1690/submission/159887831

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

    1 6 cabcba 6 1 5 2 3 4

    correct output — 2 your output — 4

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

    You are not counting the answer for window i = 0 to i = k-1. Just add ans = min(ans,w) before if(i<=k) line.

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

My Rating was 973 initially, still this contest is showing unrated for me. Why so ?

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

How to solve G

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

Can someone tell me why f is wrong in the 100th of the second example?Thanks you!

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

    that test is 9 cbbbcbccb 9 5 6 8 4 3 1 2 7 which contains a cycle of index 5-2-8-4 cbcb ,it justs need 2 steps instead of 4 so the answer is 6 not 12

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

      Thank you, your answer solved my problem perfectly。

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

Will the editorial be released for this?

Its been around 13 hours since its completion.

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

After giving the contest, why am I still unrated?? This was my first contest.

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

    Due to the hacking phase that was completed just a few moments ago. I guess you will get your ratings in a while!

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

Ratings are not updated yet?

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

wHeRE EdiToRiaLl?

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

why it is showing unrated till now

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

I'm still unrated.

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

After how many hours will the rating be updated?

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

I think given explanation of example in E is wrong. Please correct me, if I am missing something.

Example is, n=6,k=3, weights of goods a=[3,2,7,1,4,8]

We have to pack them into n/2 packages, ie. two goods in each package, and such that total cost is minimised, where cost is [weight_of_package/k], (ROUNDED DOWN).

So, "according to me", they should be packed into these packages: [7,1] (cost=8/3 = 2), [3,2] (cost=5/3 = 1), and [4,8] (cost=12/3 = 4)

So, cost should be 2+1+4 = 7. (This is the minimum I can get)

But in example the minimum cost given is 8. How ? Or there's some caveat in my approach ?

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

    The problem is a maximization problem, not minimization.

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

      Thank you, I believe I should focus more on the problem first... wasted much time thinking HOW and WHY for the wrong thing :(

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

I had a doubt. Is this contest unrated. My rating is less than 1600 and I have given 5 rated contests before.Have the ratings been applied yet?

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

thank you AHMADUL for weak pretests on E.

Very idiotic.

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

First 3-digit placement, yay! :D Thank you for this contest! <3

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

Are the ratings updated?

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

This is my submission for E, why getting TLE, complexity seems to be O(n+k^2) to me which should be fine, https://codeforces.com/contest/1690/submission/159917329

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

    It's $$$O(T(N+K^2))$$$ which cannot pass

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

      But the constraint for K is 1000 , so K^2 should give 10^6 which is enough I think , considering it is given sum over all test case will not exceed 2*10^5

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

        There's no constraint on the sum of $$$K$$$ over all the test cases.

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

why my rating increase or decrease by this contest i solved 3 problems!!

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

i dont understand why this round was unrated for me.........

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

    Maybe someone made a mistake. Anyways it's going to get fixed soon most likely.

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

Can someone plz tell me why is this code failing at test 2? "problem B" https://codeforces.com/contest/1690/submission/159826598

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

    Consider the case, a=[6 5 7] and b=[0 0 2]. Here, your logic will give output as yes as it first compares for 6,5 and then for 5,7 but the correct output shall be No. Understand why this problem arises and Modify your logic to correct it.

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

    The first mistake syntax error you are doing is that (if(su[i]==su[i-1]) continue;). this condition can give you index out of bound for i=0, and accessing su[0-1] = s[-1].

    The test case where your code is when you need to compare the difference of current ith to greater previous than last one. i.e 1 4 5 1 2 5 1 0 0 0

    Expected : NO OUTPUT: YES

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

still not updated the ratings ..... it's been more than 17 hours since it got finished.

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

    same problem.. i dont know why but for both of us the round was unrated

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

My solution for F was accepted in Python but not in PyPy3

ಥ_ಥ

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

Attention!

Your solution 159836981 for the problem 1690F significantly coincides with solutions Pretest2/159836252, Ksathwik03/159836981. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I have referred and used the template provided by gfg (https://www.geeksforgeeks.org/minimum-rotations-required-to-get-the-same-string-set-2/) which has been published before the start of the contest ,to solve the problem of of minimum rotations to get back the original string i did not use any unfair means or copied the solution you can check our both code they are completely different except for that rotation string part. [user:https://codeforces.com/profile/MikeMirzayanov] i request you to please check and do the needful :).

I would like to mention that the account with whom i was (plagiarized)[https://codeforces.com/profile/Pretest2] , his rating got increased whereas my rating wasn't

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

I am amazed how many participants are discussing their "missed" rating change instead of solving unsolved problems.

$$$P.S.$$$ It's simple, if there was no announcement that round have became unrated, you should just wait a bit.

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

    Damn you had the time to read through all comments

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

my rating is less than 1600 so if i am right this round should be rated for me but why is this contest not showing in rated graph? and my rating too remained unchanged.

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

    Maybe just wait

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

    The ratings have not been updated yet. You will see your rating's changes only after they have been updated.

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

Why is the Rating Not Updated

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

Rating update is slow(;′⌒`)

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

    I reloaded many times with the expectation of seeing my positive delta. But it didn't appear :(

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

      Just use CF Predictor

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

        Carrot is also good

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

          Wait so I just added Carrot, and it shows a different predicted rating change, much lower than CF Predictor. Why so?

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

            Carrot is normally much more accurate than CF predictor. So you should go with the rating that carrot predicts

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

            Carrot's prediction should be closer to the actual delta, I use both and this is what I experienced.

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

who know when rating change

»
8 months ago, # |
  Vote: I like it -10 Vote: I do not like it

wth !! It's unrated for everyone . You can see in your graph in the profile ,change to all contests .

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

May I know will there be any Editorial for the contest. It is my first contest and I only solve 4 lol~ It is a fun and beginner-friendly contest.

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

When will the ratings get updated?

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

hello admins, i got a mail for plagarism for submission 159834564 for recent Codeforces Round for Div 3 and matching solutions of me and Chirag37/159781058.Sir/Mam i dont even know him and i swear i never practiced like this question before.I swear i dont use ideone.com and hence no chance of intentional leakage of code. Please it is my humble request to grant me some increase in rating. Thank You

»
8 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Hey Vladosiya, MikeMirzayanov

I just recieved a message saying that my solution in the last div.3 contest coincided with Time_to_pass. I'm mistakenly accused of cheating in #797 (Div. 3).

I swear that I didn't cheat in the contest, and all the codes in this contest are 100% written by me. Both were my IDs only. I tried solving it from another ID to avoid penalty. I know it was not never a good habit. I will not be doing these silly things onwards. I apologize for my mistake. I have given around 30 contests and this is the first time I have done this. Please help me. [I can give proof if needed about the IDs ownership]

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

Who else got bamboozled by F and did union find only to get a wrong answer and not knowing why Only after contest, then realised its a directed graph and uf cannot be applied here

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

Dear MikeMirzayanov,

Sir my rating get changed even though it should be unrated for me can you check this as it will be unfair for others.

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

hello admins I have just received a message saying my solution 159822431 for the problem 1690B significantly coincides with solutions 7878797/159821282.It was unintentionally because I have used ideone.com and I am totally unaware of that because till now I have given few contests on Codeforces using VScode and this was the first time I have used ideone.com because of some updation required in vscode. And I have checked 7878797 user id recently and I have found that this id is having its rating skipped in its previous contest also and one more thing is that this id have used different templates of code in every question, these two things are enough to know that user id 7878797 is a cheater and have copied my solution of 1690B which was totally written by me. So, I am totally innocent and hence this is my humble request to give me my ratings back and now onwards I will totally follow the instructions of which I was unaware previously. Thank you

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

Hey Vladosiya,MikeMirzayanov

My solution for the problem 1690E significantly coincides with my solution.My 1st solution was in queue so I again submitted my same solution for the problem 1690E.My all solutions were skipped.Please look into this matter. Here is the proof

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

can someone tell me why this submission gives runtime error https://codeforces.com/contest/1690/submission/159945020

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

This contest is not very interesting as problems A to D are easy and it is not expected from a div 3 contest.

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

I want to have Contribution -100

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

Hi, can someone explain the rating logic (or link it) please... I solved ABCD and F...F is rated 1700...however the delta i got is just 300 something...which seems too low xD

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

Hi Admin, ( Vladosiya , MikeMirzayanov )

I received a message regarding the contest Codeforces Round #797 (Div. 3) saying that: my solution for the 1690E - Максимизация цен coincides with about 11 other people. - I'm a newbie here and I don't know many people, so cheating/copying is unethical and impossible for me. I've realized what mistake I did. I use ideone.com and other open judges (for this contest I used ideone) to test my solution on sample cases, didn't know that people could copy down answers/solutions from ideone.com. I know this is a clear rules violation as per unintentional leakage, however, I was totally unaware of it. I'm really sorry about this and I'll make sure to use only local and private testing systems in the future. I went through the solutions of the people mentioned and noticed that they had copied the code, with some modifications, which is unfair for me. Can you please look into this and return my ratings, I had a decent positive delta. It'll really boost my morale. Thanks.

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

    you will get more positive rating changes in the future again. it was a mistake and you got the lesson (not using public online ides). It is not a big deal, just forget about it.

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

Good round.

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

    Bro, they might not block your id but I don't think you will get the rating anyways for the second time after the engine detected something.

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

Good luck cheaters for next contest

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

Why so much hate

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

In problem F, the rotation of string will cost o(n^2) time. it's ok for this problem. But I want to know is there any o(n) approach to do this work?