Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

By awoo, history, 9 months 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

»
9 months 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

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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

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

        You can consider hacking as Debugging practice

        • »
          »
          »
          »
          »
          9 months 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.

          • »
            »
            »
            »
            »
            »
            9 months 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.

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

        Solving one more problem would always benefit more lol

        • »
          »
          »
          »
          »
          9 months 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.

          • »
            »
            »
            »
            »
            »
            9 months 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

      • »
        »
        »
        »
        9 months 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.

    • »
      »
      »
      9 months 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

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

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

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

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

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

Hoping to become pupil again

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

    very true pfp XD

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

    Hoping to become specialist...and very relatable pfp...

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

As a participant, I wish you good problems

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

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

»
9 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Finally a contest! Can't wait

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

Educational Codeforces Round 5

»
9 months ago, # |
  Vote: I like it -16 Vote: I do not like it

finally, Contest after a long wait!!

»
9 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Hoping to have a wonderful round and becoming a specialist again

»
9 months ago, # |
  Vote: I like it -35 Vote: I do not like it

When the editorial will be published? Amazing round!

»
9 months 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!!

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

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

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

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

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

    its a system used to prepare the problem set

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

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

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

.

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

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

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

it is a palindrome round 101

i hope it be easy :D

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

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

»
9 months 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"

  • »
    »
    9 months 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!!

  • »
    »
    9 months 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.

  • »
    »
    9 months 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

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

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

»
9 months 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.

»
9 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Yet another div 1 round in disguise

  • »
    »
    9 months 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

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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

      • »
        »
        »
        »
        9 months 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.

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

Questions of this round to me:

»
9 months 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

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

(After contest) How do you solve D?

  • »
    »
    9 months 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

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

      Brilliant, thanks for it!

    • »
      »
      »
      9 months 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.

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

        sqrt(n) works too

        code
        • »
          »
          »
          »
          »
          9 months 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.

    • »
      »
      »
      9 months 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

      • »
        »
        »
        »
        9 months 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.

      • »
        »
        »
        »
        9 months 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.

      • »
        »
        »
        »
        9 months 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.

    • »
      »
      »
      9 months 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 :(

  • »
    »
    9 months 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).

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

how to solve c ??

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

    how to understand c (english)?

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

    like a chain fall down (QAQ

  • »
    »
    9 months 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])

  • »
    »
    9 months 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;
           }
       }
    
  • »
    »
    9 months 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$$$.

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

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

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

        Then it's impossible. I set

        Unable to parse markup [type=CF_MATHJAX]

        and $$$l = max(H[i], l - k + 1)$$$. In that, case $$$h < l$$$ so we output NO.
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When the editorial will be published? Amazing round!

  • »
    »
    9 months 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.

»
9 months 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

  • »
    »
    9 months 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.

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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?

»
9 months 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.

»
9 months 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

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

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

  • »
    »
    9 months 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

  • »
    »
    9 months 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.

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

    prefix sum

  • »
    »
    9 months 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...

  • »
    »
    9 months 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

  • »
    »
    9 months 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

    • »
      »
      »
      9 months 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

»
9 months 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

  • »
    »
    9 months 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)

    • »
      »
      »
      9 months 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 ?

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

D was easier than C

»
9 months 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.

  • »
    »
    9 months 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

»
9 months 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.

  • »
    »
    9 months 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

  • »
    »
    9 months 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.

  • »
    »
    9 months 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.

  • »
    »
    9 months 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.

  • »
    »
    9 months 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

    • »
      »
      »
      9 months 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)

      • »
        »
        »
        »
        9 months 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.

»
9 months 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

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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 :(

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

        Hashing, Suffix Array

        Queue go brrr: code.

        • »
          »
          »
          »
          »
          9 months 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

          • »
            »
            »
            »
            »
            »
            9 months 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.

      • »
        »
        »
        »
        9 months 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)$$$.

        • »
          »
          »
          »
          »
          9 months 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!

          • »
            »
            »
            »
            »
            »
            9 months 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.

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

      Making fun of less rated participants is not helpful.

      • »
        »
        »
        »
        9 months 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.

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

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

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

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

»
9 months 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

  • »
    »
    9 months 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 .

»
9 months 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?

  • »
    »
    9 months 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.

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

      Got it, thanks for the great problem.

»
9 months 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

  • »
    »
    9 months 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.

»
9 months 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?

  • »
    »
    9 months 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$$$.

    • »
      »
      »
      9 months 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!

    • »
      »
      »
      9 months 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

»
9 months 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.

»
9 months 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

»
9 months 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.

  • »
    »
    9 months 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

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

    I did it that way and got accepted :)

  • »
    »
    9 months 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).

  • »
    »
    9 months 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$$$

  • »
    »
    9 months 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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
9 months 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

(()?

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

    The input should contain exactly one ( and one )

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

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

    • »
      »
      »
      9 months 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.

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

102622037 How to reduce memory here?

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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

»
9 months 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.

»
9 months 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 ??

  • »
    »
    9 months 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**)

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

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

»
9 months 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.

»
9 months 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?

»
9 months 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.

»
9 months 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

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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 ;)

»
9 months 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"?

  • »
    »
    9 months 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..

  • »
    »
    9 months 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.

  • »
    »
    9 months 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 .

»
9 months 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 ')'

»
9 months 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;

»
9 months 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.

»
9 months 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.

  • »
    »
    9 months 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.

»
9 months 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..?

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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.?

      • »
        »
        »
        »
        9 months 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.

  • »
    »
    9 months 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

»
9 months 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

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

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

»
9 months 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...

»
9 months 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 :)

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

    Edit: Wrong

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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 :(

»
9 months ago, # |
  Vote: I like it -47 Vote: I do not like it

My very first comment on CF pls don't downvote

  • »
    »
    9 months 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.

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

Parade of Invalid input in A XD

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

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

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

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

»
9 months 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

»
9 months 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

»
9 months 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!

  • »
    »
    9 months 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 ')'

    • »
      »
      »
      9 months 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...

      • »
        »
        »
        »
        9 months 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.

»
9 months 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 )

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

    question could be framed in a better way...

  • »
    »
    9 months 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

»
9 months 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

»
9 months 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.

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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}$$$.

      • »
        »
        »
        »
        9 months 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

        • »
          »
          »
          »
          »
          9 months 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).

          • »
            »
            »
            »
            »
            »
            9 months 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!

    • »
      »
      »
      9 months 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

»
9 months 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.

»
9 months 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.

»
9 months 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 )

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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 ??

      • »
        »
        »
        »
        9 months 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 ?

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

What's the famous hack for E?

  • »
    »
    9 months 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

  • »
    »
    9 months 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.

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

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

»
9 months 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 >_<

»
9 months 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!

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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!

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

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

      • »
        »
        »
        »
        9 months 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.

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

How to solve E by SAM? :-(

  • »
    »
    9 months 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 :)

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

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

    • »
      »
      »
      9 months 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.

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

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

  • »
    »
    9 months 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.

»
9 months 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?

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

please post solution of this contest

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

my code What's wrong with my code?

»
9 months 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

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

I think educational rounds improve my implementation and fast solving.

»
9 months 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?

  • »
    »
    9 months 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.

  • »
    »
    9 months 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
    
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
9 months 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

»
9 months 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!

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

Sorry, got the statement my bad!

For 1469A - Regular Bracket Sequence

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.

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

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

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

Why doesn't the system test start?

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

Magic moment

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

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

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

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

  • »
    »
    9 months 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)

»
9 months 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.

  • »
    »
    9 months 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).

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

Hi ! Good job. When will the ratings change ?

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

When will the rate change take place ?

»
9 months 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?

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

How long will it take to update the ratings?

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

editorial please ?