Wind_Eagle's blog

Codeforces Round #741 (Div. 2)
By Wind_Eagle, 3 years ago, In English

Choose the way, five paths there for you to find
Turn the page, the question lies between the lines...

Hello, Codeforces!

I hoped that once there will be my second round, and finally, here it is!

I am very glad to invite you to the Codeforces Round #741 (Div. 2), which will take place in Aug/26/2021 17:35 (Moscow time). This round will be rated for the participants with rating lower than 100000110100 (2100).

My thanks to:

  • antontrygubO_o for rejecting problems A his great coordination of this round! Thanks!

  • gepardo made a lot. There wouldn't have been this contest if he didn't help me. Thanks!

  • EIK this is the person who taught me competitive programming — my Informatics teacher. Thanks!

  • MikeMirzayanov for Codeforces and Polygon platforms. Thanks!

  • You for participating in this round. Thanks!

You will have 2 hours and 15 minutes for solving 6 tasks, one of which will be divided into easy and hard verions.

One of the problems will be interactive. So, it is recommended to read the ultimate guide on your favourite type of problems before the round.

I hope you will enjoy the round!

Round testers: 244mhq, BigBag, Savior-of-Cross, Kuroni, programmer228, MagentaCobra, Vladik, bWayne, kassutta, asrinivasan007.

Score distribution: 500-1000-1250-(1250+1250)-2750-3500.

UPD: It was decided to add a sixth task to the round to balance the difficulty.

UPD2: Editorial is here!

UPD3: Congratulations to the winners!

Winners
Some other people who deserve congratulations
  • Vote: I like it
  • +520
  • Vote: I do not like it

Comments Comments (208)
| Write comment?
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

good luck every one :)

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

    do you know why you got so many downvotes?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +55 Vote: I do not like it

      i think it's because he copied the comment of upsolving from the deltix round blog and people at cf don't like cheating or copying either in contest or in blogs:)

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it -6 Vote: I do not like it

      CF comment voting is so weird and unpredictable. See?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +95 Vote: I do not like it

        Yes, never write comments if you aren't red

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

          So, why did you write the comment with the advice not to write comments? :)

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            Because I want negative contribution, but I didn't make it this time :)

            → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -197 Vote: I do not like it

          And if you are red then any trash you comment will get upvotes.

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

    Please, Update Score distribution.

    → Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Ready for a binary problem :')

Spoiler
→ Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

for rejecting problems A

Lol.

→ Reply
»
3 years ago, # |
  Vote: I like it +97 Vote: I do not like it

If I could say..

"100000110100(2100) = 2100**11 + 2100**5 + 2100**4 + 2100**2 ~= 3.5e36. Now we are all rated, so yay!"

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Hope to see you GM post this round, Best of luck :P

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Your rating graph even after refreshing 3-4 times :|
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You just zoomed in on the graph.

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

        Nope, zoomed in/out won't produce such graph. Additionally, u can see highlighted highest rating at left corner :P

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

          Just check the timeline it is starting from jan 1970 . and Yes, zoomed in/out produce such types of graphs.

          → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

your last round had a problem related to Bit manipulation , i am guessing this round has one too ^_^

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Well lots of bit manipulation is already going on in comment section.. damn they are already practicing for the problem.. BitForces

    → Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

pikachu theme? sounds interesting :))

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is full form of P.S.??

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice! P.P.P.S. Very nice.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Ah! the poetic side of the author, the P.S.(Pre-Script) is noice!

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Useful Resource to watch before this round.!

Best of Luck Everyone!

→ Reply
»
3 years ago, # |
  Vote: I like it +99 Vote: I do not like it

So, this is a Div. 10 round where we have 10 hours to solve 101 tasks ?

→ Reply
»
3 years ago, # |
  Vote: I like it +76 Vote: I do not like it

Who is the VIP tester this time? The suspense is killing me.

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

this is the person who teached me competitive programming

Should be taught lol

Really looking forward to this round!

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

    I wonder if I get negative contribution, will it balance out and give me positive delta

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Really kind of yours to thank your CP teacher EIK. Looking forward to participate in your contest!

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

i guess next time is: PSPSPSPS congratulations to the winners

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

teached taught

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Everybody here talking about Wind_Eagle's typo mistake of taught ,but nobody noticing the beautiful 2 liner poem at the top right corner of blog.

→ Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Good luck to everyone, and i hope i can be cm after the contest.

→ Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

So this round is about pikachu?

Spoiler
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

I think it should be available and not availible. Wind_Eagle

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hoping interactive problem to be D or E. I don't like interactive problems but still, will participate in this contest.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just VCed your last round, problems were super cool!!, Looking forward to this round

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

As a tester, you don't know if I tested or not

→ Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it -6 Vote: I do not like it

D1,d2 require 1 correct soln

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    Well, you are kind of correct: tasks D1 and D2 require a correct solution.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"the ultimate guide on your favourite type of problems"(INTERACTIVE) -Not really

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Where is the announcement of the testing round I just participated in?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any astrologer out there, Will i become blue today .....?

→ Reply
»
3 years ago, # |
  Vote: I like it +60 Vote: I do not like it

Why is rating updation being done right now, in last round I went back to below 2100, but due to rating changes being updated it shows I am above 2100 right now which creates confusion whether this round will be rated for me or not ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I expect a Easy A??

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why not?Every A of CF is easy!Sometimes it looks harder but has an easy solution.Like last round's A was pretty easy.But most of us thought that bruteforce wouldnt work :(

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

      Ahh let's Be honest this time...Implementing A took me 2-3 mins but understanding A took me 20-22 mins last round!

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

        Yeah, the implementation of A just involves a few if else and for loops, but still it takes time to figure out what exactly we need to do in the question :(

        → Reply
»
3 years ago, # |
  Vote: I like it -51 Vote: I do not like it

IMG-20210726-002423

When my Brute Force Solution passes all the TCs.

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

By this line rating lower than 100000110100 (2100) , I think there will be good concepts of bits in the problems

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please provide the editorials in JAVA as well.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Editorials will be provided only on English and Russian, I think :)

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the tutorial be released

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D2?

Is it somehow related to finding the K-th one in the segment tree?

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

    I didn't submit anything for the contest, but I think you might be able to keep the indices of positive/negative in a set, get the lower and upper bound for each query in logn, and just greedily pick from there.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 7   Vote: I like it +8 Vote: I do not like it

    Much easier :)

    From D1 you should already know, that answer is always $$$1$$$ for odd segments and $$$2$$$ for even, if sum inside is not equal $$$0$$$. So, firstly we will reduce problem to odd segments by taking first element of even segment to answer, for example. Then, you need to find such element, that sums before it and after in segment the same. Suppose we have query $$$[l, r]$$$ and we want to delete element $$$x$$$. In terms of prefix sums we will get $$$pref[r] - pref[x] = pref[x- 1] - pref[l - 1]$$$, that equals to $$$pref[x - 1] + pref[x] = pref[l - 1] + pref[r]$$$. And all you need — is to count $$$pref[x] + pref[x - 1]$$$ for all elements and add to some associative container such indexes, let's call it $$$C$$$. The answer- lower_bound in $$$C[pref[l - 1] + pref[r]]$$$ by $$$l$$$. 127111849

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

      I did the exact same thing just that I am trying to find the element that divides the segment into two equal sums. so if for an odd segment the sum is 2*a+1. I am trying to find the element responsible for making the sum a+1. So that on the removal of that element the two segment right and left of it will have the same sum. But for some reason, I m getting wrong answer on test 2. Submission: 127143195 Can u help?

      → Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Very balanced and cool contest! Thank you very much <3

→ Reply
»
3 years ago, # |
  Vote: I like it +74 Vote: I do not like it

GuessForces

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve E?

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

    I can think of O(n^2 logn). But I don't think that's meant to pass.

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

    Wait for editorial :)

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

    I used suffix array with an O(N^2) dp, got the pattern when writing out the suffix array of the first sample test and try to get the result from that.

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

      Actually you can precompute LCP in $$$O(N^2)$$$ with something like this:

      $$$lcp[i][j] = s[i] == s[j] ? 1 + lcp[i + 1][j + 1] : 0$$$

      That makes the code really clean.

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

    I tried an O(n^2) dp approach. solution


    I utilised the fact that the answer for the reverse of the expansion will be the longest decreasing subsequence.

    By reversing the string, we can enumerate all the substrings that end at any particular character such that they are in the same order as in the original expansion.


    Now let dp[i] be the LDS such that we necessarily took the substring ending with char s[i].

    So for calculating dp[i], the answer will be at least i+1 as we can take all the substrings ending at s[i]. Now we can iterate and check if we can add all these substrings to any previous answer only if those answers are greater than all substrings ending at s[i] (as it's always best to include these substrings).

    SO to check two substring families ending at s[j] and s[i] (j < i), I pre-calculated g[j][i] which tells me after which length of a substring starting from j towards 0, it becomes greater than the substring family s[i] and use this value to subtract the initial substrings starting at j which are smaller than substring family s[i].

    Now final answer is max of all dp[i]

    PS:- sorry for my bad explanation.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    Greedy .... lets say you have a string 1101 which is x (let's say) then to get a number that dividides it is simply 11010 which is 2 * x

    So basically all we need is a 0 to find a multiple .... let place = index of last 0 (from 1 to n)

    Case 1 — 0 exist in 1 to n/2 then just print from that place where 0 is to n and place+1 to n

    Case 2- 0 exist after n/2 then print 1 to place , 1 to place -1

    case 3- 0 is at n/2 ... print from n/2 to n and n/2+1 to n

    Case 4 — all numbers are 1 ... then print 1 to n/2 and n/2 to n or 1 to n/2 , 2 to n/2+1

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

      I the case that all the numbers are 1 i took 1 to n/2 and 1 to 2*n /2 but that did not work

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

        I made a dummy mistake in the case that every thing is one , i output the interval in the wrong order.It's 1 to 2 *n/2 and 1 to n/2

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

        chika10 Can you help me in Problem C.Idk where I'm making a mistake.127118923

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A bit difficult for me. Is answer for D <= 2?

→ Reply
»
3 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Today I'll loose my "newbie" virginity

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Lol, guessed the solution for D1 but tried implementing with sparse tables instead of prefix sums for some reason...

How to prove D?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 5   Vote: I like it +7 Vote: I do not like it

    actually if alternative sum is 0 -> ok,

    if it's odd then of course there exists 1 rod which divides interval into 2 intervals with equal alternative sum(total sum / 2) so this will be the rod to be removed(and after it second sum will become: -sum and hence 0 in total).

    if sum is even -> just ignore first rod in current interval and sum will become odd, now do the same as above.(p.s. here it can be proved that in 1 deletions it's impossible to make things good(of course even in 0 deletions) the reason is simple: making alternative sum in 1 deletions simply means that there should be 1 rod without which the remaining sum should be split into 2 equal alternative sums which is impossible(odd isn't divisible by 2))

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

    These two observations must be enough to get to a solution.

    Observation 1: If rod at Index i is removed,the subarray [i+1,N] gets multiplied by -1.

    Observation 2: If Sum is odd (of the form 2*a+1), we can find the index at which sum[ l ,i-1 ] == a && sum [ i+1, r ] == a and remove the rod at index i.

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

    Observe that once you remove a character the net value of the sequence following it till the end gets multiplied by -1. Now coming to the question There are 2 cases, either the sequence length is odd or it is even

    • Case odd: When the length of the sequence is odd then the total sign-variable sum must be odd. Now every odd number x can be written as odd = even + [+/-] + even. Now if you strategically remove the [+/-] then the net value becomes even — even = 0. Hence the answer for odd length is always 1.

    • Case even: When the length of the sequence is even then the total sign-variable sum must be even. If the total sign-variable sum is already equal to 0, then no rods need to be removed hence answer is 0. Otherwise, we can write even = [+/-] + odd. Now to you have to remove one rod to get the net value odd and we saw that every odd value can be made 0 by Furthur removing one rod. Hence the net answer for this case becomes 2.

    → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

In B, the highest left digits is 2 right?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Balanced an implementation heavy contest. B and C could be solved easily if you have pen, paper and time.

→ Reply
»
3 years ago, # |
  Vote: I like it +120 Vote: I do not like it

Some relevant meme.

Hnet-com-image-3

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I've prooved all the solutions :)

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

      I'd be waiting for the editorial then :D. And memes apart, themks for an amazing contest! The problems were very interesting!

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D1 I only saw sample test and guess :)) then I pass pretest :V cool :)

→ Reply
»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

The keyword for today's contest is "answer <= 2".

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?

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

    Just search for one zero For example you have 10111 then ans is 0111 111 k=1 and if the zero is after half the string like 11101 then ans is 1110 111 k=2

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

      Did the first thing but missed the second one during contest,couldn't catch the left shifting observation...I am gonna kill myself

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

        I got the second one but failed to understand the first one, and got stuck in this problem.

        → Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Every other problem is casework lol. Nothing to learn from the first 4 problems.

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

    Finding out the cases is problem solving too, no?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      Sure it is, but so are puzzles. None of these problems involved programming or designing a data structure or an algorithm I'd say.

      I'm not saying these problems are bad, but it's nice to have a variety in contest problems. There is so much possible with graph/tree, DP, DataStructures, geometry, string algos. So it's a little disheartening to see the first 4 problems just being ad-hoc.

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

        Task E? It involved algorithms lol.

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

          Yeah, I can barely make it to the 5th or 6th problem with enough time in a 2hr contest.

          I used to like Topcoder SRMs for this reason because one can actually get to the harder/nicer problems in time since there are only 3 problems. But i guess I'm digressing here, I'll give it a try when i find time to upsolve. Thanks.

          → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +43 Vote: I do not like it

Did you changed the checker for B?
Because my code passed sample in contest but failed on the same test case on sys test.
Mentioning Wind_Eagle

My code failed system test:

And it failed on the sample case:

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Same for me. I print the wrong length of the string. I always print 1, even when I have to print 2. The code passed pretets but failed systests. In fact, my solution should fail sample test, so it should have failed pretests as well. There's something wrong here.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +17 Vote: I do not like it

      Yes, this is the same mistake I made.

      I think they changed the checker without any announcement.

      This is unfair.

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

        gepardo Wind_Eagle Could you look into the situation please? It's as though there are different checkers for pretests and systests. Both of us could easily correct out the code without even losing 50 points for the wrong submission as we fail on the sample test. I understand that it's still our mistake and we should have been more attentive. I cannot prove that I had the AC on B during the round, but do believe me. There could be more casualties.

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

          I have a proof. See my Submission(127073976) for B that gave runtime error on test 2, but actually prints wrong answer for test 1 as well. It was very unfortunate that they had incorrect checker for B, that made my obvious incorrect solution pass.
          The previous Codeforces had weak pretests for D1 and D2, that allowed my solution with integer overflow to pass but it failed on system tests.
          It is too sad and demotivating to lose rating continuously due to others mistakes. (ofcourse some mistake was mine as well, but in ideal cases I will consider them as other's mistake).

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

            same things happening to me :(
            A screenshot from round 738

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

        And my code passed after fixing the size.

        I was about to get somewhere around +100
        Now its -8
        (;﹏;)

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    I don't know why B asks for outputing the length, it makes no sense, just annoying.

    → Reply
»
3 years ago, # |
  Vote: I like it +66 Vote: I do not like it

In last Div1 round my rating decrease by over 100 so I become Canditate Master after that; but because ratings are temporarily rollbacked, and when I register the current round I noticed that I'm "out of competition". I will be rated after undoing rollback? or be unrated as my rating is temporarily still > 2100?

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

    Will be rated.

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

      lmao I guess I will be unrated so I give up debuging D2 and start to write E.

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

    I'm also in the same situation, let's see how rating changes after the contest.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    I can tell from your picture that you are Chinese.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D2?

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

$$$Trickforces.$$$

How sneaky: "such that $$$f(t)=f(w)⋅k.$$$"

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

deleted.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In C is f(t) and f(w) both are 0 allowed? that would make k become any integer.

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

    Yes, such case is possible, and $$$k$$$ can be any integer in this case.

    → Reply
»
3 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Ad-hoc problems nowadays are getting to the next level.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Deleted

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it
Spoiler
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am so sleepy today... especially I only sleeped for 20 mins in the afternoon;But the problems are quite challengeable.wu... it is 1:00 now,i gotta sleep;

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In C, first testcase, would "2 5 3 5" be a permissible output? We have t="0111" and w="111", hence f(t)=7=f(w)=f(w)⋅1

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solid contest

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Liked the problems.

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I personally like this round,because the problems require a lot of thinking,and some of them need you to process all those tricky corner cases,the difficulty is quite suitable for me.

but I think the Examples in D1 "spoke too much",I guessed a solution via Examples and after checking through some queries having odd length,I submitted and got AC.I would've never guessed it if there weren't so many Examples

→ Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Great Problems, Thanks to the authors

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

it was really a cool contest, thanks Wind_Eagle

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorial?

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Is there any good website conducting contests on DS Algo?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem B, checker log says 'wrong answer Number is too big! (test case 101)'. What am i doing wrong? Can anyone help. 127129777

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

    You are doing way too many calculations you should have checked the string in n^2 complexity considering all pairs of two digit number after the one digit number

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Note that if we take some subarray, we can take all the suffix which has the prefix as this subarray. compute the prefix array for every suffix using the z algorithm, Then we do normal LIS dp. The comparison will be, let x = z[j][i] for all j < i. Then if s[i + x] > s[j+x], dp[i] = dp[j] + n-i-x+1. Take the max of all dp. Submission

    Unfortunately I din have time to implement this during contest even though I copied the code for z algorithm from geeksforgeeks.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I will turn to an expert after two huors.

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

EDIT — Problem solved!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In question B , what is this issue , "Number too big!"? Did we had to perform maximum deletions? Edit:- Never Mind , Got it

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution 127123174 was rejected during the contest. However after the contest this submission of mine is accepted: 127130827 Now both the submissions are literally same except in line 67 and 68 where I have essentially just printed (l2, r2) before (l1, r1). I think this was allowed. Am I wrong?

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

    You had to print l1 r1 before l2 and r2, that was asked.

    Since, f(substr(l1,r1))=K*f(substr(l2,r2)), and K is an positive integer, do it was essential for the decimal representation of the substring formed by l1 and r1 to be >= decimal representation of the substring formed by l2 and r2, so you needed to print l1 and r1 before. And, it was even mentioned in the question itself

    For every test case print four integers l1, r1, l2, r2, which denote the beginning of the first substring, the end of the first substring, the beginning of the second substring, and the end of the second substring, respectively.

    → Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    EDIT — Problem solved! (My sieve function was getting out of bounds, which caused undefined behavior, thus resulting in my code getting RTE in competition and got accepted afterwards)

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +63 Vote: I do not like it

    Mike, will the rating after this round be applied after the rating changes in round 740 return? Or there would be a mess? I'm afraid that i won't be rated.

    → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Wind_Eagle Nice Dream Theater references in A&B!

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

    Thanks :)

    My other favourite bands include Yes, Rush, Van der Graaf Generator, Pink Floyd, ELP, King Crimson, Magma, Symphony X, Fates Warning and some other progressive bands.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sorry, misread

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

        Umgh... Where is the Rush reference in D?

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

          I thought it was a reference to the 2112 album after seeing Dream Theater and Oldfield references.

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

            Progressive Rock & Metal <3

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

            You know what, I can understand now that the half of the contest was a bit 'Rush reference' (album 2112): at least in tasks B, C, D there were magic numbers 1 and 2 (most commonly the answer).

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

127118923 I don't understand why my solution for problem C is failing on pretest 2.Can anyone review my solution or at least provide some test cases.Thank You :)

→ Reply
»
3 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

Can somebody review this simple code for problem B? I tried brute force for 2 digits solution, if one digit composite couldn't be formed. I am unable to see failed test case in my submission. What does "Number too big" error mean? https://codeforces.me/contest/1562/submission/127124101

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D?

→ Reply
»
3 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Motivating everyone for competitive coding.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks to the authors for the contest, and to Mike for codeforces.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
Hi everyone,

`Just tried to solve problem B during the contest, and ended up wasting my last hour and a half trying to figure out if I was missing some edge case :P (I am a noobie still)`
`Can someone kindly point out what I was missing? Still trying to understand..`
`Here's my submission:

127114107 Details: answer Number is too big! (test case 289)

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

    Check this case

    Case:

    Correct output is 57 but your code prints 573, which is too big.

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

      You are absolutely right! Thanks!! Can't believe I spent an hour and a half looking at these four numbers and didn't realize 57 wasn't a prime :p Thanks once again!

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The questions were really nice. I also appreciate the dream theater references! Wind_Eagle

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Apart from the tricky string questions(which are hard for me to solve), it's a very good round and i really had fun.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the statement for problem C was way too convoluted/complicated. So many formal, mathematical equations in the text make it really difficult to understand what is even asked. If you said it in text, in some kind of story, the statement could have been 5 times shorter. A good story helps us understand the problem, but the "Frodo and Bilbo" and "gold and silver" were just distractions, the actual task had no story, just a set of 4/5 conditions that had to be satisfied. (And the f(t)=f(w)*k condition is super weird)

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Today morning I got this message saying: Attention!

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

I want to clarify that the match is a pure coincidence. The solution to this problem is so trivial that my code even coincides with the official editorial solution. You can also lookup that I submitted two other attempts to this problem where I made silly errors for the case when all ones occur.Also it does not match entirely the condition used in my code is (i+1)<=n/2 whereas it's i<=n/2 in the other.

My rating has been rolled back. Wind_Eagle MikeMirzayanov sir please look into this.

UPD: No response from codeforces, I lost my rating(74). This is so Unfair.

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

I even don't know the other person . And solution of this problem is very basic to think. We just have to output three lines . In thousands of people pattern of two people may match. I haven't sent my solution to anyone also. And I used to write code on Codechef Ide and that can be Accesed by me only. So I don't know how this happened. So Mike sir Please look in to this issue

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

    The other person has posted the same comment above you too. Lol, you guys coincided again.

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

      U can go and read both the code then U will realise that it is just a coincidence. We just have to output 3 fixed lines and if our logic are same then we may write in similar fashion..

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it a violation if I submit the same code in my mini account?

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

    Of course it is. You agree that you will not use multiple accounts and will take part in the contest using your personal and the single account while you are registering.

    → Reply