By pikmike, history, 2 months ago, translation, In English,

Hello Codeforces!

On Mar/23/2020 17:35 (Moscow time) Educational Codeforces Round 84 (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 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 Ne0n25 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 MiFaFaOvO 7 230
2 Volkov_Ivan 7 272
3 Egor 7 343
4 2829908231 7 360
5 rainboy 7 707

Congratulations to the best hackers:

Rank Competitor Hack Count
1 theStaticMind 14:-8
2 Chrollo_Lucifer 5:-1
3 Learner 10:-13
4 RitikBaid 3
5 Ashiok 4:-3
139 successful hacks and 617 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A fextivity 0:01
B Sonechko 0:05
C Isaunoya 0:05
D MiFaFaOvO 0:10
E Medeowex 0:11
F YangDavid 0:35
G rainboy 0:44

UPD: Editorial is out

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

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

good luck :D

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

    Only contest can keep us busy during quarantine. :)

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

      Actually thinking about when is the next contest does that ;)

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

        Apparently there are no div 2+ contests until April 3 :( So a long long (note the pun) 9 days wait.

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

          Was that pun INTended?

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

          I guess that pun cannot fall short.

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

          I think cf should double the contest frequency

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

            not double but 3 and i think there are more rated contest(i am a chinese)

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

            with no strings attached

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

          The 9 days will be void of any rating changes for me. :(

»
2 months ago, # |
  Vote: I like it -38 Vote: I do not like it

My Last contest the first time i solve two problems , and i solved them in less than 30 minutes, this contest i will solve at least three problems insha' allah :), Good Luck for all :).

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

    Inshaallah brother <3 Good luck you too

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

      I wish best of luck for you too <3 :) , Thanks brother <3 :)

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

    Lands up solving none , Better luck next time Bro.

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

      I solved B in the contest , and solved A after it :) , you too bro :)

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

Haven't participated an educational round properly before. Can someone tell me if the hacks are accounted in ranking?

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

    You do not get points for hacking. You only get one problem less solved if you get hacked.

    So, if you hack somebody with same number of solved problems, you raise by one position in the ranking, because the other one falls down.

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

      Well not necessarily: if the person whose solution I hacked was already beneath me due to submission time. :P

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

        You can make a problem outta that.

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

          Problem A in next contest "predict the rank" lol

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

            That would be too easy to hack.

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

AHH forget about what I said :)))

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

Educational codeforces rounds are a great harbour space initiative. The last educational codeforces round had easy A B and C questions but D and E were really really great for learning. Hope to learn a lot from this contest as well.

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

I hope the tasks will be interesting.

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

I just hope this round will have strong pretests. :D

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

I will Focus now

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

    and that is why we never focus on ourselves and lose ratings.

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

      Ok, Now I will take care of it. I will focus on contest :)

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

      Wow, your rating records are similar to mine. I also think I never do my best in contests, so my rating never goes up.

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

    Don't focus on your friends rating , focus on problems to solve as you can... and if there new ideas for you try to learn it and keep that in your mind or write it in your note book that will make your thinking high not just your rating. Good Luck for you in this contest :)

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

    Will you stop commenting this in every contest blog?

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

Please God Save Us from Corona Virus :( Screenshot Pray to God.

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

Teachers say that we loose our time in quarantine and we are doing nothing. LOOK TEACHERS... WE ARE GETTING EDUCATED

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

    Exactly! those college/school hours are boring and gruesome.

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

Thank you for giving the exact number of problems.

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

We need more contests during the quarantine please! When will we have a contest about Coronavirus?)

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

    Well We don't know if we will be alive To participate That Corona Contest

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

Hello, I am actually slow at solving the initial problems(but i solve them) and not able to solve the tougher ones. So basically the rating never increases. So what should be done ? Thanks.

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

    Practise. Practise. Practise. Try to solve problems of higher difficulty. Well, I was stuck as a newbie for quite a while. But after some practice, I managed to become a pupil. Initially, I used to solve 1 problem a contest, rarely 2, sometimes none. But now, after a decent amount of practice, I am able to solve at least 2 per contest. Just don't give up.

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

      Thanks man!!

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

      where to practice man!!! I am practicing a lot but some questions are not able to solved by me.this really demotivates me and as a result i loose confidence... tell man!!!

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

        In problemset, try solving the As. They are the easy ones. Once you get comfortable with that, go for Bs. Then the Cs. Keep building it step by step.

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

        Learn new concepts like dsu, graphs, modular arithmetic, dp ect then the solution will come from within

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

      I think 'Practice' would help.

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

    then upsolve the tougher ones. That's actually what makes you capable of solving them in-contest.

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

Can someone explain me the difference between education codeforces round and normal div2 rounds . TIA

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

    Two biggest differences are the 12 hour open hacking phase and the score distribution (every problem carries the same weight in educational rounds).

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

    Compared with normal rounds, edu(educational) round don't have a "score distribution"

    Only two factors affect the ranking:"Problem solved" and "Penalty"

    That means, solving 2 problems is always better than solving 1 problem

    However, in normal rounds, problem F worths more points than problem A+B

    • Hacks:

    1.In the normal rounds,you can only hack if following conditions hold:

    • You solved the problem,and you locked it

    • The victim and you are in the same room

    • The contest is not ended yet

    However, in edu rounds, you can hack anyone in the open-hack phase(even if you didn't participate the contest), and you don't need to solve the problem."Room" doesn't exist in edu rounds.

    2.In edu rounds, you can copy the code and test it locally, which means you can preview whether or not the solution will fail.

    However, in normal rounds, it's forbidden to copy the code.

    3.In normal rounds,a successful hack gives you 100 points and an unsuccessful cost you 50 points.

    In edu rounds, hacks changes nothing to your penalty. The only difference is the victim loses a problem

    • System test:

    In normal rounds, system test begins shortly after the contest.All solution will be rejudged with pretests, maintests prepared by authors and successful hacks, if there are.

    In edu rounds, system test begins after the open-hack phase. All solution will be rejudged by pretests and successful hacks.There's no "maintest"

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

      Would you please elaborate on point 2. I am not sure I understood. What do you mean "forbidden to copy the code"?

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

        In normal Div.2 competitions, you cannot copy other's code when you are hacking them (should be in contest rules). In educational competitions (and Div.3 also I think), you will be able to copy the code and test test-cases by yourself.

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

          Thanks. I did not read carefully and did not realize that was in relation to hacks.

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

These days we need more and more contests :'D

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

Hope to learn something new and solve 3 or more question this time. . .

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

Please... make strong Pretest Cases!!

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

I really pray for the load on the server as all college students of India are at home and they have nothing to do so expecting mass participation today.

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

I really wish a color change this time!

Fingers crossed! All the best everyone.

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

My first unofficial Div.2

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

Only exciting thing to engage me, during this quarantine.

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

The biggest mistake of mine is not continuous in every codeforces contest...I request all of you those who are low rated do more and more contest & upsolve,,

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

Screenshot_2020-03-23-Harbour-Space---Codeforces.png

Hoping for strong pretest this time.

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

Hope this round will also be an intresting one, like the other ones, I am really enjoying after joining this community...♥♥♥ All the best guys.. Wash your hands and join contesting..

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

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

I remember that the number of problem was 6 at first. Is the purpose of extra problem to reduce difficulty gap, or is there some other purpose?

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

contest and chill

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

17k+ registration Going to be 18k soom Is it effect corona? I hope corona can't attack anyone on other way.

»
2 months ago, # |
  Vote: I like it +66 Vote: I do not like it
  • Monday
  • Educational
  • 18k participants
»
2 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

18584 registrations! Still increasing!! All the best everyone!!!

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

The server is gonna explode. 18K registration O_O

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

It's about time. Good luck everyone

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

I think that someone should stop coming up with problems

»
2 months ago, # |
  Vote: I like it -29 Vote: I do not like it

WrongAnswerforces

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

The statement of Problem C and E is poor. Is there a reason U / D operation changes x coordinate and L / R operation changes y coordinate in problem C, not U / D changes y and L / R changes x?

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

    D is hard to understand too.

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

      No, it's well written, permutation cycles are denoted in same manner

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

    I tried hard to find solution for C for 2*(n+m) moves.

    That was not fault of statement language, but lengthy statement misguides sometimes to get obvious things wrong. Luckily I noticed later and was able to solve it.

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

    I found problem C pretty clear. Rather than, problem D was more difficult to understand.

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

    Exactly. I'd prefer:

    • $$$\text{U} : (x, y) \to (x, y + 1)$$$

    • $$$\text{D} : (x, y) \to (x, y - 1)$$$

    • $$$\text{L} : (x, y) \to (x - 1, y)$$$

    • $$$\text{R} : (x, y) \to (x + 1, y)$$$

    :P

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

    I'm so confused that I asked the author like this :p

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

    (row, column) is standard when talking about matrices.

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

      but variables x and y are suggestive of the mathematical 2d coordinate system

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

    Well there is always a confusion for grids and 2d matrices. For mathematicians, it is more standard to use co-ordinate system, and for computer scientists it is more natural to think about indices / enumeration of the matrix / grid, which brings us to what it was in the question.

    Doing CP, I think I have been swayed towards the computer science way, and found the directions straightforward. Maybe they should have added the line ( which is usually always there ), "Rows are numbered from 1 to n, from top to bottom, and Columns are numbered from 1 to m, from left to right".

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

    The sample testcases for Problem C is good enough, so I believe explaining which is x and which is y is not important. Remember, only complain about the statement if the sample testcase is just as bad!

    Same thing with problem E.

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

So, how to solve F? Is it inclusion-exclusion on each bit separately?

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

    Solve for each bit separately, multiply results.

    To solve for one bit, I did a linear DP setting 0s from left to right and counting ways to do so.

    Essentially you only have two restrictions to deal with:

    • First of all, for given position P you can't put 0 there if it is a part of some 1-segment.
    • In case you decide to put 0 there, the previous 0 can't be too far to the left so you don't have some 0-segment being completely between those two 0s.
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    No inclusion-exclusion, but let's look at each bit separately.

    Consider some fixed bit, we have some ranges $$$l \ldots r$$$ where this bit must be constantly 1 and some other ranges where this bit must have at least one zero. Let's delete the ranges of the first type and shrink the array. Now we have some ranges and in each range we must have at least one zero (if some of these ranges became empty after the shrink, answer to the problem is 0).

    Now let $$$\mathrm{dp}[k]$$$ be the number of ways to fill the array up to $$$k$$$ such that there is a zero at $$$k$$$ and all the constraints that have the right endpoint $$$<k$$$ are satisfied.

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

      Could you explain a sketch of a linear time DP?

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

        Let $$$dp[i]$$$ be the number of ways to fill up the array up to position $$$i$$$ with a $$$0$$$ at position $$$i$$$. If we're in a segment where only $$$1$$$s are allowed, then $$$dp[i] = 0$$$ (you can't set a $$$0$$$ there).

        Otherwise let $$$l_i$$$ be the rightmost starting point of the segments with ending points $$$< i$$$. We now know that we need to put a zero somewhere between $$$l_i$$$ and $$$i - 1$$$, inclusive (otherwise there is no $$$0$$$ in said segment). This $$$l_i$$$ can be kept updated with proper bookkeeping. Since there are no other restrictions, we can set the zero anywhere between $$$l_i$$$ and $$$i - 1$$$, inclusive. This gives us:

        $$$dp[i] = \sum_{k=l_i}^{i - 1} dp[k]$$$

        We can calculate this sum in $$$\mathcal O(1)$$$ if we build a prefix-sum structure while calculating our dp. To get the result, we can just imagine counting the number of arrays of size $$$n + 1$$$ which end on a $$$0$$$. This gives us a total running time of $$$\mathcal O(k(n + m))$$$ which gives AC. Maybe there is a simpler solution than mine, but I hope, this already helps.

        Edit: Here is a link to my submission, maybe it helps to understand: https://codeforces.com/contest/1327/submission/74120243

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

          "let li be the rightmost starting point of the segments with ending points <i. We now know that we need to put a zero somewhere between li and i−1, inclusive (otherwise there is no 0 in said segment)."
          Shouldn't we put a zero somewhere between li and ri (where ri is the right border of the segment whose left border is li), instead of between li and i-1?

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

            We're only talking about the last $$$0$$$ before $$$i$$$. If we put the last $$$0$$$ at $$$i - 1$$$ for example, we can then look where we placed the last $$$0$$$ before $$$i - 1$$$. Either it's between $$$l_i$$$ and $$$r_i$$$, or afterwards. But even if it is afterwards, we slowly but steadily get closer to $$$r_i$$$ and when we're at $$$i = r_i + 1$$$, then we have no other option then putting it inside $$$l_i$$$ and $$$r_i$$$. In either way, we have put a $$$0$$$ inside $$$l_i$$$ and $$$r_i$$$.

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

How to solve E :<

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

    I had a multiplication instead an addition and unfortunately I solved the problem 5 minutes after the contest ended.

    It is a combinatorial problem.

    Let's say we want to find the answer for block_size = i. This block will contain the same digits (lets name them with letter "a"). Because block_size can't be larger we want the adjacent digits to be different (lets name them with letter "b"). Now the picture is this: xxxbaa...aabxxx (x are the empty cells for now) You can have 10 possible values for "a". Total ways for a and b are 10 * 9. The rest cells can be anything, so we have 10^(N-i-2) ways to set them a value. Now for that fixed picture, ways are equal to 10 * 9 * 10^(N-i-2). But in how many ways we can fix a block of size "i" having two adjacent empty cells ? This can be done in N — i — 1 ways, so we multiply by that as well. Finally we need to add up (this is where I used multiplication by accident) the corner case where we have only one adjacent cell.

    Here is my source-code: https://codeforces.com/contest/1327/submission/74125507

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

      How about the case when you have something like this : xxxxbaabaabxxxxx? Shouldn't this increase the answer by two because we have two blocks there? I don't see how your solution counts for that.

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

        Split this xxxxbaabaabxxxxx to these two pictures xxxxbaabxxxxxxxx and xxxxxxxbaabxxxxx.

        Now the initial picture xxxxbaabaabxxxxx will appear twice. Once for the case we have fixed the first "aa" and once for the case we have fixed the second "aa".

        Probably what you are thinking is that we are counting similar patterns more than once, here we need to take into consideration every "aa", so actually these two blocks of "aa" are independent.

        It will be easier if you stop thinking 10^N numbers but a string of N positions in which you want to add digits.

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

          I still can't understand your point like if u assume cdaabaacd this is one number but aren't we counting our answer twice for i=2 by considering xxaaxxxxx and xxxxxaaxx different but they will count our above number twice?

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

            The author is deliberately counting the case cdaabaacd twice, because this case contains two consecutive segments.

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

              oh! yeah right, Thanks!

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

      Why did you take both the adjacent digits same ? Shouldn't be the total no of ways be 9*10*9 ?

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

        Yes if block size is less than n-2 and we are considering the block is between the number (having adjacent element both side) it will be 9*9*10 , and when we consider the block to be at the corner of the number then it will have only adjacent then we will multiply with 9*10

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

      Thanks

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

      very nice explanation

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

    I used dynamic programming.

    First, let's consider a block of size n. Then there will only be 10 ways to fit them. I will represent the block as X.

    • X (10)

    Then, if we consider a block of size n-1, There will be 180 ways to fit them.

    • X? (10 * 9) 9 -> because it cannot be the same as X
    • ?X (90)

    Then, n-2, there are 2610 ways

    • X?? (90 * 10) X? + ?
    • ?X? (90 * 9) ?X + ?
    • ??X (900)

    You can see that the configuration ending with ? can be computed from the previous block size and the configuration ending with X can be computed naively.

    So, here is the dp.

    $$$dp_{n, s} = \begin{matrix} 10 * dp_{n+1, 0} + 9 * dp_{n+1, 1} & if : s=0\\ 10 * dp_{n+1, 1} & if : s=1 \end{matrix}$$$

    s = 0 is for configurations ending with ?, and s = 1 is for configurations ending with X.

    This doesn't work specifically for n-1, because the first ? (for ?X) is counted as 9 instead of 10, so make that a base case and use the dp starting for n-2.

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

      Oh, thanks. It is easy to understand but is that the formula is

      dp[n + 1][0] = dp[n + 1][1] = 0;
      for n -> 0
          dp[n][s] = is_configurations
                   ? 10 * dp[n + 1][0] + 9 * dp[n + 1][1]
                   : 10 * dp[n + 1][1];
      
      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        yea, but the base case is for n and n-1, not n+1.

        dp[n][0] = 0;
        dp[n][1] = 10;
        dp[n-1][0] = 90;
        dp[n-1][1] = 90;
        

        latex is so hard ><

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

      This is a very nice dp. I have one question to see if I got it right. Let's say we have block of size=4 in the configuration ??0000X? (X != 0). The term $$$10 \cdot dp_{n+1, 0}$$$ comes from the fact that with nine ways we can produce this: ??000YX? (Y != 0) and with one way we can produce this (??000X0?).

      Is it right ?

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

        No. it means if you currently have ??0000X? and you add another character, it becomes ??0000X??, and because this additional character is not incident to the block that we care about, it is guaranteed to not extend the block. So, there are 10 ways to do that (0-9).

        For $$$9 * dp_{n+1,1}$$$, it's 9 because the additional character is incident to the block, so it cannot be the same with the block in order to not extend it.

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

    we could use FFT to solve this problem let f be [1,9,90,900...],and g=f*f,then 10*g[n-i] will be the answer for the i th term

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

In problem B, I thought that maybe it's better to use the word index rather than number. I misunderstand the word number as count.

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

if the contest was 2:15 or 2:30 min, then it might be better(since there was 7 qns). Anyhow nice problems.

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

How to solve D?

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

    If you draw a directed graph with edges $$$(v, p_v)$$$, then each its component will contain one cycle. When we raise our permutation to the power $$$k$$$, an edge from $$$v$$$ will start pointing at a vertex $$$k$$$ steps away. The initial permutation is OK if and only if we have a unicolored loop.

    Now, note that, for some loop of length $$$L$$$, if we raise our permutation to the power $$$m$$$ that $$$gcd(L, m) = G \ne 1$$$, we will be able to jump along this loop in such a way that we will only visit every $$$G$$$-th vertex, which reduces the number of vertices in our path and, hopefully, makes it unicolored.

    For example, if we have a loop of length $$$36$$$ and raise our permutation to the power $$$9$$$, then, starting at $$$s$$$, we will visit only $$$(s + 9k) \mod 36$$$-th vertices of a loop. Our big loop as though breaks into $$$9$$$ small loops of length $$$4$$$. We can travel along each of them and check if any one becomes unicolored.

    Now do it for every divisor of the length (since GCD of $$$k$$$ and some other number can be only a divisor of $$$k$$$) of every loop found. It wiil not TL as the number of divisors of a number less than $$$2 \cdot 10^5$$$ doesn't exceed $$$200$$$, and each such procedure takes linear time.

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

      Great thanks.

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

      "When we raise our permutation to the power k, an edge from v will start pointing at a vertex k steps away." — How did you find about this? What was your approach?

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

        Don't think of it as modifying edges. Think of it as traversing k edges.

        p[v] traverses one edge, p^2[v] traverses two edges, etc.

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

        Looking at the cycles is a very common pattern in anything to do with permutations. What the cycles do when you take the permutation to the $$$k$$$-th power is basically standard knowledge about permutations.

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

      Why the graph theory interpretation when this is exactly cyclic permutations? https://en.wikipedia.org/wiki/Cyclic_permutation

      See my answer https://codeforces.com/blog/entry/75082?#comment-592145

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

      can you tell how can we say that we will be able to jump Gth vertex from s, where G = gcd(m, L), m = power raised and L is length of cycle?

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

        Think of this as, finding the minimum k such as: s ≡ s + k * m (mod L). This translates to 0 ≡ k * m (mod L). Now for k to be minimum, such that this equation holds true, k * m = LCM(L, m). So, k = LCM(L, m)/m. We know, LCM(L, m) * GCD(L, m) = L * m. Therefore, k = L / GCD(L, m).

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

    You do not need graph theory at all. Each permutation is the product of cycles. https://en.wikipedia.org/wiki/Cyclic_permutation

    In each cycle a permutation p^k is like stepping through the cycle k times. So we need to find minimum k so that we start somewhere in the cycle, step by k while maintaining a color (looping around if needed), and eventually returning to our starting point.

    For the last example our cycles are (1 7 3 5) (2 4 6 8). Our cycle colors are (5 8 6 7) (3 4 5 4).

    In this case we only consider k that divides cycle length C. To see why consider repeatedly adding k mod C which is what we are doing. We end up stepping through all multiples of gcd(k,C). This gcd is less than k if k does not divide C so k was not optimal.

    In general we have [Lagrange's Theorem](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)) For this case we consider (cyclic) subgroups of cyclic groups (one for each cycle).

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

How to do C?

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

    Push all points to 1 corner then iterate them over every grid of the board .it's no more than 2nm

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

    Since the number of actions is quite big, you can collect all chips in one cell and then just visit all cells.

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

    go to most up-left(1,1).then travel through all the squares and go to the most under-right(n,m).it is always smaller equal than 2*n*m

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

    You can first use $$$n + m - 2$$$ operations to push all of the stuffs to the right-down corner.

    Then travel the whole board with $$$n - 1$$$ $$$\text{U}$$$, $$$1$$$ $$$\text{R}$$$, (repeat it with $$$m - 1$$$ times).

    Total times of operations will be $$$nm + n + m - 2$$$, and it will be sure less than $$$2nm$$$.

    Hope it helps :P

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

    You can always solve the problem in <= 2*n*m steps if you follow these steps.

    1. Gather every chip to the top-left place. It should take (n-1)+(m-1) steps max.

    2. Now move these chips together through the matrix in a spiral order. This should take n*m steps max.

    Totals steps taken = (n+m-2) + n*m which will never exceed 2*n*m steps.

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

      Spiral traversal is much harder to code than boustrophedon (back and forth) traversal

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

Since recent previous contests had the first question based on parity, I could only think the solution based only parity. How the hell do you solve question-A?

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

    Both n and k should be of same parity and k*k<=n.

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

      Proof? (that $$$k^2 \le n$$$)?

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

        Well, we should consider the circumstance where $$$k$$$ and $$$n$$$ have the same remainder under modulo $$$2$$$.

        Because otherwise there isn't a solution.

        While adding up odd numbers, if $$$n$$$ is greater than $$$k^2$$$, let $$$d = n - k^2$$$, we can get $$$2|d$$$, so we can replace some of the smaller odd numbers into bigger ones.

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

        Min number made of k odd numbers is $$$(k*(k+1) + k*(k-1))/2$$$

        So you can construct every number equal or bigger that that with same parity.

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

          I understand the sum of the first $$$k$$$ odds is $$$k^2$$$ but I've been staring at this equation $$$(k * (k+1) + k * (k-1))/2$$$ on paper for 30 minutes and I don't understand what it means. I'm just curious, can you elaborate (without reducing it using algebra). All I see is the formula for arithmetic sum and $$$\binom n2$$$.

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

            I think what the OP wanted to say was that the minimum number made by first 'k' odd numbers is (k∗(k+1)+k∗(k−1))/2, which is same as the square of k, solved by reducing using algebra. The OP's wording is wrong because the minimum number you can make with k odd numbers is infinite, unless you are given those k odd numbers.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it
             1 2 3 4 5...
            +  1 2 3 4...
            ---------
             1 3 5 7 9...
            

            first line is $$$k*(k+1)/2$$$, second line is $$$(k-1)*k/2$$$

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

        Sum of First n odd nos. is n**2.
        1=1;
        1+3=4;
        1+3+5=9;
        So k should be <= root(n).

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

      .

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

        No, it should be less than equal to. Consider 221 and 175 as input.

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

    First of all, the sum of the first $$$k$$$ odd numbers is $$$k^2$$$.

    Then, if $$$n$$$ is greater than $$$k^2$$$ and the remainder $$$k$$$ and $$$n$$$ have under modulo $$$2$$$ are the same, then it is sure that we can figure out a proper solution.

    Otherwise, there's no solution.

    Hope my explanation helps :P

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

    let us assume odd number are 2a1-1,2a2-1,2a3-1,....2ak-1

    as per equation sum up all n= 2*(a1+a2+a3+...ak) -k;

    so a1+a2+a3...ak = n+k/2;

    first check if n+k is divisible by 2 or not , if so then for all distinct a1!=a2!=a3..!=ak ,minimum sum of first k distinct positive number is k*(k+1)/2; if this sum is smaller than or equal to (n+k)/2 ,then ans is yes ,else no

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

Today's problem E

One can write a simple bruteforce for n = 5 and find this trivially.

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

Well done every one :D. Thanks for a nice contest(even though my rating drop :( )

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

How the hell do you solve A????

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

    If you observe the basic even odd numbers. Sum of any numbers even times will always even and the sum of any numbers odd times will be odd. So, wither we need both n and k even or odd. Other than that if the sum of first "k" odd numbers is greater than "n" then it is not possible to get any set of "k" numbers with "n" as the sum. And sum of first n odd numbers is n^2. Hopefully, It will help. Thanks.

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

    Short answer cout<<((((n-=k*k)<0)||(n&1))?"NO":"YES");

    Details answer

    n -= k * k; // 1 + 3 + 5 + ... + 2 * k &mdash; 1 = k * k
    if (n < 0) // if n < smallest sum of first k odd number
       cout << "NO";
    else if (n % 2 == 0) // we can chose first (k &mdash; 1) odd number than choose last as n &mdash; sum
       cout << "YES";
    else
       cout << "NO";
    
»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I would like to thank the authors for allowing me to use BM. https://codeforces.com/contest/1327/submission/74109025

Source — https://codeforces.com/blog/entry/61306

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

What should the answer be to this test case in D: n=3 , P = [3,1,2] ,C=[1,2,3]? There does not exist any k for this case right?

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

    Since all colors are different, we need p[i] = i, smallest k for which this happens is 3.

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

    It should be 3

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

    answer is 3. p^3 = {1,2,3}. SO now you have 3 infinite cycles.

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

Amazing: 20000+ registered users for this round!

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

for the first time, I have no idea how my A and B got AC!!.

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

E is much easier than D?  I solved E even earlier than B.

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

    I spend lot of time on E, thinking of things like multinomials, but that would straight up blow the complexity. Also tried generating function, but gave up. Can you give a hint? Thanks!

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

      If a block has a size of i:

      There are 10 plans for all numbers in the block, 9 plans for each number adjacent to the block, 10 plans for each number not adjacent to the block.

      Then just discuss:

      The block includes both the first and last element.

      The block includes either of the first and last element.

      The block includes neither of the first and last element.

      Here is my submission.

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

        Oh now I feel it is easy! Thank you, clearly explained!

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

        I was doing the exact same thing, but don't know for what god-damn reason I gave up :(

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

        Say for example n=4, and we have to find the answer for block size = 2;

        Now _ _ _ _, I fill the second and third places with any number. 10 ways to do it. I fill the first and last place with any number other than the one I placed on second and third : 81 ways to do that.

        Total ways = 810.

        Now, _ _ _ _ I fill the (first and second) or (third and fourth) place with any number. 10 ways to do it The Remaining places can be filled with 9*10 = 90 ways. Total ways = 810 + (90*2*10) = 2610.

        Now my question is that, when I calculate it this way, Am I not repeating the same cases? For example, _ _ _ _ I fill the first 2 places with a two. then randomly the second and third place get a 3. the number is 2233. OR I fill the last 2 places with a 3, and then randomly fill the first 2 places with a 2. I end up getting 2233.

        These are the same cases. Dont we end up recalculating them? JKLover

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

          2233 has 2 blocks of size 2, so it is right to calculate it 2 times.

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

      There is a common idea behind tasks like this on Codeforces.

      1. Write bruteforce
      2. Look on some first answers
      3. Try to transform them (like in this task divide all answers by 10)
      4. Try to find this sequence on OEIS.
      5. ???
      6. Profit!

      In example, there is this sequence for today's E

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

    Really? B was just a comprehension question. Masked in an annoyingly huge statement, was the real problem: perform the greedy mapping as described, and just check at the end if any princess and kingdom pair is unassigned. Implementation is trivial.

    E was not easy at all. The only reason I solved E is because I wrote a brute-force and observed the pattern for small values. I still have no idea why the pattern is there.

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

      I mean that E is easier than D.

      I agree with you,E is exactly more difficult than B.

      I solved E earlier than B just due to my mistake in conprehension.

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

      problem E can be solved in many different ways (including OEIS cough cough), and so I think it's significantly easier than D.

      But D doesn't require any algorithms, just an understanding of why it works in time limit. That might be why it's supposed to be easier than E.

      Whatever... I demand D and E to be swapped

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

    literally took two hours to solve D :D

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

I don't know why but my rating decreases in every Educational Round...Get educated....

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

    Same xD every educational round brought us a whole "strange" problem that made us confused a lot

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

    Your rating just went up by 42 points...

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

      Yeah I didn't see that coming. [facepalm]

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

What is the time complexity for D? I believe most submissions had O(n x logn x sqrt(n) [all divisors]). How could it pass?

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

    Where does the log come from? I had no log and can't see where you would get it.

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

      How to solve D? please

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

      I got the log initially by somewhat different implementation than most. I basically check the answer for all divisors of each disjoint cycle. In the check function, I used binary lifting/search of some sorts to get the kth power permutation. Anyways, I got a TLE verdict :(

      Link

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

    My solution has solution O(n * divs(n)) without the log factor.

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

    O(n sqrt(n)), but actually it's O(160 n) since there are at most 160 factors for number in [1,n].

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

    -is-this-fft-, Mucosolvan, cwise okay, thanks, I misread the limit of the second for (to i, not to n) :'(.

    Guess stuck by wrong time analysis exists :'(.

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

    The time complexity is indeed $$$O(n^{4/3} + n\log{n})$$$.

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

      Random boring comment: while this $$$O(n^{1/3})$$$ bound may be reasonable in practice for given constraints, it is worth keeping in mind that the function we are talking about is subpolinomial: see wiki.

      So it is a bit like saying "We implemented $$$n^2$$$ here, optimized it with bitsets to $$$\frac{n^2}{32}$$$, and since $$$n=1000$$$, our solution is $$$O(n\sqrt{n})$$$"

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

        Personally, I don't see any problems with $$$O(n^{\frac{1}{3}})$$$ since, for example, saying that $$$\sqrt{n} = O(n)$$$ doesn't contradict with the definition of big-O notation.

        On the contrary, the example with bitset contradicts with the definition of big-O unless adding constraints on $$$n$$$ every time you mention $$$O(n \sqrt{n})$$$.

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

How to solve C if we are required to minimize the number of operations ?

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

Why does this code give Runtime Error on Test 1?

https://codeforces.com/contest/1327/submission/74124335

It works on my machine and I couldn't find any source of undefined behavior in the code.

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

    Error: attempt to subscript container with out-of-bounds index 3, but container only holds 3 elements.

    This probably happens in line 142: if(c[i[w+len/j]] != c[i[w]])

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

    You have an out-of-bounds access on line 142: if(c[i[w+len/j]] != c[i[w]]). Here i = {1,2,3}, w=0,len=3,j=1 situation is reached and out-of-bounds occurs.

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

    Got the error. Thanks!

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


Wow! first time I see this number.

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

    What will you do when you are being quarantined? Of course, you will find anything to kill the time

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

Hey guys, can anybody explain how to solve E? Thanks

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

    Refer this comment by JKLover : Link

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

    Consider a block of length $$$i$$$ ($$$i$$$ goes from $$$1$$$ to $$$(n-1))$$$. We can have $$$(n - i + 1)$$$ such blocks. Let the digit placed in the entire block be $$$k$$$. For every block, the immediate left and right digits surrounding the block can contain all digits except $$$k$$$, otherwise the length of the current block will change. Therefore, for these left and right places we have $$$9$$$ possible digits and for all remaining places we have $$$10$$$ possible digits. We need to handle two cases :

    Case 1 : The blocks of the kind $$$0...(i-1)$$$ and $$$(n-i)...(n-1)$$$ have only one surrounding digit in each, $$$(i)th$$$ and $$$(n-i-1)th$$$ respectively where we can place $$$9$$$ digits.

    Number of remaining places with $$$10$$$ possibilities at every place = $$$(n - i - 1)$$$.

    Total possible ways = $$$2$$$ x $$$10^{(n - i - 1)}$$$ x $$$9$$$

    Case 2 : All blocks except the two mentioned in case 1 (there will be $$$(n - i - 1)$$$ such blocks). Each of these blocks has both left and right surrounding digits.

    Number of remaining places = $$$(n - i - 2)$$$.

    Total possible ways = $$$(n - i - 1)$$$ x $$$10^{(n - i - 2)}$$$ x $$$9^2$$$.

    Overall answer for a block of length $$$i$$$ = $$$10 * (Case 1 + Case 2)$$$ (multiplied by 10 since the current answer is just for one possible digit across the entire block).

    Simplifying the expression gives the result = $$$9$$$ x $$$10^{(n - i - 1)}$$$ x $$$(9$$$ x $$$(n - i) + 11)$$$

    For $$$i = n$$$ the answer is simply $$$10$$$

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

      Great explanation. Thank you a lot.

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

      Say for example n=4, and we have to find the answer for block size = 2;

      Now _ _ _ _, I fill the second and third places with any number. 10 ways to do it. I fill the first and last place with any number other than the one I placed on second and third : 81 ways to do that.

      Total ways = 810.

      Now, _ _ _ _ I fill the (first and second) or (third and fourth) place with any number. 10 ways to do it The Remaining places can be filled with 9*10 = 90 ways. Total ways = 810 + (90*2*10) = 2610.

      Now my question is that, when I calculate it this way, Am I not repeating the same cases? For example, _ _ _ _ I fill the first 2 places with a two. then randomly the second and third place get a 3. the number is 2233. OR I fill the last 2 places with a 3, and then randomly fill the first 2 places with a 2. I end up getting 2233.

      These are the same cases. Dont we end up recalculating them? cuber_coder

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

        Yes you are right in your example that you are considering the number 2233 twice but for different block each time. Though the number is same but the interval used for block is different and we are counting number of blocks and not the frequency of number. Moreover it can be clarified from the fact that 2233 is chosen twice as it has 2 blocks 2 length 2. Hence in the given logic for each block length i a number is considered same number of times as the frequency of blocks having length i and same digit.

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

why is everyone in C , computing n times L,m times R, and then in a (n,m)loop D & U ??

whats logic ,and how did you all reached this condition

Are you guys are trying to access all points from most bottom(point) to the highest point, then why not begin() from lowest input point instead of (0,0), else ain't the length of out instruction will increase??

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

    Because you must gather all point to one place. What if when you iterate, there's some point that didn't pass the place it has to pass? Or there're some points that have to pass someplace lower than itself or lower than the lowest point?

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

    It's simpler this way. The problem doesn't ask us for a short sequence of operations. And moving all points to a corner and then moving all of them over the whole board works.

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

    Besides, You don't have to minimize the output unless it longer than 2nm .

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

20K registration !!...happy quarantine...

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

Problem B — WTH! Submitted code in PyPy3 — TLE but same code for Python3.7 — Accepted and then codeforces suggests PyPy3 works faster.

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

How to solve G?

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

    You build an Aho-Corasick automaton from the t_i strings and then do a dp over the automaton states and the set of characters you've already used.

    So, for a bitmask m and a Aho-Corasick state s, dp[m][s] would be the highest value attainable using the characters corresponding to the set bits in m for the first popcount(m) question marks, while ending in state s. You'll need to know the cost of all strings ending in a state, which you'll have to propagate along back links. In the transition, you look at all possible characters you could use for the next question mark, and then add the cost of the state you get after using that character, and all the states you visit when adding the fixed characters up to the next question mark (or the end).

    This comes out to $$$O(14 \cdot 2^{14} 10^3 + 4 \cdot 10^8)$$$ which passes in 1.5s/4s for me.

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

    Use Aho–Corasick algorithm to build an automaton.

    Consider dp(automaton node, bitmask of used letter), and there will be up to $$$2^{14} \times 1000$$$ states. We can not use this state to iterator string $$$s$$$.

    But the transition of the dp state between two "?" is only related with automaton node. So between two "?", we only need to preform transition of the automaton node, and when we meet a "?", use the above transition to perform transition of complete dp state (this will only happen up to $$$14$$$ times).

    Sorry for my bad English, and you can see my submission 74095972.

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

Is finding the shortest cycle in the graph with edges between 'i' and 'input[i]' a wrong approach? After this, I considered nodes with the same colour separately like what is the path length between two nodes of same colour that maybe my answer too, took min of all possible answer. Got WA on 2nd test:( is the approach wrong?

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

Any hacks for A ?

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

Couldn't even do A

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

how do they calculate the penalty in educational rounds?

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

    Summation of total time taken for each problem.

    Suppose you solve problem A in 10mins and Problem B in next 15 mins.

    Then total penalty is (10 + (15 + 10) + extra time penalty for previous wrong submissions) mins

    Or basically just sum up the time shown below your submissions in the ranklist and add extra time penalty for wrong submissions )

»
2 months ago, # |
  Vote: I like it -42 Vote: I do not like it

Statement of D was very confusing is there any sense for using same letter $$$(c)$$$ to denote colors as well as multiplication of permutations?

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

    wow I didn't even notice that

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

    Sorry, my bad. I didn't notice it.

    But is there any sense for registering a fake account to express your opinion?

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

As I know little about replacement I think E is much easier than D...

But I didn't try to solve E on the contest...

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

Problem B: how fast is your reading comprehension

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

Were today's A,B,C easier than usual educational round problems ?

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

A long time ago, I used an extension that computed approximate rating changes before official results were out. Can anyone send link to that?

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

Is this kind of self-hacking allowed? https://codeforces.com/contest/1327/submission/74121343

It seems kind of obvious and shameful that people would stoop to such low levels. Very disappointed.

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

    Doesn't really matter since you get no points for hacking. Infact it atleast makes it fairer for other contestants, since the hacked user's rank worsens.

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

why does the problem D (1327D - Бесконечный путь) have so many tags

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

In Problem D, it says that the answer always exists.

I maybe wrong, but I feel that for this testcase the answer doesn't exist. 1 4 2 1 4 3 4 3 1 2

I don't think an answer exists. because the p^2 = 1234 p^3 = 2143 .......... and so on. We never get an answer here. Please correct me if I am wrong.

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

    On p^2 we already get the answer, start the infinite sequence with any index you still end up at the same index. And same index has same color.

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

Bad Day for me. On looking the number of submissions, i thought E is more easier than D but failed to solve E at the time of contest. Later on i found D was more easier for me than E.

Did you guys solved any problem similar to E before??

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

    I think E is much easier than D... E is straightforward combinatorics problem isnt it?

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

      You don't even need combinatorics. I just calculated sequence for first 1 <= n <= 6 digit numbers and with some observation constructed the sequence.

      PS: This might not be a good way of solving problems like this, but that's what i did.

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

      Well i am weak in combinatorics but after the contest i upsolved it using prefix sum. My Solution

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

You can try to think about a clever solution for problem E... ooor you can brute force first values and let Berlekamp Massey do its magic finding a linear recurrence that solves the problem without understanding anything of what it is doing: submission :P

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

I tried to minimize the number of operations required for problem C .

The logic roughly goes as: I find the point which is closest to it's target and take it there in min steps updating all other points, and keep repeating this. This might not be optimal but takes less steps atleast than the solution of most.

But I'm getting some wierd Diagnostics issue and hence a WA on Test 4, although my output is correct.

https://codeforces.com/contest/1327/submission/74139658

Can someone help out?

»
2 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Quick tutorial

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

Why so much delay in the editorial ?

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

Can someone explain the problem statement for D?

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

in problem D: for this input: 1 3 2 3 1 1 2 3 I ran it on an accepted solution and it got 3 can anyone please explain to me why?

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

    $$$ \forall \sigma \in S_n, \sigma^n = \mathrm{Id} $$$.

    You get $$$ n $$$ classes of color equivalence, each with 1 element, so the answer is at most 3.

    But it can't be less than 3, because otherwise you get a cycle of length 3 and it contains 3 colors.

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

      P^1 = 2 3 1 , P^2 = 3 1 2 , P^3 = 2 3 1 and 2 3 1 doesn't have an infinite path

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

        P^3 is in fact 1 2 3.

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

          How is P^3 = 1 2 3 can you please show me the steps for it to be 1 2 3

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

            $$$ P $$$ = 2, 3, 1

            $$$ P^2 $$$ = 3, 1, 2

            $$$ P^3[1] = P^2[P[1]] = P^2[2] = 1 $$$.

            $$$ P^3[2] = P^2[P[2]] = P^2[3] = 2 $$$.

            $$$ P^3[3] = 3 $$$, because $$$ P^3 $$$ is a permutation of $$$ { 1, 2, 3 } $$$.

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

      Haha, I tried to prove and lol now I have a counterexample for that statement.

      $$$ P = (1 2 3) (4 5 6 7) (8) $$$.

      Order of $$$ P $$$ is $$$ 12 $$$, but $$$ n = 8 $$$.

      But in that particular case, $$$ \sigma^3 = (1)(2)(3) $$$ indeed.

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

      Btw this is not true:

      • $$$\forall \sigma \in S_n, \sigma^n = \mathrm{Id}$$$

      Consider $$$ \sigma = (1)(2 3 4) $$$.

      Then, $$$ \sigma^4 = (1)(2 3 4) $$$ and not $$$Id$$$.

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

For problem E this can help https://oeis.org/A255380 As in the given link it's for special case 10. we didn't need that , so in the formula just remove a(n-11) that's all.

Overall didn't liked the problem as 'E'.

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

    Thanks for the link! Very interesting problem too.

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

Why there are more participants solved E than D? (;´д`)ゞ

In my opinion, it is better to swap D and E. I managed to solve D but then I did not have enough time to solve E. (Honestly I had. But I just kept making foolish mistakes..) Maybe I should stop to solve E instead of insisting on D as soon as I noticed that fact.

All in all, nice contest! Like it! (*^▽^*)

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

Where is solution?

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

How many people solve problem E with OEIS?

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

Thanks to codeforces for giving us opportunity to participate in too many contests. I have a request. Please make contests more frequent during this hard time.

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

I hope will finally become purple today, thanks for the contest.

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

When rating will be changed?

12 hours hacking phase has been finished.......

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

    It is done always after the system testing :P

    There is a system testing done after the hacking phase

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

      Are there any rules that after system testing how many times it takes?

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

Can anyone please exaplain me question E??

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

why dafuq does it happen? my sol of A didnt get accepted bcoz the datatype was int and not long long int. Although it was given that the limits were till 10 to the power 7

»
2 months ago, # |