Блог пользователя Wind_Eagle

Автор Wind_Eagle, 3 года назад, перевод, По-русски

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

Привет, Codeforces!

Я надеялся, что однажды у меня будет второй раунд, и вот, наконец, надежды оправдались!

Я очень рад пригласить вас на Codeforces Round #741 (Div. 2), который пройдет в 26.08.2021 17:35 (Московское время). Этот раунд будет рейтинговым для участников, чей рейтинг ниже, чем 100000110100 (то есть 2100).

Моя искренняя благодарность:

  • antontrygubO_o за отклонение задач А за выдающуюся координацию раунда! Благодарю!

  • gepardo сделал много чего полезного. Без него этого раунда бы не было. Благодарю!

  • EIK это тот человек, без которого я бы вообще не попал в спортивное программирование — мой учитель информатики. Благодарю!

  • MikeMirzayanov за платформы Codeforces и Polygon. Благодарю!

  • Вы, за то, что участвуете в этом раунде. Благодарю!

У вас будет 2 часа и 15 минут на решение 6 задач, одна из которых разделена на простую и сложную версии.

Одна из задач будет интерактивной. Рекомендуется прочитать наиполнейшее руководство по вашему любимому типу задач перед раундом.

Я надеюсь, вам понравится раунд!

Тестировали раунд: 244mhq, BigBag, Savior-of-Cross, Kuroni, programmer228, MagentaCobra, Vladik, bWayne, kassutta, asrinivasan007.

Разбалловка: 500-1000-1250-(1250+1250)-2750-3500.

UPD: Для балансировки сложности было решено добавить в раунд шестую задачу.

UPD2: Разбор уже доступен!

UPD3: Поздравления победителям!

Победители
Другие люди, которые заслуживают поздравления
  • Проголосовать: нравится
  • +520
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

good luck every one :)

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Ready for a binary problem :')

Spoiler
»
3 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

for rejecting problems A

Lol.

»
3 года назад, # |
  Проголосовать: нравится +97 Проголосовать: не нравится

If I could say..

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

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

pikachu theme? sounds interesting :))

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What is full form of P.S.??

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Useful Resource to watch before this round.!

Best of Luck Everyone!

»
3 года назад, # |
  Проголосовать: нравится +99 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +76 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

this is the person who teached me competitive programming

Should be taught lol

Really looking forward to this round!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

i guess next time is: PSPSPSPS congratulations to the winners

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

teached taught

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

So this round is about pikachu?

Spoiler
»
3 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

I think it should be available and not availible. Wind_Eagle

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Я очень рад пригласить ВАМ на раунд. (Надо "вас", просто опечатка, не минусуйте сильно :-) ). И ещё потом кусок текста на англ.

»
3 года назад, # |
Rev. 5   Проголосовать: нравится -6 Проголосовать: не нравится

D1,d2 require 1 correct soln

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

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 ?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can I expect a Easy A??

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 :(

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 :(

»
3 года назад, # |
  Проголосовать: нравится -51 Проголосовать: не нравится

IMG-20210726-002423

When my Brute Force Solution passes all the TCs.

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could you please provide the editorials in JAVA as well.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

when will the tutorial be released

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D2?

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
    Rev. 7   Проголосовать: нравится +8 Проголосовать: не нравится

    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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится

GuessForces

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve E?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Wait for editorial :)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

Today I'll loose my "newbie" virginity

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

How to prove D?

  • »
    »
    3 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +7 Проголосовать: не нравится

    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))

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

In B, the highest left digits is 2 right?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +120 Проголосовать: не нравится

Some relevant meme.

Hnet-com-image-3

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    I've prooved all the solutions :)

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve C?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Finding out the cases is problem solving too, no?

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Task E? It involved algorithms lol.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          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.

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +43 Проголосовать: не нравится

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:

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

      Yes, this is the same mistake I made.

      I think they changed the checker without any announcement.

      This is unfair.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +16 Проголосовать: не нравится

          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).

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        And my code passed after fixing the size.

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +35 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

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?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D2?

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

$$$Trickforces.$$$

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

deleted.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Deleted

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
Spoiler
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Solid contest

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Liked the problems.

»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Great Problems, Thanks to the authors

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

it was really a cool contest, thanks Wind_Eagle

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Editorial?

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Is there any good website conducting contests on DS Algo?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E?

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

EDIT — Problem solved!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.


»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +63 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Wind_Eagle Nice Dream Theater references in A&B!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Sorry, misread

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +4 Проголосовать: не нравится

            Progressive Rock & Metal <3

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            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).

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :)

»
3 года назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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://mirror.codeforces.com/contest/1562/submission/127124101

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve D?

»
3 года назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

Motivating everyone for competitive coding.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
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)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Check this case

    Case:

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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://mirror.codeforces.com/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.

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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://mirror.codeforces.com/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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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..

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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.