By awoo, history, 21 month(s) ago, translation, In English

Hello Codeforces!

On Jan/24/2023 17:35 (Moscow time) Educational Codeforces Round 142 (Rated for Div. 2) will start.

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

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

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

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

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

Harbour.Space

Hey, Codeforces!

Preparations are under way for the second “Hello Muscat 2023” ICPC programming bootcamp, the continuation of the “Hello” bootcamp series, organised by Harbour.Space University, in collaboration with PhazeRo, Gutech, UK Oman Digital Club, Leagues of Code, Gutech CS Club and Codeforces!

Quite exciting, isn’t it? Now it's time for you to dive deeper into the competitive programming world with the 8 days intensive Hello Muscat 2023. It will take place in Muscat, Oman and online from March 8th to March 16th, 2023, both participation formats are available. As always, we can’t wait to see you there to learn, practice and compete on the international stage, smoothing your road towards the joined World Finals 2022 and 2023 in Egypt!

Our coaching line-up combines talent and experience, featuring ICPC world champions winners and finalists, as well as legendary names from the field of competitive programming: Mike Mirzayanov MikeMirzayanov, Yahor Dubovik 244mhq, Artem Plotkin Rox, Maksym Oboznyi MaksymOboznyi and Nikolay Budin budalnik.

The Bootcamp will be split into three divisions:

  • Division A. Division A will be a mirror of the Petrozavodsk Programming Camp. Suitable for teams who already qualified for the world finals ICPC or are aiming that high.
  • Division B. Designed to help teams prepare for the next season of ICPC regional competitions. Appropriate as an introduction for teams and students just getting their foot in the door of the world of ICPC and competitive programming competitions in general.
  • Division C. Designed for newcomers to the world of ICPC competitive programming.

Types of participation: On-Site and Online

_We believe that participation in our Bootcamp should be accessible by all teams wherever they are and that is why we made onsite and online types of participation. 20% Early Bird Discount is offered to universities and participants who register and pay before Jan 31st 2023.

  • On-site:

Price: 1500 € — 1200 €

What is included: training, contests, access to the recordings of the lectures, accommodation for 9 nights in a 4 star hotel Mysk, breakfast and lunch, transfer from hotel to venue every day, leisure, entertainment and welcome pack.

  • Online:

Price: 100 € — 80 €

What is included: training, contests, access to the recordings of the lectures.

Learn more about Hello Muscat 2023→

Good luck with the round!

UPD: Editorial is out

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

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +72 Vote: I do not like it

Welcome to slow-rating-update round #142!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    True. These rounds and div3 rounds take a lot of time. maybe because of hacking phase.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Me after solving ABCD:

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I'm not aware of this: I don't see this contest taken into account on rating because it's not yet processed?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody noticed that quite hell unusual time of 26th Feb contest??!!

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Hope to get BLUE today!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I feel like Educational Rounds are more Mathematical than usual rounds, is this the case?

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Good luck! Wish every participant have higher ratings!

»
21 month(s) ago, # |
  Vote: I like it -33 Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it -62 Vote: I do not like it

Classic Mathforces.

None of A,B and C had anything to do with DSA

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    A was greedy, B was a math problem, C use binary search. 1 out of the first 3 problems of a div 2 round being math problems doesn't imply that a contest is "Mathforces" dumbass. Also, atleast don't be green and talk shit about a contest not having enough DSA problems.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -37 Vote: I do not like it

      Mind your language, this is not reddit/twitter. As for rating, I don't take these contest seriously nowadays. I at one point was Blue unlike someone who has never crossed 1500 xD

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        "Mind your language"- What you say matters as much as how you say it, so that's pretty rich coming from a guy who spouts shit like there's no tomorrow.

        Also, I don't want to get into petty comparisons, but I have given like 7 contests till now, so I'm pretty sure my peak will be way above yours :)

        Edit: The part about "someone who has never crossed 1500" didn't age well

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

          Bro called me a dumbass for sharing my take on the contest and then preaching me.

          And then Bro says he doesnt do pity comparisons but advices me to get out of green and then give my analysis on the contest.

          Hypocrisy at its finest!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Considering your past rating you shouldn't have had any trouble doing A, B, or C... idk man skill issue

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's not about whether I am able to solve or not, its about the quality of questions. I was able to solve A and B but still complaining because there was no satisfaction solving those problems

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        of course you didn't have any satisfaction solving them, they aren't supposed to be hard for anyone above 1k rating

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          idk B was kinda annoying for me, C was good tho

»
21 month(s) ago, # |
  Vote: I like it -28 Vote: I do not like it

Problem C is the literal definition of million corner cases and i love it lol

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Think about binary search approach

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +32 Vote: I do not like it

    Huh? I have 0 corner cases.

    (now someone will definitely hack me xd)

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      well, my first approach is to find middle positions not numbers, and when i realised that, i also realised the sample test cases has outsmarted me ._.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    190436527 No corner cases whatsoever.

»
21 month(s) ago, # |
  Vote: I like it +27 Vote: I do not like it

Nice problem D, it took a while before I noticed the name of the problem :) great hint

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I quite liked problem C. I am pretty proud of an elegant solution I came up with inspired by some monotonic stack problems I was solving the other day.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve 1st ?

My approach was to count the number of frequency and take their sum, and ans should be max to max n what is wrong in this?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My solution is to count number of 1-s in array and print n — (count_1 / 2).

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Only double 1-s pair in the array can decrease operation times, so all you need to do is just count the pair's amount.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You can kill monsters of health 1 in pairs and remaining you can kill individually.

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

I was stuck with problem C. My code outputs correctly for samples and inputs I give. Perhaps I can't find the edge cases. Here is my code https://codeforces.net/contest/1792/submission/190399259 .

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Counterexample:

    8
    2 3 1 7 8 4 5 6
    

    Output should be 2. Pick (2, 7), then pick (1, 8). Your code seems to output 3.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

leave it there is an easy way to solve D then my way

»
21 month(s) ago, # |
Rev. 4   Vote: I like it +55 Vote: I do not like it

OMGGG solved E on 01.59.54 les goo

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve 2nd problem

my approach was if we can have a > 0 then one joke from b and one joke from c and alternating it till either b or c runs out . so it's min of (b , c) + min jokes in total . now these jokes will balance it and bring it back to a . now if d > 0 i can take the min of d , a extra jokes . if( b or c ) are not 0 . add one more joke .

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    If $$$a = 0$$$, output $$$min(1, a + b + c + d)$$$.

    Else the answer is $$$a + min(b, c) * 2 + min(a + 1, b + c + d - min(b, c) * 2)$$$

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can u explain how min(a+1,b+c+d-min(b,c)*2) come up .Beacause I am not able to figure it out

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        • Take all $$$a$$$

        • Taking $$$1$$$ $$$b$$$ then $$$1$$$ $$$c$$$ until $$$b = 0$$$ or $$$c = 0$$$.

        • Now both of them will have $$$a$$$ points and at least one of them cannot get anymore points. You can take at most $$$a + 1$$$ from $$$b + c + d$$$.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

D was nice combination of DP and trie.. loved the question

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is DP being involved? Do you store the answers so that you do not insert a permutation again?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      no, You create dp[i][j] = Indices of all the permutations, which has '1' on i'th index and 2 on j'th index .

      Then, for each permutation, u can loop. this will give you ( 5 * 10^4 * 8! ) roughly... Also, u need to put break statement if you already found the ans of length 'm' .

      You can follow my solution here.

      ALAS, I was just 2 minutes late from finishing my final solution :( ...

      If you need understanding my solution, feel free to ping me.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Unfortunately your solution got TLE at 31

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yeah, it got TLE, I am resolving the errors. Sorry. I will update once done. Thanks :)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

i freaking could not implement trie, i chocked and even forgot dynamic allocation !!!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    If you are talking about D, straightforward polynomial hashing (without the mod) would do.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you mean rolling hash right? I could not think of this in contest, wasted an hour googling dynamic allocation and still could not do because of the stress of the contest.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain what polynomial hashing is? or post a link please. I'm having a hard time implementing D as well

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        polynomial hashing is basically encoding an array/string into a number. So for example the permutation $$$5, 3, 1, 4, 2$$$, you just encode it into the number $$$53142$$$. This way, you can easily compare array in $$$O(1)$$$, in order to binary search/use map

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you use map with vector it also works

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain how that would work, I saw many submissions with maps but I can't seem to comprehend them? Im not able to understand how the map solutions are working.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Map remembers a value by their key, a key can be almost anything, even vector, so when you are itterating over an array and you are looking at what prefix should the other array have to get beauty of A with the array we are looking at, you can remember that prefix as a vector and use that vector as a key in map, and remember value 1 in map at that key. after doing that for all arrays, you are now looking for an answer for an array lets say C, you itterate over its prefixes, push them in vector, and for every prefix vector you check if you have written 1 in the map at the place of this vector( so you use this prefix vector as a key) if you have then you can get the beauty of the lenght of the prefix vector

»
21 month(s) ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I think I had an interesting approach for C, curious if anyone else had the same idea:

  1. Push all elements in the permutation into a queue. Initialize variable 'min' as 1, 'ans' as 0.

For i = 1 : n:

  1. While queue.front() == min or queue.front() == selected, queue.pop(), min++ if queue.front() == min

  2. Selected.insert(i, n-i-1), ans++;

Done! Return answer.

»
21 month(s) ago, # |
  Vote: I like it +20 Vote: I do not like it

Damn. beethoven97 hacked LGM turmax's solution

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

For me C > E > D. I Spent more than 40 min on C and am still not able to solve it. What's the solution?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think in terms of binary search. Can we solve the problem with $$$i$$$ operations? Now think what should the last operation be? What should the second to last operation be, and so on so forth ...

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My reasoning was that if we select some elements, we will always select 1, n, 2, n-1, etc... The order we select them should not matter because some optimal ordering should exist anyways. So I created a queue and popped off elements while it was sorted. Then, whenever it was unsorted, I removed elements i and n-1-i from the array and continued to pop while it was sorted. The number of times you remove i and n-1-i is the answer.

    Submission: 190357765

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can see that you can not use operation on numbers that are close to each other and ordered for example 4,5,6. 4,5,7 and 6,5,4 will not go. So if array is like this 4,8,7,5,3,2,1,6 you can do operation on every other number except these 3 numbers = 4,5,6, and answer will be max(min(numbers)-1, n-max(numbers)) = max(4-1, 8-6) = 3.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just do n/2,n/2+1;n/2-1,n/2+2;... if n%2==0 or do n/2,n/2+2;... if n%2==1 and skip the first operations if they are already in place.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    You have to find the longest MIDDLE subarray.

    5
    1 2 5 3 4
    

    The longest you can find is 2 3 4.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Would C Problem be solved by 2 Pointers ? if not, then what?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give stress test for 2nd testcase on E? 190401625

»
21 month(s) ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

A: Use first spell for 1-health monsters and second spell for others.

B: First tell all type-1 jokes, then tell type-2 and type-3 jokes alternately, until one type of jokes run out. Then tell all remaining jokes until someone leaves.

C: Take n=6 as example. First let ans=3=n/2, and check if the order of {3,4} is correct (which means, 3 appear earlier than 4 in the initial permutation), here 3,4 are "central" elements of 1-6. If it's not, we need ans=3 operations. Otherwise, we need to do ans--, and check the order of {2,3,4,5}. Do this repeatly until we fail at any check or we've checked the whole permutation. If n id odd, let k=(n-1)/2, start at ans=k and checking {k,k+1,k+2}.

D: We need to check the longest common prefix of ai and aj^(-1) (where aj^(-1) is the inverse of aj), we could store all aj^(-1) in a trie and find for all ai.

E: Didn't solved. Maybe we can let set s={d: m1*m2%d==0 && 1<=d && d<=n} and do loop for(d1:s) for(d2:s && d2>=d1) but I don't know if this approach will get TLE (for cases like n=1e9, m1=m2=735134400).

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Stored all aj in a trie and searched for aj^-1, didn't realize the solution during contest. :(

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    D: Sort the permutations and For every prefix of every permutation, binary search permutations that match this prefix and use segment tree to update range (l <= i <= r) a[i] = max(a[i], x). 190359788

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Any hints for E?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    two pointers

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In defense of this hint, my submission passed system testing with a two pointer-like approach: https://codeforces.net/contest/1792/submission/190397103.

      Although upon further reflection, the analysis I had of its time complexity was not correct, so if anyone can come up with a proof of correctness (or a hack), that would be cool!

      The main idea was to process the divisors in ascending order. Let the current divisor be $$$a$$$. We will maintain a pointer to the minimum divisor, $$$b$$$ such that $$$a / b <= n$$$. Then we just search from $$$b$$$ until the last divisor <= $$$n$$$. It feels like there might be an argument that the average number of elements we check is not too high, but I can't find it.

      The dp solution seems much more straightforward to understand, so apologies for the misdirection.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't know for sure that this is the intended solution.

    First, find all the divisors by brute force as the maximum number of divisors for (large) n cannot exceed cube root n. And for every divisor x below 1e9, remove the divisors of x until x*1e9 iteratively and update the answer.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

    Generate all divisors of $$$m$$$ (there's about $$$10^5$$$ of them in the worst case). For every divisor, instead of the minimum row where it appears, let's search for the maximum column (it's easy to see that these two are equivalent). So, for every divisor, we need to find its maximum divisor which is not greater than $$$n$$$.

    This can be done with the following dynamic: $$$dp[d]$$$ is maximum divisor of $$$d$$$ not exceeding $$$n$$$. If $$$d \le n$$$, then $$$dp[d] = d$$$, otherwise iterate on the prime divisor $$$p$$$ in the factorization of $$$d$$$ and find the maximum of $$$dp[d/p]$$$.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you mention the time complexity of this approach? It's not immediately clear this solution can fit into time limit?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 3   Vote: I like it +15 Vote: I do not like it

        Something like $$$O(D \log D \log m)$$$, where $$$D$$$ is the number of divisors of $$$m$$$. There are $$$D$$$ states in the dynamic programming, each state has up to $$$\log m$$$ transitions (each transition corresponds to dividing by a prime from the factorization of $$$m$$$), and an extra logarithm because everything is stored in a map.

        upd: Plus $$$\sqrt{m_1} + \sqrt{m_2}$$$ to factorize $$$m$$$.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +20 Vote: I do not like it

          More accurately, $$$D \le 105\,000$$$, "$$$\log{m}$$$ transitions" is actually $$$\le 15$$$.

          And don't use maps for $$$dp$$$, use vectors.

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            How to not use maps? The factors of m could be large right?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I generated all divisors of $$$m$$$ . For each divisor $$$a$$$ , I brutely searched minimal row number within the range $$$[\lceil \frac a n \rceil,min(n, \sqrt a)]$$$ among divisors of $$$m$$$ .This naive solution seems to run very fast.

      Is it reasonable to let this solution pass? I mean, this solution is unbelievably too simple, meanwhile hard to know exact time complexity.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My best guess is that for each divisor $$$a$$$, there's a big chance that you have to go through like $$$50$$$ divisors on average (maybe much less I don't really know) before finding an answer. You see, for highly composite numbers, aka numbers that has a lot of divisors, its divisors are also expected to have a lot of divisors, thus it is likely for the algorithm to encounter a divisor of $$$a$$$ in very few loops. For number that has less divisors, I think that there simply isn't enough divisors to make a simple $$$O(n^2)$$$ getting TLE

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Why dp[d] = std::max(dp[d], dp[d / p]), I don't understand this, please explain it to me.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think dp[d] must equal std::max(dp[d], dp[all_of_divisors(d)])

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          If you do dp[d] in order then dp[d/p1/p2] would've already been considered during the transition of dp[d/p1]

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

D could have been a really nice binary search + trie task if bounds were N<=1e5, NxM <= 1e5

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why binary search tho? You can just DFS down the trie, and the answer would simply be where the DFS end.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I feel bad when I heard that $$$O(n^2)$$$ solution can pass F2.

I feel worse when I really pass it after the contest. Here

I guess the author think D&C + fft is too slow, but it is not that slow, and is it reasonable to let $$$n^2$$$ solutions pass?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem F of last contest also be passed by some O(n^2) solutions.

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    Unfortunately, looks like really fast templates for modular arithmetics do the trick. I haven't come up with the D&C+FFT solution, the model one has slower asymptotics than D&C+FFT. So, basically, I could try one of the following two things:

    • let only solutions with very optimized FFT and modular arithmetics pass;
    • let solutions with more "normal" implementations of FFT and modular arithmetics pass, but risk that someone with a very strong modular template will squeeze $$$O(n^2)$$$ in

    I still think that 2nd is better choice. Maybe my mistake was even trying to distinguish $$$O(n^2)$$$ and $$$O(n \sqrt{n \log n})$$$. I am sorry for that, but I hope not a lot of participants were affected by the issue.

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      The formula is like $$$f_{i} = \sum{f_{j}\times f_{i-j}}$$$, in my memory it can be solve by D&C and fft(since $$$f_{i}=\sum{f_{j}\times g_{i-j}}$$$ for fixed $$$g$$$ can be solved) , but maybe I remember it wrong(I feel sorry), and I didn't figure it out during the contest.

      However, OEIS A000311 shows that $$$ans = exp(f(x)) = 2f(x) - x + 1$$$, thus we can solve it by Polynomial Newtonian iteration($$$O(nlogn)$$$ maybe?).

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I squeezed in $$$O(n^2)$$$ by precomputing for biggest n and putting it into the source code and running the $$$n^2$$$ normally for small $$$n$$$. I didn't use any very optimized modular arithmetic. 190408679 (there seems to be no test with a number in range of [3.5e4,4e4), so the runtime is misleading but testing the worstcase on custom invocation gives 4500 ms.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In fact we can directly get a formula using lagrange inversion. the final result (plus 2) is the $$$x^{n-1}$$$ coefficient of $$$2(n-1)!(\frac{x}{2x+1-e^x})^n$$$

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Did any1 use strings for D?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I concatenated values in array and stored them in hashmap, but I did it because golang doesn't support custom key types in hashmap.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yup! I did.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Could anyone help me understand why my code for D gives incorrect output here:

https://codeforces.net/contest/1792/submission/190405242

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    your answer would have been fine if rj = pqj

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for helping. What makes this hurt more is that I would have got last 5 second AC instead of WA, had I not done that silly mistake xD.

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      Wait a minute, but wont p(q(j)) and q(p(j)) be like the inverse of each other, ie. they will produce each other?

      For example, wouldn't the product of p = 3142 and q = 2413 be 1234 whether you take r = p.q or r = q.p?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        No take this for example
        2 4 1 3
        2 1 4 3

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          In the first sample test case, the optimal p for i = 1 such that k for ai * p is maximised will be [3 1 4 2] right? But none of the given arrays have a prefix 3, So how is the answer 1 and not 0?

          I'm extremely sorry if I'm asking dumb questions rn, I'm a bit sleep deprived.

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You are getting confused 💀, take a vector of pair store the values of "p" in that vector along with index ({value,index}), sort it and then take the prefix of indexes , what you are doing is you are still finding pqj 💀 💀

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Is E solved by observing numbers of divisors is relatively little(milion or so cause max 20 diferent primes in numbers) and then searching through primes?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with my solution for problem C? 190408656

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Test Case
    1
    5
    4 1 5 3 2

    your output
    expected output
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In C what I did for every index I find the fine permutation till that then I will find the left portions towards left and right of the this range 3 1 2 4 5 here fine permutation of index 4 will be 3 4 and then in final permutation 1 2 should come on left of it and 5 in right so greedily we pick 2 and 5 first then 1 and 5 My submission https://codeforces.net/contest/1792/submission/190407907

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Why so many hacks of B? Is there any edge case?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    I think people are simulating it, which is too slow. Most of the hacks are TLEs.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it's becaues of the $$$1e18$$$ upper limit of $$$a1,a2,a3,a4$$$, which causes the TLE

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      You scared the heck out of me when I read 1e18 because I used ints in my program, but thankfully I rechecked the constraints and saw that they were 1e8.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        oops, I guess I misread it xd, anyway it will still TLE regardless

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Am I the only one who solve problem D with trie and later see that it has an easy solution?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I used a trie too, I found it to be somewhat intuitive. What's the easier way?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You are not alone bro.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    yeah I firstly thought of trie but then realised that a map would just suffice because of the low constraints.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone give a failing TC for this submission of Problem B?

190391460

Thanks.

Upd: Found the TC.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +53 Vote: I do not like it

F1 can be cheesed since $$$n$$$ is small and the answer is required modulo a fixed number, You can pre-compute the answers in $$$O(n ^ 3)$$$ and copy the array into your code.

My solution 190420429

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Yesterday I was practicing hashing, but I tried to don't think biased and made a solution with custom sorting and binary search in D :)

My solution
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

D was really standard...even using simple map for counting will pass for me C>D

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

I passed E in 15 minutes after the match,it didn't seem like a difficult problem,what a pity

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I understood that problem D can be solved by trie, and I was having some difficulty so I looked at some submissions. I see that many people have implemented trie (or something similar) using map. Can anyone explain the logic behind the implementation?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

any hints for D

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

C can also be solved using DP: 190339025

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what's the meaning of vector d and statues shifting funcion

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      $$$d_i$$$ means the length of Longest Continious Subsequence ($$$...,i-2,i-1,i$$$) (End with number $$$i$$$)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh this $$$O(n)$$$ is better than std's $$$O(n\log n)$$$ :)

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Hi guys if you are still stuck on the problems or want a editorial on it you might wanna check this out: https://youtu.be/TOotS4TDzTI

happy coding!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Bad F due to oeis.org/A006351.We can search exsamples+2 to get this

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    how is that related to the problem, ur solution to the problem (F1) doesn't use the formula mentioned in the link, how could someone possibly use it ?

    also i dont think someone possibly would search first two samples + 2 in oeis and if so, it displays 316 results found, i dont see any reason calling it "Bad" because of such a reasoning.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i dont think someone possibly would search first two samples + 2 in oeis

      Several participants did search the answers for $$$n$$$ between $$$1$$$ and $$$4$$$, found the formula, and had their solutions accepted. Moreover, one could find these values with simple combinatorial considerations.

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      look at this: a(1) = 1; a(n) = a(n-1) + Sum_{k=1..n-1} binomial(n-1,k) * a(k) * a(n-k). — Ilya Gutkovskiy, Aug 28 2020

      use this recursive, we can solve F1 and then the recursive is a convolution, while module is 998244353, which means it is easy to brainstorm NTT. And let me tell you why I searched answer+2. the problem said that at least one edge should be painted as red/blue, that means when n>=2, there are two illegal answer(all red or all blue) being removed, while n=1, one illegal answer(no edge) will be removed, so let's search 1,2,8,52(see samples) in oeis.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

hope to get green

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

About E.Divisors

Does this problem have too strict time limit?This is my solution https://codeforces.net/contest/1792/submission/190443658 and it has been hacked for 3 times, I think this problem may need to have more loose time limit like 4 seconods.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There are some better solutions that don't iterate over divisors of every single divisor of m. See this. Also your code is T^2 (T is the number of divisors of m), which is even worse...

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The question is, you only need to make a few changes to your code to pass all testdata.

    I raised my question here , but still no one answered.

    vector<ll> s3;
    for (const auto &x1 : s1)
        for (const auto &x2 : s2) s3.push_back(x1 * x2);
    sort(s3.begin(), s3.end());
    s3.erase(std::unique(s3.begin(), s3.end()), s3.end());
    int ans1 = 0, ans2 = 0;
    for (const auto &x : s3) {
        for (auto pos = std::lower_bound(s3.begin(), s3.end(), (x + n - 1) / n); pos != s3.end(); ++pos)
            if (*pos > n or *pos * *pos > x) break;
        elif (x % (*pos) == 0) {
            ans1++, ans2 ^= *pos;
            break;
        }
    }
    
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We knew about such solution and it passes. We suspect that either the number of divisors is small (so $$$divs(m)^2$$$ is fine) or divisors are "packed" close, so it's near enough.

      Add here that divisors, you actually need to find their own divisors, are in the segment $$$(n, n^2]$$$. So if $$$n$$$ is big, many divisors $$$\le n$$$. If $$$n$$$ is small, many divisors $$$> n^2$$$.

      Anyway, we decided that it's okay if some participants gamble and get AC.

      P.S.: Even so, you need to write it accurately enough.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I'm not saying that a naive solution needs no skill. I'm saying that, such solution needs obviously less skill than people always expect for E.

        If you attribute my not_pass to my cowardice or bad strategy, that's right.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In addition, the naive solution is not only "near enough", but far more.

        I found all factors during the contest. Now I added two for-loops. Guess what, it costs 156 ms only.

        156 ms

        If you say that this solution requires some advanced mathematical knowledge, which you had already used to prove the time complexity, so this solution can be an alternative. I would blame me for my lack of knowledge.

        But you said otherwise. Emm... whatever, it was history.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks,i will write it more detailed soon

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      OK,i will try it soon,thanks so much

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

There will be only 6 hrs before next round begin. Maybe the rating update of the next round will be earlier than this round.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wait.

    System Testing is running.

    After system testing everything will be fine.

»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

When will the Editorial be published ?

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

This is to address the concerned authorities about my submission 190353992, which got skipped because the system considered it similar to another submission by BoosterImpulse , submission id 190386013.

I think the major reason why these 2 codes appear similar, is because of the use of a template of MOD INT (MINT), which I have used many times in my code and is clearly written before the contest and you can clearly see my code is completely different from the other person's code, my code is a normal implementation of two pointers. You can also check the timings of the submission and other persons' submissions. Please look into this matter as soon as possible cause I will become an expert if my solutions are been judged fairly. awoo BledDest Neon MikeMirzayanov adedalic

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes I too am pretty confused as to why the solutions are plagiarised.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Rating updated :D

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the editorial be published?

»
21 month(s) ago, # |
  Vote: I like it +79 Vote: I do not like it

System said that I cheated but I did not.

wsyear/190368291, LXH-cat/190370101 we used a similar template of modint and checked oeis to find a formula:

a(0)=0, a(1)=a(2)=1; for n >= 2, a(n+1) = (n+2)*a(n) + 2*Sum_{k=2..n-1} binomial(n, k)*a(k)*a(n-k+1).

With the same formula, our codes are similar.

The code that I used modint before this contest.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi my submission 190325251 is said to coincide with submission 190323813. I believe the logic to this problem is very straight forward and the solve() template we both used is very standard. Any of my previous submission uses a similar template + style and I believe this is just a mistake from the automated plagiarism checking system. Please update I dont want to be flagged for cheating :(

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

IMO the problems were great. I enjoyed thinking about and solving them. Also I got caught on the special case for B (a1 == 0) haha.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Through this comment, I want to address the cheating charges levied on me and Numinous , for having a coinciding solution to problem C in Educational Round 142. The submissions are 190386013 and 190353992. The reason for getting plagiarised was having a similar template, going through solve function for both speaks out the difference clearly. I hereby in my humble opinion ask MikeMirzayanov Neon BledDest adedalic vovuh awoo to provide us justice and the ratings we deserve . Thank You for your time and effort .