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

Hello Codeforces!

On Dec/28/2020 17:35 (Moscow time) Educational Codeforces Round 101 (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 Roman Roms Glazov, 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!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 jiangly 6 121
2 Geothermal 6 138
3 neal 6 138
4 kotatsugame 6 165
5 tute7627 6 177

Congratulations to the best hackers:

Rank Competitor Hack Count
1 dorijanlendvaj 72:-13
2 star_xingchen_c 56:-1
3 ubc_123 26:-5
4 yash_daga 21
5 lsantire 20:-2
321 successful hacks and 593 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A WuBullMe 0:01
B Geothermal 0:02
C I_love_Tanya_Romanova 0:08
D abc864197532 0:12
E Kerim.K 0:18
F jiangly 0:42

UPD: Editorial is out

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

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

What the meaning of Educational rounds? I think that the meaning is hacking education, this contests teach to hack

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

    It teaches how to understand someone else's codes,, which is very important part of learning CP.

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

      Why it's important? I did hacking in Educational 1-2 times

      I think that one of most important — write code fast and without bugs

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

        You can consider hacking as Debugging practice

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

          Debugging others people's code improves your debugging skills.. I love Educational Rounds because they always teaches new concepts.

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

            Hey guys, nobody is here to ask for your philosphies.Plz plz stop spamming.U want to sound cool, become red.Relevant things kept at the bottom while only irrelevant thing is at top.plz consider it.

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

        Solving one more problem would always benefit more lol

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

          It varies from time to time. Sometimes a few minutes before the contest end, even high rated coder try to hack instead of solving one more problem. Because they guess it's not enough time to solve the last harder problem. So, they try to increase some points. And, the educational hacking phrases can be practice for the fruitful use of those few minutes.

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

            Yeah I mean he/she is just being salty, not thinking of improving but just complaining

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

        one of the things that improves your debugging skill is the debugging of other people's code.

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

      Pupil comments something: 8 downvotes (as of posting this comment)

      Red comments the same thing: 49 upvotes (as of posting this comment)

      LOL

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

I hope it is easy enough to change the rank:):)

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

Last Educational for the year. Ah,may it be really exciting . :D

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

Hoping to become pupil again

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

As a participant, I wish you good problems

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

2 points to master. I expect to become orange to New year

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

Finally a contest! Can't wait

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

Educational Codeforces Round 5

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

finally, Contest after a long wait!!

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

Hoping to have a wonderful round and becoming a specialist again

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

When the editorial will be published? Amazing round!

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

Today is my birthday. I hope to reach specialist. Wish me guys!! And I wish all the best for all those giving this contest!!

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

Midsems going on have not practiced since weeks , lets c what happens !!

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

is Polygon is a different site like codeforces?? i dunno about that

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

    its a system used to prepare the problem set

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

This rounds are easy and difficult i like that Good!!

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

.

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

I hope this contest will be easier than the previous one)))

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

it is a palindrome round 101

i hope it be easy :D

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

last round of this decade...want to give our best...

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

Excited for the round. Aiming for green. Hope it will be really "educational"

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

    please change your profile picture first , why u put such profile pictures on a platform like codeforces it doesn't make sense at all , please change it!!

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

    MikeMirzayanov can you please ban this guy? He has had this profile pic for months now.

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

    does it even matters whatever profile picture it is unless it's NFSW, which this one is clearly not, Be a bit tolerant to other cultures and choices

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

      It looks pretty NSFW, especially the smaller version...

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

My last comment was removed by the CF admins .This is very wrong ..u cannot supress my voice.

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

Yet another div 1 round in disguise

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

    First 4 problems look like not less 1700 of difficulty. Quite easy round

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

      Could you please explain how to solve problem C (without dp transition)? It took me more than an hour just to even understand the theoretically implausible picture of the problem.

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

        Keep minimum and maximum y-coordinates of the bottom of next section, based on current altitude and previous minimum and maximum values

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

        You store maximum and minimum height for a segment to be added to the prefix.

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

Questions of this round to me:

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

does the hack make u increase in ur points in the edu rounds

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

(After contest) How do you solve D?

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

    This is how I did it — First make all the numbers from 3 to n-1 (excluding 8) 1 by the operation "i n" (where 3 <= i <= n-1 and i not equal to 8). Now transform n to 1 by the operations "n 8". Finally make 3 "8 2" operations to transform the 8 to 1.

    The first step would take n-4 operations. The second step would take at most 6 operations and the final one would take exactly 3 operations. (n-4) + 6 + 3 = n+5

    To see that the second operation would take at most 6 operations, note that n is at most 2e5 < 2^18

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

      Brilliant, thanks for it!

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

      really nice solution, i was trying using sqrt($$$n$$$) instead of 8 and the operations were exceeding $$$n$$$ + 5.

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

        sqrt(n) works too

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

          yeah, it's working because of ceil which i figured out later, floor won't work or maybe i made a mistake while calculating operations.

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

      How did u decide on 8? I was thinking of 64 and 128 but the operations were exceeding n+5

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

        Well, I sequentially tried 2, 4 and then 8 and then 8 worked for me so I stopped there.

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

        64 actually doesn't exceed n + 5, it's worst case is actually exactly n + 5, but 128 does exceed the bounds.

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

        you can take any number x less than n (say,x=32 here) then net operations will be n-4+log(n to base x)+log(x to base 2) (here you should use ceil of log function ) So, its better to choose x as power of 2.

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

      I thought of this, but I did not have time to implement it and it seemed a bit hacky :(

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

    If n<=32, divide every number from 3 to n-1 with n and then continuously divide n with 2 until it becomes 1.

    if n>32, divide every number from 3 to n-1 except 32 with n and continuously divide n with 32 until it becomes 1 and then continuously divide 32 with 2 until it becomes 1.

    When I said divide 'a' with 'b', I meant ceil(a/b).

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

how to solve c ??

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

    how to understand c (english)?

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

    like a chain fall down (QAQ

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

    Keep maximum and minimum possible heights of sections, or rather the y-coordinates of their bottom. Let's call minimum coordinate d and maximum coordinate u. For section i it's possible to choose y-coordinate in segment [max(a[i], d-k+1); min(u+k-1, h[i]+k-1)] where h[i] is height of place for i-th section. Then d = max(a[i], d-k+1) and u = min(u+k-1, h[i]+k-1)

    Don't forget that the last section must lay on land (coordinate y=a[n-1])

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

    Something like that, create the low and high boundary and check for rules

       low[0] = high[0] = ground[0];
    
       bool good = true;
    
       for (ll i = 1; i < n; i++)
       {
           low[i] = max(low[i - 1] - k + 1, ground[i]);
           high[i] = min(high[i - 1] + k - 1, ground[i] + k - 1);
    
           if (high[i] < low[i]) {
               good = false;
               break;
           }
       }
       if (good) {
           if (ground[n-1] < low[n-1] or ground[n-1] > high[n-1]) {
               good = false;
           }
       }
    
  • »
    »
    3 weeks ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    Calculate the highest possible (fence $$$k - 1$$$ from ground or last fence) and lowest possible (fence on ground or $$$k - 1$$$ below last fence) height for the bottom of the fence at each position, using the highest and lowest possible height for the previous position. At each position we should have $$$h >= l$$$, and also in the last position we should have $$$l = H_n$$$.

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

      what if the Hn is higher tan r[n-1]+k-1 ?

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

        Then it's impossible. I set $$$h = min(H[i] + k - 1, h + k - 1)$$$ and $$$l = max(H[i], l - k + 1)$$$. In that, case $$$h < l$$$ so we output NO.

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

When the editorial will be published? Amazing round!

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

    After 1 day most of the time . But till then most of the solution would have been discussed here.

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

I didn't manage to code it, but I know how to solve E with Suffix Array. You start by inverting the input string. What you want is the mex of all substrings of size k. After sorting the suffixes, there is a lemma that says that on average, adding one to a binary string does 2 operations. By using these, you can solve the problem

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

    Suppose n=k=3 and s=111, you're saying the answer is mex({111}) = 000?

    Edit: I missed "invert the input string"; should be mex({000}). Nice solution.

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

    Another way:

    Let m be the smallest integer such that 2^m > n+1-k (number of substrings). Consider last min(m, k) inverted bits of every substring; select smallest unused mask.

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

      Well yes, but I think you still have to check that all prefixes of the substrings of length k are equal to 0 up to the value of that unused mask.

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

        Yes, I forgot to mention that a substring can be skipped if the first k-min(m, k) bits aren't all 0 (after inversion).

        Code: 102623431

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

    I solved E using string hashing.

    Create an empty set "se" of data type <pair<long long, long long> >, and store the hashes of complements of all substrings of s of size k in se.

    For each substring, one hash corresponding to modulo 10^9+7 and one corresponding to 10^9+9 are stored as pair elements. This can be done in O(n) if we keep using the hash of the complement of the previous substring while iterating from 1st to last substring of size k.

    Now in set "se", we have the hash pairs which our result string t cannot take. These elements are at most n-k+1. So, if we start constructing t by iterating from 0 to n-k+2 in binary form, we will get the answer in at most n-k+2 operations. While iterating from 0 to n-k+2, the first binary string t whose hash pair does not match any pair element from the set is the answer.

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

      I haven't understood the last part (i.e. how to find t from the set se), can you explain it in a detail?

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

Anyone know what test 83 of E is?

Edit: Got it, suppose $$$n = 10^6$$$, then our check length for the mask will be 20 bits. While we may think of checking all subarrays [x — 19, x] for $$$x \geq 20$$$ is the logical one to find all subarray end masks, the mask generated by any subarray checked before $$$[k - 19, k]$$$ where $$$(k \gt 20)$$$ will never actually be at the end of any subarray and shouldn't be counted as a mask that need be satisfied for bit similarity.

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

Can someone point out the error for my submission for Problem C ?

102615036

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

How to solve B ?Is there a dp solution for it?

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

    Find the max prefix in array 1 and array 2 and just output its sum

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

    Just try paring each prefix of R and each prefix of B (two for loops) and sum the prefixes up. Update the best solution as you do this.

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

    prefix sum

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

    Oh I have solved it in that way ,but I have missed that it can never be less than 0.God damn it...

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

    Yes, there is a solution using dp.

    The problem can be described as: Find the prefix that has the largest sum in an array that can be formed through two other.

    Therefore, we can make a dp[i][j], with i the index of array r and j the index of array b.

    In a dp state, we have two options:

    1- add r[i] to the array and increment i. 2- add b[j] to the array and increment j.

    if I have already pre-calculated dp[i][j] before, I can stop because the answer for the remaining suffix has already been calculated.

    My code: https://codeforces.com/contest/1469/submission/102568792

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

    You can solve B using a greedy algorithm, take the max prefix sum of blue and max prefix sum of red. You can be sure it will always work because you want to maximise sum of a prefix of list a. You also know that orders of b and r are fixed so taking the maximum prefix sum of those lists will always be optimal There also exist a (much slower) dp solution which I coded https://codeforces.com/contest/1469/submission/102569441

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

      I spent 50 minutes trying to code up the the dfs solution and in the end it didnt work. Looked your comment cretaed the solution in literally 5 minutes and it got accepted. Its worth thinking I have to say :D

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

I tried to solve C by creating minimum and maximum starting position for next section . Could some one help me where i am wrong . Submission

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

    Line: l = max(a[i]+1-k-(k-1),0LL);

    in your loop the minimum starting position depends on reachable minimum of last block, not a[i]+1-k (it may be not reachable)

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

      Before that i have checked if a[i]>l .Now if a[i]>l then we can use that formula right ?

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

D was easier than C

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

you people can never make good problems how is this round educational? No DP/ graph till 4th. question. Please change the name of these rounds as Adhoc-edu rounds.

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

    Well, you can solve B with dp, and one of the approaches to C is to consider dp solution and get rid of the second state

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

What is the intuition behind D? I thought of divide and conquer but couldn't think of a good solution.

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

    I worked on 8 and n. You can make all numbers (except 1 2 8 and n) 1 using i and n. By 6 operations at most by using 8 and n, you can turn n into 1, and 3 operations are needed to turn 8 into 1 by using 2 and 8. So n-4+9 operations would take it to solve

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

    I'm not sure that this will pass systests, but I did something like for all values i from ceil(sqrt(n)) to n choose indices i, n, so they are now 1. Then choose indices n, ceil(sqrt(n)) two times, so n is now also 1. So, we reduced the problem to the same but ceil(sqrt(n)) instead of n, now repeat the process until all except 2 are ones.

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

    mark 5 visits as 2 4 16 256 65536 n assuming n>65536. you can see that leaving this 5 pointers you need n-5 operations. and you can convert them to 2 1 1 1 1 in 10 operations thus total n+5 operations.

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

    I did the following, for all numbers in the range 3 to n — 1 that are not powers of 16, perform the operation $$$(i, i + 1)$$$.

    If there are $$$k$$$ powers of 16 less than $$$n$$$, this will take $$$n - 3 - k$$$, where $$$k \leq 4$$$ (as $$$2 \times 10^{5} \lt 16^5$$$ = $$$2^{20}$$$). Now, consider the sequence $$$16^1, 16^2, \ldots, 16^k, n$$$, we divide each term by the previous one, now each of these numbers are at max $$$16$$$ and we have used $$$(n - 3 - k) + k$$$ = $$$n - 3$$$ operations and have 8 operations left.

    We have a $$$2$$$ (at $$$i = 2$$$), $$$k + 1$$$ numbers which are at max $$$16$$$ and the rest are $$$1$$$.

    Now lets divide $$$k$$$ of these $$$k + 1$$$ numbers by the first $$$16$$$, making them all $$$1$$$. Now we have used $$$n - 3 + 4$$$ = $$$n + 1$$$ operations, and have $$$n - 2$$$ $$$1s$$$, one $$$2$$$ and one $$$16$$$, we can now use the remaining $$$4$$$ operations to divide $$$16$$$ by $$$2$$$ four times and get the required sequence.

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

    Keep 1 and 2 as it is. Now let's convert all but Nth, 1st, and 2nd element to 1, by dividing by Nth element.
    That's N — 3 moves, with 8 moves remaining. Notice that 2 * 10^5 cannot be reduced to 1 with 8 divisions by the second element.
    Observation: Any number can be made 1 by 2 divisions using ceil(square-root). Lets keep 1st, 2nd, p1, p2, and N elements and make everything else 1, where p2 = ceil(sqrt(N)) and p1 = ceil(sqrt(p2)).
    That's N — 5 moves. N can be made 1 with 2 divisions by p2, and p2 to 1 by 2 divisions of p1.
    Now the total moves = N — 5 + 4 = N — 1.
    Note that p1 is atmost sqrt(sqrt(200000)) = 22.
    22 can be made 1 by 5 division of 2.
    Total moves = N — 1 + 4 = N + 4

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

      Thanks, well explained! But I wonder why were you changing array elements(except p1&p2) in your solution which I guess was not required. Any reason? (Just curious)

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

        I had used it to run verifier for first 10k [1 to 10000] and last 1000 [2*10^5-1000, 2*10^5] using asserts. You can refer to the commented code for the verification.

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

Was C a DP problem? It looked like it at first but none of the top solutions have used DP

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

    One of the approaches is the following: let $$$dp[i][j]$$$ be true if we can place first $$$i$$$ sections so that the $$$i$$$-th of them is on height exactly $$$j$$$, and false otherwise. The number of states in it is too much, so we need to improve something.

    It can be proven that for every $$$i$$$, the values of $$$j$$$ such that $$$dp[i][j]$$$ is true form a consecutive segment (possibly empty, then there is no answer). So we can get rid of the second state and rewrite the solution as $$$dp[i]$$$ — the segment of values of $$$j$$$ such that the original $$$dp[i][j]$$$ is true.

    It's just a sketch of the solution, we will provide a more thorough explanation in the editorial.

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

      Bruh is the official solution to E hasing? I had suffix array but didn't manage to code :(

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

        Hashing, Suffix Array

        Queue go brrr: code.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it
          char c;
          cin >> c;
          if(!(c & 1))
          

          you genuinely know/searched for the ascii code of '0'. Nice

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

            Lol I learned some cute tricks like that from reading tmw's code too often.

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

        The official solution doesn't use any string algorithms.

        The idea is the following: there is always an answer when $$$k \ge 20$$$ (each substring of length $$$k$$$ forbids at most one string from being the answer), so we are interested in at most $$$20$$$ last characters of the answer (all others can be zero). I check each substring of length $$$20$$$ and determine which combination of last characters it forbids from being the answer (be careful: there may be zeroes before these $$$20$$$ characters in $$$s$$$, and it may mean that this substring actually doesn't forbid anything since the prefix of the answer will contain $$$k - 20$$$ zeroes). I have marked some combinations of last characters as forbidden, so all that's left is to find the minimum unforbidden combination.

        The implementation I provided is a bit different since I use something like $$$\lceil \log_2(n - k + 2) \rceil$$$ instead of $$$20$$$. It runs in something like $$$O(n \log n)$$$.

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

          I understand. To check if the first n — k — 20 characters are '1' I am guessing that you are using hashes. Thank you!

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

            No need for hashes, just precalculate the closest position of $$$0$$$ to the right/left of each index.

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

      Making fun of less rated participants is not helpful.

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

        I didn't make fun, it is the exact way I approached this problem when I first heard about it.

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

      Plz explain dp solution also in detail in problem C editorial.

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

Any ideas of problem c ?if yes plz share with brief explanation

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

The solution for ques A was already uploaded on Youtube while the contest was going on. This is very unfair with those who seriously give the contests. It should be made unrated.

https://www.youtube.com/watch?v=iiCJIBGaqhk

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

    No one can do anything about that . Stop searching solution on youtube or ignore if it's published on web during the contest .

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

Why there is always a soultion in $$$E$$$ for $$$k > 20$$$??? I have seen many solutions use this and couldn't understand why?

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

    Each substring of $$$s$$$ having length $$$k$$$ forbids us to use its inverse as the answer (so, it forbids at most one string from being the answer to the problem). When $$$k = 20$$$, there are $$$2^{20}$$$ different strings that we may try as the answer, and that's why it always exists.

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

      Got it, thanks for the great problem.

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

this guy uploaded answer for question A while the round was still going on https://youtu.be/iiCJIBGaqhk

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

    It looks like he tried to ruin the contest but he was only able to solve problem A lmao. But still, hope he got banned, I guess it's possible for hosts to search the same code and find this guy.

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

What the fuck is the testcase #43 in E and how did it fucking kill my solution?

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

    It is constructed in the following way: we have a binary number $$$111\dots11$$$ (exactly $$$200$$$ ones in this test, but there are other tests with different length of this number). The string $$$s$$$ starts with it. Then, we decrease this number by $$$1$$$ and append it to the right of $$$s$$$, then decrease again by $$$1$$$ and append again, and so on, until the length of $$$s$$$ becomes $$$10^6$$$.

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

      The fact that you are responding to so many comments is really helpful. Thank you!

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

      Thanks a lot! Found a stupid bug in my code and I'm just dumbass

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

I tried to solve problem C by storing maximum height a block can go and minimum height which is required ,can someone tell me where I am wrong. these is my solution.**Please help me** I still can't get it.

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

Could please anyone suggest what I'm doing wrong in this for B. 102616928

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

Problem D: I see many different submission for D. Has anyone else also done by taking square root repetitively? I think it will pass, as repetitively square rooting should not take more than 5 rounds, not sure.

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

    hey, I tried this but either the approach doesn't work or my code has a bug: 102619406

    edit: whoops i'm an idiot/it's too early in the morning... I was doing everything in reverse order

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

    I did it that way and got accepted :)

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

    Yes, I did that too. Our solution will take just n+3 moves. (Maximum).

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

    Square root method should pass worst case is you get $$$[65537,257,17,5,3,2]$$$ or $$$[200000,448,22,5,3,2]$$$. Let $$$|S|$$$ = no of elements in this sequence.

    no of operations = $$$n - 1- |S| + 2 * (|S| -1) = n + |S| -3$$$

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

    mark 5 visits as 2 4 16 256 65536 n assuming n>65536. you can see that leaving this 5 pointers you need n-5 operations. and you can convert them to 2 1 1 1 1 in 10 operations thus total n+5 operations.

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

I am trying to hack A , it shows this input is invalid how ?

1

(()?

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

    The input should contain exactly one ( and one )

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

      lol , didn't read that , solved it without that info

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

      In the question they could have mentioned it like this "there is only one character '(' and one character ')'"

      As they mentioned ( ) without '' I got confused and didnt understand that statement properly.

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

102622037 How to reduce memory here?

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

    You don't need to look at the whole string of length k, just the last 20 should be enough.

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

      Problems such as this can occur. 100000000000000000001 was the substring but we saved 000000000001 's occurrence and this cant become answer when it would have

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

D is one of the most beautiful question I have seen so far.

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

Please someone explain question 1. If ((() give YES as the answer then how ??

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

    Read question properly. (**There is exactly one opening bracket and exactly one closing bracket**)

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

If I would have got 10 more minutes, D was cracked

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

For problem D, did anyone else take just the indices n and ceil(n^((sqrt(5)-1)/2))? It works but there are a few corner cases. Head bashing that I didn't get the direct square root solution.

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

In problem C I found the max h[i] and then started seeing whether it works or not. Here is my submission. Can anyone help?

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

Was it just me , who didn't see the "exactly one" part in problem A, for a very long time.

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

Could anyone please explain why this code prints wrong output compared to my local execution environment? (Problem D)

http://codeforces.com/contest/1469/submission/102626247

input:
1
5

expected(local):
7
6 7
5 7
4 7
3 7
7 2
7 2
7 2

actual(codeforces):
7
4 7
5 7
6 7
7 3
7 3
3 2
3 2

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

    The test case you included is not incorrect. The incorrect test case occurs at test case 11, or n=13. After the first 9 steps, the array has become all 1's except [1,2,3,13] at indices 1,2,3,13. After step 10, the array is [1,2,3,5]. After step 11, the array is [1,2,1,5]. After step 12, the array is [1,2,1,3]. We still need 2 more steps to get the desired array, yet your response only has room for 1 more step.

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

      Thanks for the reply! Actually I misunderstood that 'Output' was an answer and 'Answer' was my output ;)

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

For problem A, what if there are at least one ( and at least one ) rather than "exactly"?

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

    i have solved considering that only because i didn't see exactly statment..

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

    One of our solutions to this problem is greedy: replace the first several "?" characters with "(", until we have enough opening brackets, replace all remaining "?" with ")", and check that the resulting sequence is an RBS. It should work if there are more than one opening/closing brackets.

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

    you can still solve for given constraint using brute force .submission . I didn't read that "exactly" during the contest and thus solved for at least .

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

invalid input during hacking for the problem A because string s have exactly one '(' and one ')'

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

If you got WA on test 2 and have no clue why, there's a chance you might have missed the second condition (at least I did):

the first and the last sections should stand on the corresponding ground levels;

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

the only Educational thing I learnt from problem A was to read problem statement again and again.

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

Why are people with rating >=2100 in the official standings? I wanted to see how I'm standing against other Div. 2 coders but I can't find a way to do it.

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

    After the hacking period is over , and the system testing is done , there will be a option in the standing page where you can choose div1 , div2 or both.

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

I'm getting Invaild input format while hacking a submission.

Is there any format which we have to follow..?

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

    You have to follow the format and the bounds in the problem statement. You may have forgot to include the number of test cases in the input, or maybe one of the numbers is greater than or less than what the problem statement allows.

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

      my input is in given range only..

      i'm giving like this below example:

      No. of test cases
      input
      

      That's it.!

      Do i have to provide expected output.?

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

        You don't need to provide expected output, but I would recommend you to read the problem statement again. For example, in task A you might have missed that there must be exactly one '(' and exactly one ')' in each test case.

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

    if you are hacking A problem then read the problem correctly string s have exaclty one '(' and one ')'

    if you are giving testcase as

    1 (((())

    then its wrong

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

Can someone tell mistake in my code of Problem C : 102622419 Got WA in test case 2

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

Actually I can't understand why this contest's called educational

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

It was written twice "**There is exactly one character ( and exactly one character )**" in front of my eyes.I can't believe that, still not noticed it carefully who else faced that...

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

Good contest, thanks to the organisers. Some tricky but interesting problems. I made a right mess of A! Disappointed not to get E due to TLE but I think I am one of many — I spotted the 'reduce K to 20' trick, but I think using pypy was my downfall, along with the (very) large limits — wasn't able to get my constant factor down enough for pypy. Also serves me right for not being good enough at C++ I guess :)

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

    Edit: Wrong

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

      Could you explain why? In my critical loop, I cannot see anything that evaluates 2^20 different options. I see O(N*20) for each test case, but we know that sum of N over all Q cases is capped to (about) 2^20, so if Q is large then it will not be doing anything like 2^20 calculations. I'm probably missing something — would be grateful if you could show me what that is.

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

        I checked again and looks like I miscalculated the complexity of your code. My bad :(

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

My very first comment on CF pls don't downvote

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

    okay, but what's the point of your comment ?? I asked a genuine doubt some other day and got downvoted.

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

Parade of Invalid input in A XD

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

    we all misread A didint see two brackets acquired exactly once :(

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

      they should have mentioned it in quotes. '(' and ')'

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

video tutorial for B number problem using dp . hope you guys will enjoy the explanation !!! link : https://www.youtube.com/watch?v=mxxVp-eZPYs

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

Here are some video solutions for all problems, with the added bonus of struggling with a writing tablet

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

In problem A on
test case: (((),
this guy's solution gives YES, whereas this guy's solution gives NO. And interestingly, both are ACCEPTED ..... Something FISHY! Don't KNOW!

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

    Not a valid test case. The inputs must have exactly 1 '(' and exactly 1 ')'

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

      Ooh the way the question is written is misleading then....

      And why different solution for same test cases...

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

        You can get different solutions for the same test case if the test case is invalid since one solution may not work for all inputs in general, but relies on an assumption that the restriction given guarantees.

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

Everyone who is trying to hack A's submissions, please note this -> There is exactly one character ( and exactly one character )

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

    question could be framed in a better way...

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

    Honestly I don't get how everyone is missing this, it's written in bold in the statement twice

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

D easy solution (for given constraints): If n <= 8: Go bruteforce Return;

From 3 to n-1 divide all by n except 8. (We are left with 2, 8, n)(n-4 operations) Divide n by 8 till it becomes 1 (at most 6 operations) Divide 8 by 2 (3 operations) Done. Finally, n-4+6+3 = n+5

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

Thanks for the problem D!
With my group of high school students, we routinely discuss solutions after Codeforces contests. This time, the three solutions we had for D were attacking the problem from different angles: repeated square root, a few powers of two, and leaving only two non-unity elements. Loved it.

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

    I honestly feel that was hardest problem in the round for me today! Took me like 30 mins to construct square root solution, but when I found that, was very beautiful. What are other approaches?

    Also surprisingly F was the easiest among D, E, F :( Sad I had only 5 mins left when started it.

    EDIT: Above comment shows the solution with 2, 8, n, which seems to be very nice and way simpler than mine.

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

      In every solution, we can destroy (reduce to 1) every element except the last in one operation, dividing it by the next element, or by the last element.


      The "few powers of two" solution is as follows:

      Suppose we leave $$$2$$$, $$$2^2$$$, $$$2^4$$$, $$$2^8$$$, and $$$2^{16}$$$ undestroyed. Then each of them except $$$2$$$ can be destroyed by the previous one in two operations.

      Now, take only those which are $$$\le n$$$, and substitute the last of them by $$$n$$$ itself. Then, $$$n$$$ can be destroyed in four operations, and all others still in two operations. Turns out it is enough.


      The "two non-unity elements" solution is as follows:

      Let us destroy all elements except $$$n$$$ and one other, $$$x$$$. The remaining problem is then to pick $$$x$$$ so that the pair $$$(x, n)$$$ can be reduced to $$$(1, 2)$$$ fast. The reduction is dividing the greater number by the lesser one until the pair becomes $$$(1, 2)$$$ or $$$(2, 1)$$$. For example, $$$(12, 5) \rightarrow (3, 5) \rightarrow (3, 2) \rightarrow (2, 2) \rightarrow (2, 1)$$$ takes four steps.

      Some pairs are too slow: $$$(200\,000, 2)$$$ requires 18 steps.
      Some pairs are plain bad: $$$(3, 9) \rightarrow (3, 3) \rightarrow (1, 3)$$$ never goes to $$$(1, 2)$$$.

      But for the good pairs, just how fast it can be? Let us follow the division process backwards:
      $$$(1, 2)$$$ can result from $$$(2, 2)$$$,
      $$$(2, 2)$$$ can result from $$$(4, 2)$$$ (or from $$$(3, 2)$$$, but let us look at the greatest possible value for now),
      $$$(2, 4)$$$ can result from $$$(8, 4)$$$,
      $$$(4, 8)$$$ can result from $$$(32, 8)$$$,
      $$$(8, 32)$$$ can result from $$$(256, 32)$$$,
      $$$(32, 256)$$$ can result from $$$(8192, 256)$$$,
      $$$(256, 8192)$$$ can result from $$$(2\,097\,152, 8192)$$$.
      So, in seven steps we have, we can destroy up to $$$n = 2^{21}$$$. Side note: the quantities are of the form $$$2^{F_n}$$$, Fibonacci powers of two.

      With some monotonicity and hopeful handwaving, every number less than $$$2^{21}$$$ is also covered. But by which $$$x$$$, exactly? As the $$$(3, 9)$$$ example above shows, we can't just pick any and hope for the best. Turns out we can find such $$$x$$$ by brute force: the number of steps for each $$$x$$$ to try to reduce $$$(x, n)$$$ to $$$(1, 2)$$$ is logarithmic at worst. So, the whole solution works in $$$O (n \log n)$$$.

      The fact that the solution exists for every possible $$$n$$$ up to $$$2^{21}$$$ I did not rigorously prove, but checked after the contest, in $$$O (n \log n)$$$ also, by two pointers on $$$n$$$ and $$$x$$$ going down. As the "best" possible pairs $$$(x, n)$$$ look like $$$(2^{F_k}, 2^{F_{k+1}})$$$, a value $$$x$$$ near to $$$n^\varphi$$$ fits, where $$$\varphi = \frac{\sqrt{5} - 1}{2}$$$.

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

        Nice explanation for the two non-unity elements solution. I found $$$x$$$ by guessing $$$x=\lceil{\sqrt{n}\rceil}$$$ but that took too many operations (200007 for $$$n=200000$$$) so I figured I wanted to balance it by putting more steps into dividing $$$n$$$ and less into dividing $$$x$$$. I figured a cube root might work so I went with $$$\lceil{x^{0.3333}\rceil}$$$ and that got (200005 for $$$n=200000$$$). 102597360

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

          Just realised my 2 element approach is slightly different from what you describe. It's actually a 3 element approach in most cases. I leave 2,x and n. Then repeatedly divide n by x until I get 1 followed by dividing x by 2 until I get 1 (unless x=2).

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

            Yeah, it's actually nice that the constraints deny the simplest ideas, like "leave 2 and n", but allow so many approaches to turn into actual solutions. Kudos again to the authors!

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

      My solution to D with thought process:
      * When you divide a smaller number by a bigger number you get 1
      * Say arr = [1, 2,..., n]
      * When we do {i, n} operations for every i, we get [1, 1, 1..., n]
      * But we want 2 at the end...
      * So, we will make operations {n, i} whenever we can.
      * Say we are at i (processing the numbers from n-1 to 1)

      while ceil_div(arr[n], arr[i]) >= arr[i]:
          arr[n] = ceil_div(arr[n], arr[i])
      

      I don't have a formal proof of this, but it is something on the lines of How many times do we square-root a number to get 2
      This is the code for above approach: 102649278

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

Here's my solution for problem A if we remove the constraint of there being exactly one '(' and ')'. https://codeforces.com/contest/1469/submission/102634522

Please let me know if there's anything wrong with the logic.

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

Nice contest! I recorded myself solving and explaining problems (only A-D today, so there is definitely a room for improvement), here is the YT link. Of course, there was a post-contest stream by Neal Wu with the discussion of the solutions, but maybe you will find my explanations useful as well.

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

I wanted to ask what is the meaning of There is exactly one character ( and exactly one character )

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

    In the string there will be only one '(' opening bracket and only one ')' closing bracket.

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

      like if length is 6 can you construct one test case for me ??

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

        )????(, This could be one , another (???)? , You will have to use exactly one ( and exactly one ) , and remaining should be ?

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

What's the famous hack for E?

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

    My guess is

    1. Solutions using hashing forgetting to use srand which leads to fixed seed giving WA due to collisions

    2. Using string set for hashing which is too slow

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

    I hacked the solutions (including yours :P) where while checking the last 20 characters of the substring people forgot to check whether the remaining all characters of that substring are zero or not.

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

      How did so many solutions pass 89 tests ?! Thanks for answering.

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

dorijanlendvaj is GOD!

the predictor says +43 for a account when the contest over,but +106 for that account right now.

Hope everyone won't FST >_<

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

Hello, everyone!

I found one submission for problem E which used a HASH algorithm, can you hack it? In fact, I wonder how to hack such HASH algorithms. If you know the way to hack it, please contact with me, thanks so much!

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

    As I know, there is no good way now to hack hash algorithms that use multiple large prime numbers.

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

      I also realized this problem after writing this comment some time.

      Anyway, thanks a lot!

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

      Unfortunately, the submission above which used a HASH algorithm has been hacked.

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

        I think it's probably because he's always using the power of two.

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

How to solve E by SAM? :-(

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

    If you flip all the numbers in the string, the problem is now to find the minimum string of size K that is not a substring of $$$S$$$. To do that, build the automaton of $$$S$$$ and just run a dfs trying to put a 0 first, and if that failed, try to put 1. If your path is already of length K, then this path is not valid (it is a substring of $$$S$$$). If at some moment, you try to put a digit and there is no edge labeled with that number going out from the current vertex of the automaton, you know that it's not a substring of $$$S$$$ anymore, so you just complete it with zeros and print it.

    Time and memory complexity is $$$O(n)$$$. Here is my submission :)

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

      Thanks for your reply! Now i know how to solve it. :-)

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

      Could you please provide a tutorial for SAM or whatever you mean by building an "automaton of S"?

      Thank you in advance.

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

How to approach A? I used stacks for it but got WA

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

    If the length of the string is odd, it's not possible. If the first character is ) or the last character is (, it's not possible. Otherwise you can show a solution exists.

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

For A, what would the method be if more than one character of ( or ) is allowed?

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

please post solution of this contest

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

my code What's wrong with my code?

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

it's really sad to see people getting hacked on E, including me XD

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

I think educational rounds improve my implementation and fast solving.

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

My submission for E fails at test case 92. I'm going through masks and printing the one with the least value that doesn't correspond to the last min(k, 20) bits of any of the k-length inverted substrings. Any clues?

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

    I do the same and also get WA in Test #92.

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

    I found my mistake, I didn't consider the leading zeroes. even if your solution gives some mask (not all zeros), a string with all zeros can still be the answer, because it might match with its zeros before the last 20 characters.

    Here's a test to reproduce the flaw:

    Test:
    Input:
    1
    100 80
    0000000000000000000000000000000000000001000000000000000000100000000000000000001111111111111111111111
    
    Expected output:
    YES
    00000000000000000000000000000000000000000000000000000000000000000000000000000000
    
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, you're right, I got it the next day. Thanks.

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

For C: I am checking for each fence [1,n-1] if it's in the range of adjacent fences range. The range of any fence i in [1,n-1] is [xi+1,xi+2*k-1] where xi is ground level of i. But I got wrong answer on test case #2. Can anybody help me figuring out why my approach is wrong.102616612

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

My first AK for Div.2 round. I am very happy. Thank you!

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

Sorry, got the statement my bad!

For 1469A - Правильная скобочная последовательность

In this problem (Edu Round 101- A) most people code doesn't consider below stated test case.

Can anyone explain why?

Test Case:

())(()

There is exactly one character ( and exactly one character ) in this sequence.

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

    Because the input should contain only one ( and only one ) brackets.

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

Why doesn't the system test start?

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

Magic moment

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

    Do you want to increase your friends by putting this comment?

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

      I wanna increase your contribution! It's very cold and frosty!

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

    U can open the contest status and use the status filter (found in the right-down corner of the page)

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

I tried looking at the solutions of others in the hope to learn about problems I couldn't solve(as I thought was a reason for educational rounds), but in solutions, it is really hard to find java codes, does standing have some feature to find java solution codes in standings, or if not I hope they make such option.

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

    For each problem, there's a "Solved" page (example: https://codeforces.com/contest/1469/status/A). Typically the solutions are ordered by size, which puts Java behind since it's verbose at times. But you can use the filter to the right, select "Verdict: Accepted" and "Language: Java 8" (or Java 11).

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

Hi ! Good job. When will the ratings change ?

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

When will the rate change take place ?

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

Is it normal that the results have not been announced yet?

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

How long will it take to update the ratings?

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

editorial please ?

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

All the problem set was so tricky!!!!!

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

When will the editorial come out? I believe there are many people waiting for it.