By awoo, history, 4 years ago, translation, In English

Hello Codeforces!

On Jun/11/2020 17:35 (Moscow time) Educational Codeforces Round 89 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Hey Codeforces!

A couple of weeks ago, we had the pleasure of hosting a webinar featuring Sergey Gordeichik, CIO of the Inception Institute of Artificial Intelligence and Director of the University’s Cybersecurity Programme.

In his talk, Sergey shared his expertise and insights on how AI is being used both positively and negatively during the COVID-19 global pandemic. He touched on topics such as the ethics of using this technology, and how it was implemented during each phase of the pandemic.

We know not everyone had the chance to tune in during the webinar, so we thought you’d be interested in having a look at the slide deck of his presentation.

You can check it out here.

If this was interesting for you, let us know in the comments, and we’ll do our best to try and provide more content like this. Keep an eye out for the final two talks in our webinar series — they might be of interest to you :)

Finally, don’t forget that this July, Sergey is teaching a course on the Cybersecurity of Cloud, Big Data, and AI. The course will be 100% online, so be sure to check it out on our website if you’re interested. Here’s the link.

That’s all from us!

Good luck in the round, and we’ll see you soon!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 ksun48 7 188
2 saketh 7 264
3 hank55663 7 320
4 244mhq 6 109
5 Radewoosh 6 126

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Hakiobo 70
2 napgod_pk 67:-12
3 Zaher 71:-21
4 VladProg 60
5 BohdanPastuschak 62:-26

1115 successful hacks and 2003 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A neal 0:00
B neal 0:02
C ksun48 0:05
D BohdanPastuschak 0:05
E ksun48 0:15
F kort0n 0:51
G rainboy 0:25

UPD: Editorial is out

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

| Write comment?
»
4 years ago, # |
Rev. 5   Vote: I like it +14 Vote: I do not like it

Is something wrong ?? why there are no comments.

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

Were are the meme squad ??

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

    A sad meme :)

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

      .

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

      My D failed system tests duo to TLE, costs me 100+ rating points.

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

        Same here bro,my D also failed :( I feel that the max_test(TLE test) should be included in the pretests. I may be biased because my solution failed, but I think once something passes pretests and it is on the edge of time complexity ==> maybe something like around 1e9 operations whereas maybe only 5 * 1e8 operations are normally allowed... then when it passes pretests, it is very hard for a person to question that maybe the solution might TLE. (I mean how can a person say whether it passed because it was just under time limit , or actually it wasn't supposed to pass?)

        Therefore I think the max_test is a basic test which should be included. But yeah, maybe they intentionally left it out as it was an Educational Round.

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

          We both could be master if not failed D!!!

»
4 years ago, # |
Rev. 2   Vote: I like it -27 Vote: I do not like it

I enjoy Codeforces comment section more than Facebook. But what's happened today!! Almost 3 hours past and only 2 comments.

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

    I think the announcement was not there on the Home page earlier.

»
4 years ago, # |
  Vote: I like it -50 Vote: I do not like it

Though I enjoy everytime..  Here are the meme squad bro :v

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

Hey sorry for asking if this is discussed before but how come all the Educational Rounds are made by the same authors awoo, vovuh, adedalic, BledDest, Roms, Neon. PS: I love their contests it's just I'm pleasantly surprised.

  • »
    »
    4 years ago, # ^ |
    Rev. 6   Vote: I like it -64 Vote: I do not like it

    I quit .

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

      I really worship awoo. I am just trying to know why they make all Educational Rounds

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

    I'm guessing Harbour.Space University signed a contract with Mike for publicity. As part of the contract, 2 contests per month must be held sporting the uni's name. Since this is a long term contract, Mike needed a reliable team of people to hold these (easier than finding a new team for each contest).

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

    And one more thing they all are from same institution Saratov state U.

»
4 years ago, # |
  Vote: I like it +147 Vote: I do not like it

Afraid of WrongAnswerOnTest2 :(

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

    Afraid of timelimited on 2 3 4 5 6 7 8 9 10.。。

»
4 years ago, # |
  Vote: I like it -29 Vote: I do not like it

I don't know but why I feel like this blog and the round are feeling bored. Weird!

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

    It had only been 50 minutes since the blog was made public. Wait for few hours, I know my true redditers won't let you feel bored

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

      I am not bored. I said if the blog and the round were a person then they seem bored. XD

»
4 years ago, # |
  Vote: I like it -78 Vote: I do not like it

Coding is Love ♥ Contest is the best option to judge yourself.. Thanks authors for all efforts . ♥

»
4 years ago, # |
  Vote: I like it -38 Vote: I do not like it

Waiting for testers' validation comment ;)

»
4 years ago, # |
  Vote: I like it +298 Vote: I do not like it

Educational round exist:

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

What do we say to Educational Div2 C? Not Today.

»
4 years ago, # |
  Vote: I like it +50 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +45 Vote: I do not like it

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

    But every time the codeforces community writes a div2-only contest, somewhere in the world 3000 people with a rating of 2100+ are sad :)

»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

why Ashishgup has so much contribution by making only 5 contest,while pikemike and other authors of educational round has very less contribution?although respect to authors of educational contest,They are really doing great great great job.

»
4 years ago, # |
  Vote: I like it -25 Vote: I do not like it

I hope this one is gonna be great. GL everyone

»
4 years ago, # |
Rev. 2   Vote: I like it -26 Vote: I do not like it

GL everyone!

»
4 years ago, # |
  Vote: I like it -31 Vote: I do not like it

I fear to comment anything on codeforces comment section because community just gives big dislike. Maybe this comment gets even more and this is the reason this is my last comment ever on codeforces.

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

why are these rounds called educational?

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

    because they promote some particular university every time

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

      Ah. So there is no actual difference between the normal contests?

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

        unlike other contests, the problems you solve don't matter, solving E is the same as A, the difference between 2 participants with the same number of problems solved is the difference in submission times.

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

        the difference is that in the official rank list, div 1 participants are also included although their rating remains unchanged.

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

          There should be some kind of tutorial that explains all this..

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

hi i m new to Codeforces, Today will be my second contest but was just curious to ask why cant we register from 0 to 5 min before contest. Due to this i missed previous contest.

»
4 years ago, # |
  Vote: I like it -24 Vote: I do not like it

I know this comment will only get downvotes....But I will say it.. The contests by Ashishgup has another level of craze... The contributions of Ashishgup is evidence of the fact...

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

    I think the contests were Ashishgup were great, but saying they are just on another level is too much. Today's contest was great too, I loved C today. And other problems were great too.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Get ready for a rating drop.

»
4 years ago, # |
Rev. 2   Vote: I like it -45 Vote: I do not like it

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

Wrong answer on test 2

Wrong answer on test 2

Wrong answer on test 2

Wrong answer on test 2

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it -41 Vote: I do not like it

44quww.jpg

PS: I miss you Jhin

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

    I'll comeback soon don't worry

»
4 years ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

Educational Round Exist !

»
4 years ago, # |
  Vote: I like it +56 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello. I am new to codeforces. When they say that the rules are the extended ICPC rules, does anybody know where these can be found. Also, are you allowed to use the internet for APIs and finding other information?

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

    Yes, just submit working solutions, then everthing will be fine. But do not talk to anybody while contest about the problems.

»
4 years ago, # |
  Vote: I like it +171 Vote: I do not like it

WhatsApp-Image-2020-06-11-at-6.17.11-PM.jpg

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

    lol it looks like it's actually more efficient. Pigeoncopter

»
4 years ago, # |
Rev. 2   Vote: I like it -69 Vote: I do not like it

BledDest should seriously stop making A/B problems in these rounds, they are usually uninteresting, lengthy and their solution mostly just have 4-5 if-else statements. I mean no offence here, and I do enjoy solving your harder problems.

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

    Any examples?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it -43 Vote: I do not like it

      .

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

        Well, I can agree with the fact that ER87 A contains some cases, but the model solution for ER88 A contains zero if/else statements.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -19 Vote: I do not like it

          Keep doing the good work having simple brute force questions as A and B are not interesting and doesn't add anything to the contest.

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

    But there were almost no if-else and casework in today's A and B.

»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Guys please stop posting shit tier memes just to increase your contribution.

»
4 years ago, # |
  Vote: I like it +53 Vote: I do not like it

 Increase in codeforces traffic.. kudos to the community

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

This is the first time when small statements are troubling me!! (Sed Lyf)

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve D?

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

    test every prime factor (if the prime fac divides multiple times go mult all of them in p^n) and its reciprocal, one of them should always work if there is a solution. i'm not sure if you can do that for every single prime factor (and thus auto break the loop saving time) but i didnt want to take any chances. reason this works is because one number will have all the prime factors and one number will have none, if the 2nd is 100% coprime then when u add the second to first theres absolutely 0 chance of it being mod p, however its possible that its mod a different prime so thats why i tested every prime (it ran within the time constrants since primes under sqrt(10^7) was like 400 or something)

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

    First observation is that d1 and d2 are co-prime (or else (d1, d2) would divide a). Second observation is that if (d1 + d2, a) = x then x divides a (obviously). So, there shoudln't be any divisor x of a such that x|d1 and x|d2. From here it's obvious how to solve: get number x2 = a / x1 so that (x1, x2)=1 and if there are no such solutions, then there is no solution

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

      Why d1 and d2 are or must be coprime?

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

        If they have a common factor, it will remain in (d1 + d2). Which will turn out to be a part of the gcd of (d1 + d2) with a. Hence the gcd will be greater than 1.

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

          Of course I believe it if you say so.

          But still, if d1 and d2 have a common factor, a has it, too? Why this?

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

        If $$$gcd(d_1,d_2) = x$$$ then $$$d_1 + d_2 = x \cdot (d_1/x +d_2/x)$$$.

        Also, $$$x$$$ must divide $$$d_1$$$. Then, $$$d_1 = x\cdot y$$$ for some $$$y$$$.

        Therefore, $$$a = d_1 \cdot z = (x \cdot y) \cdot z = x \cdot(y \cdot z)$$$ for some $$$z$$$.

        Then, $$$x$$$ divides $$$a$$$.

        Finally, we have that $$$gcd(d_1+d_2,a)$$$ must be at least equal to $$$x$$$.

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

          I understand, thanks!

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

            There was a mistake, if $$$d_1$$$ divides $$$a$$$ and $$$d_2$$$ divides $$$a$$$ does not imply that $$$d_1 \cdot d_2$$$ divides $$$a$$$, but $$$lcm(d_1,d_2)$$$ divides $$$a$$$.

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

      Hey, I implemented this approach but this is giving me TLE, Could you send me the link to your submission if you have solved it??

      My submission: https://mirror.codeforces.com/contest/1366/submission/83499523

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

        First of all, u can't do that while reading the numbers, because the complexity becomes O(n * sqrt(VAL_MAX)) which is quite big. So, you might think of precalculating something. That something is the smallest prime factor or every number <= VAL_MAX. This can be done with a sieve and the time complexity is very small. Check this out (https://mirror.codeforces.com/contest/1366/submission/83421836)

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

    if ai have only 1 prime divisor, then -1

    if a[i]%2=0 then a[i]=2^k * x, so pair (x,2) alway true

    if a[i]%2=1 then a[i]=p1^x1*p2^x2*.... which (pi<p2<...) then pair(p1,p2) alway true

    TRY TO PROVE THEM !

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

      case of even is obvious, any idea/hint on proving the other case?

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

        case of odd

        call p1+p2=2^x*k of course because p1 and p2 odd

        so if gcd(ai,p1+p2) != 1 mean gcd(ai,2^x*k) != 1

        ->gcd(ai,k) != 1 because gcd(ai,2^x)=1

        (*) we have p1 < k < p2 and gcd(k,p1) = 1 because p1+p2 % p1 != 0 (similar with p1)

        to have gcd(ai,k) != 1 so k must be a prime or product of some prime whicH ai divisor. It is impossible

        • case k is a prime: p1 and p2 are two smallest prime that ai divisor so there isn't any prime between p1 and p2
        • case k is product of some prime: because k<p2 so in this case k must be divisor for p1, we saw this is impossible in (*)

        SORRY FOR MY BAD ENGLISH

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

    Using seive you can find the spf(smallest prime factor) array for all numbers till 10^7.

    Then to query a number num, divide num by spf[num] till num isn't divisible by spf[num].

    if num==1 answer doesn't exist, otherwise answer is (spf[num], num)

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

      Can you prove this approach?

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

        Yea, So the trick which i used is to basically find 2 coprime numbers d1 and d2 such that both are divisible by the number and the product of both is the number.

        If d1 and d2 are not coprime, they will have a common divisor which will also be divisible ai

        There may be many ways to find such 2 numbers d1 and d2, I just used one of them

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

          Will any 2 co-prime numbers work? I think not. If A[i]=30, gcd(2+3,30)!=1. So they must be some particular coprime. I intend to know the thought process behind it.

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

            I missed d1 and d2 need to multiply to the number in my reply. I didn't try to prove this mathematically but with intuition this came out to be true for every number

            Edit: So consider 4 prime numbers a,b,c,d (with relevant powers) with a as spf.

            For a+b*c*d to be divisible by the number ai, a+b*c*d needs to be divisible by either a,b,c,d but you can clearly see this isn't possible since none of these 4 numbers can be taken common from the sum. So ai can never be divisible by it.

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

              But, then if I take d1 and d2 as 2 distinct primes then still they can't take a common factor out of these. Like for 30, I've 2, 3 which don't have any common factor among themselves but even then their sum=5 have the common factor which divides 30.

              Can I get the reason why this doesn't happen when we take all primes with relevant powers?

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

                Ok, I got the reason that 5 is another prime factor of 30 which still divides the sum of d1 and d2. So, I need to take all the factors into consideration for d1 and d2 and not leave any, this is to ensure that d1+d2 doesn't have any prime common with a, and that can only be done if I cover all the primes by d1 and d2.

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

            Actually it can be proved like this:

            Let, x = A[i].

            Addition of 2 no.s be say z. Now possible gcds of x & z are multiples of one of the prime factors of x. Without any loss of generality, lets say multiple is 1, and gcd be 'p'.

            Sum of 2 no.s is divisible by primes which are present in both summands. If one of the two does not have 'p', then 'p' can't be a divisor of their addition. But since we are using spf and the rest of the product, we ensure all primes are present in either of the 2, still no prime lies in both summands. Hence the proof follows.

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

              Spf may work I don't know the proof for it, but two summands being greater than p and not divisible p can also result in gcd being p. Consider case of 3&5

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

                Thanks, I have updated my proof.

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

              Nice proof , Made my day buddy!

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

              "Sum of 2 no.s is only divisible by primes which are present in both summands." This statement seems wrong. Take case of 2 and 3. Their sum is 5 which is a new prime and sum is divisible by it and not by primes of summands.

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

        See Here how I am able to understand the approach. Suppose a=(p1^x1)*(p2^x2)*(p3^x3)*...(pn*xn) where p1,p2..pn are primes. Now let's take spf=p1 so after dividing we are left with x=(p2^x2)*(p3^x3)*...(pn*xn).Now x+spf=p1+(p2^x2)*(p3^x3)*...(pn*xn).So you can see there is no common factor between x+spf and a.Hence they are coprimes and x+spf cannot divide a.

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

          But the question is why is it necessary that gcd ( (p1^x1)*(p2^x2)*(p3^x3)*...(pn*xn) , p1+(p2^x2)*(p3^x3)*...(pn*xn)) = 1. Am I missing any trivial proof?

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

        This approach is really nice, in contest I was just fooling around with stupid half witted solutions.

        See If $$$a_i$$$ is prime or primes power then it is obvious that the answer is not possible.

        Lets consider the case where $$$a_i = \prod_{j=1}^{m}p_j^{k_j}$$$ and where $$$m > 1$$$ and let $$$p_1$$$ be smallest prime (which we can easily get using classic sieve).

        So in this case sharath101 argues that we can use the pair $$$(d_1, d_2)$$$ as $$$(p_1, \prod_{j=2}^{m}p_j^{k_j})$$$. Indeed $$$d_1+d_2 = p_1 + \prod_{j=2}^{m}p_j^{k_j}$$$ is not divisible by any $$$p_j$$$ for $$$j \in [1, m]$$$ and as a direct consequence $$$\text{gcd}(d_1 + d_2, a_i) = 1$$$ $$$\blacksquare$$$

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

          Yes this the proof because (a+b)%c = (a%c + b%c)%c. If we take (d1+d2)%pi then it is always non zero as in case of p1 first modulo is zero but rest can't be zero as none of the rest pi's are divisible by p1. If we take any other pi then second modulo is zero but first is p1(it's smallest). And d1+d2 can't have anything common with A because we already checked above with all factors of A and none of them divides d1+d2.

          Sorry for bad formatting I'm typing on phone

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

          I understand that d_1 + d_2 with this split is not divisible by any p_j. However, why does d_2 need to be the remaining portion? Like why can't we have d_1 = p_1 and d_2 = p_2^k_2 * p_3^k_3 or even d_2 = p_2 * p_3 * ... * p_n?

          Also, is every number which has at least two distinct primes in its prime factorization valid since we can make the split you mentioned?

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

            $$$d_2$$$ doesn't need to be remaining portion, its just that his answer is very easy to construct as we directly get smallest prime factor using sieve.

            And not all divisions into two sets will be valid, the prime factors sets $$$d_1$$$ and $$$d_2$$$ should not share any prime factor and both together should contain all primes of $$$a_i$$$ and only then we can be sure.

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

      Bro help me plz in D

      Let we have N ,

      Now unique prime factorisation of N = p ,q ,r ,s

      Now how can we claim that gcd((p + (q*r*s---)) , N ) = 1 , can u please explain

      For ex : N = 210

      then unique prime factors = 2 3 5 7

      then how gcd((2+(3*5*7)) , 210 ) = gcd(107 , 210 ) = 1 ?

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

        So consider 4 prime numbers a,b,c,d (with relevant powers) with a as spf.

        For N to be divisible by a+b*c*d, a+b*c*d needs to be divisible by either a,b,c or d but you can clearly see this isn't possible since none of these 4 numbers can be taken common from the sum. So N can never be divisible by it.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it -19 Vote: I do not like it

    .

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

      Negative: $$$30 = 2 \cdot 3 \cdot 5$$$, but $$$a_1 = 2$$$ and $$$a_2 = 3$$$ are a wrong answer, since $$$2 + 3 = 5$$$.

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

    A simple solution I came up with was as follows: Consider all primes $$$p_1, p_2, ..., p_k$$$ which divide $$$n$$$, with $$$k \ge 2$$$. Then we consider $$$a = p_1 + p_2 p_3 ... p_k$$$. Suppose $$$gcd(a, n) > 1$$$. Then at least one prime which divides $$$n$$$ also divides $$$a$$$, however this is a contradiction (fun fact: note that the same argument can be used in a proof of the infinitude of primes). Now if $$$k < 2$$$, note that there is no solution.

    To implement this, we can do the following: using the sieve of Eratosthenes, find the product of all primes which divide $$$n$$$, and call it $$$f[n]$$$. Also keep storing the smallest prime divisor of $$$n$$$, say $$$g[n]$$$, then your answer will be $$$(g[n], f[n]/g[n])$$$ if it exists.

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

    It is clear that gcd(d1, d2) = 1 otherwise gcd(d1+d2, a) !=1 Let p be the smallest prime which divides a. Then, a = XY where Y is the largest number such that Y%p !=0 If Y=1: we are sure that there can't be 2 divisiors>1 such that gcd(d1+d2, a)=1 So in this case answer is (-1, -1) Now we will prove with (d1, d2) = (X, Y) we are done. Proof: Note the following 2 identities 1. gcd(a,b) = gcd(a,a+b) 2. if gcd(a,b)=1 and gcd(a,c) = 1 then gcd(a,bc)= 1 Now note that gcd(X,Y) = 1 This implies gcd(X+Y, X) = gcd(X+Y, Y) = 1 By (2) It is clear that gcd(X+Y, XY) = gcd(X+Y, a). Hence, find p, then find Y by dividing a_i by p until you get a_i%p!=0. X = a_i/ Y If Y = 1 your answer is (- 1, -1) else (X,Y)

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

    Simple Approach

    For an $$$even$$$ number, answer will be $$$($$$ $$$2$$$, Product of remaining odd prime factors $$$)$$$

    For an $$$odd$$$ number, answer will be $$$($$$ $$$1st$$$ Smallest prime factor, $$$2nd$$$ Smallest Prime factor $$$)$$$

    And obviously, first, you need to check whether alteast $$$2$$$ distinct prime factors for a number exists or not. if not answer will be $$$($$$ $$$-1$$$, $$$-1$$$ $$$)$$$

    Proof

    For an $$$odd$$$ number,

    Consider an example $$$ai$$$ = $$$105$$$ $$$( 3 * 5 * 7 )$$$. Ans is $$$(3, 5)$$$.

    $$$3$$$ is $$$1st$$$ smallest prime factor and $$$5$$$ is $$$2nd$$$ smallest prime factor of $$$105$$$.

    Let $$$x = d1 + d2 = 3 + 5 = 8$$$.

    $$$g = gcd(x, 105)$$$ and obviously $$$g$$$ can't be $$$3$$$ or $$$5$$$. So $$$g$$$ should be greater than $$$5$$$, which is not possible. (why? Let $$$x' = g * e$$$ , $$$e$$$ is even number, $$$e$$$ must be aleast $$$2$$$. You can see $$$x' > x$$$ if $$$g > 5$$$, which is not possible.So $$$g$$$ has to be $$$1$$$.

    For an $$$even$$$ number,

    Consider an example $$$ai$$$ = $$$210$$$ $$$( 2 * 3 * 5 * 7 )$$$. Ans is $$$(2, 105)$$$.

    $$$105 = 3 * 5 * 7$$$ (Product of remaining odd prime factors).

    You can see $$$d1 = 2$$$ and $$$d2 = 105$$$, now forget about $$$d1$$$ and ask a question from yourself. What is the minimum $$$y$$$, I should add to $$$d2$$$ such that $$$g = gcd(d2 + y, ai) > 1$$$. And you will find you need to add smallest prime odd factor, for this case it is $$$3$$$ but we are adding just $$$2$$$ ($$$d1 = 2$$$, hence the answer).

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve Question D? Couldn't come up with a strategy.

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

    83434115
    Consider the cases where the number x is odd or even.

    If x is even:

    1. If x is a power of 2, then no solution exists
    2. Otherwise, there exists some odd factor k > 1 and gcd(2+k, x) = 1

    If x is odd:

    Check for every factor k < sqrt(x) if gcd(x/k + k, x) = 1
    Motivation: If x/k and k are coprime, then they would be the solution

    Otherwise, no solution exists

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

      This should give TLE, time for hacking :p, I am sorry dude.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    https://mirror.codeforces.com/contest/1366/submission/83472749 we just need to find 2 factor which are coprime to each other

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

      Let's say we have a number 70 --> 2 * 5 * 7, now according to you we can select d1 = 2 and d2 = 5 as they are co-prime but d1 + d2 = 7 i.e, not co-prime with 70 (gcd(7, 70) = 7)? If you meant something else.. please explain again if possible..? Thanks..

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Did anyone get WA4 in D because the value of mod < 10^9 ?

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

    I initialized the min as I always do with MOD. And yup, WA4.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

I figured out that the walk will always be a path (without repeated edges) except at the last edge. So I computed $$$dp[len][v] = \text{maximum weight ending at v of walk length len}$$$, for up to $$$len = 2*n$$$. for $$$q >= 2*n$$$, the weight will increase by a constant term.

Got WA on test 12 ? What am I doing wrong?

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

    increases by different constants in O(n) ranges. its not same constant always.

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

      Does it uses idea of convex hull ?

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

      Is there no upper bound for the length of path after which we start taking the same edge?

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

        It should be m, by the pidgenhole principle. After m moves, assuming you've seen every edge once, it would be at least (if not more) optimal to have kept going back and forth once you reached the edge with maximum weight.

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

    This might give you the idea where it fails :

    Input :

    4 3 1000000000

    1 2 1

    2 3 100000

    1 4 99999

    Here you will be getting maximum answer by repeating the edge 99999. But there comes a time when 100000 will dominate.

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

    Let $$$f[u][k]$$$ denote the maximum weight path ending at $$$u$$$ using exactly $$$k$$$ edges. You can compute it for all $$$1 \leq k \leq m$$$ via $$$\mathcal O(nm)$$$ DP. Consider a long path using $$$x > m$$$ edges. It will always arrive at some node $$$u$$$ using some $$$k$$$ edges and repeatedly traverse the maximum weight edge adjacent to $$$u$$$ (let's call it $$$\text{max}_u$$$) the rest $$$x-k$$$ times. So the answer for $$$x$$$ is the maximum of $$$f[u][k] + (x-k)\text{max}_u = \text{max}_u x + f[u][k]- \text{max}_uk$$$ over all $$$1\leq u\leq n$$$ and $$$1\leq k \leq m$$$. Interpret this quantity as a line $$$y=mx+c$$$ and compute the lower hull for all of $$$\mathcal O(n)$$$ such lines. Now each line can give you the maximum answer for some range $$$[l,r]$$$ of values $$$x$$$. You can use binary search to find this range and add the contribution using some standard formula.

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

      It will always arrive at some node u using some k edges and repeatedly traverse the maximum weight edge adjacent to u (let's call it maxu) the rest x−k times.

      Why so? I don't really get the intuition behind it.

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

        Suppose we have some path, the maximum weight of an edge is $$$w$$$, but in the end, we traverse some other edge having weight less than $$$w$$$. Since $$$w$$$ is the maximum weight in our path, we can replace the suffix starting with its first occurence with repeated traversal of this edge, and the total weight becomes greater.

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

          Yeah, I thought this, but what if you still haven't visited the maximum weight edge? You can visit it and then repeat that edge from thereafter. Can't you?

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

            This path is handled by dynamic programming — basically, for every possible vertex and every possible number of steps it computes the maximum weight of path to this vertex in exactly that number of steps. That way, we can consider each vertex as the one where we start walking along the maximum edge.

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

              What I am asking is why is it sufficient to only consider m steps and then repeat the last edge? What if, let's say m = 2000, for answer for 1000000000, I start repeating the last edge after 3548 steps, will this always be unoptimal or always considered if we take only m steps? If so, why?

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

                If the length of the path is greater than $$$n$$$, then it is not simple — it contains a cycle. Since the last edge is the maximum one, we can delete the whole cycle, since the average weight on it is not greater than the weight of the last edge.

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

    Here's my AC 83474415 submission.

    1. First part handles case $$$k \le n$$$ (dp)

    2. second part handles $$$n+1 \le k \le q$$$ (convex hull of $$$mx_i * (k-n) + dp_i$$$).

    Complexity is $$$O(n*m + n*n) = O(n*m)$$$ (you could probably solve second part in $$$O(n*log(n))$$$).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is D a tricky problem? I couldn't find a way to solve it

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

    In my point of view, it's a straightforward application of prime factorization.

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

god damn it I knew C solution after one minute from reading but couldn't code it without mistakes

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

    Could you please explain your approach?

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

      You have to first notice that if you take a path starting from (1,1) and (N,M) simultaneously, then all the cells on the i-th step must have the same value. This is true since we want our paths to create a palindromic string.

      Now, we can run a bfs and store the number of cells with value of zero and one on each step.

      For each step the cost to make every path palindromic is the minimum between the number of cells with value of one(1) on the i-th step and the cells with value of zero(0) on the i-th step.

      Note: When saying "step" I mean the depth of the bfs search.

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

        I did the same using dp[i][0] for storing number of 0's till i length form (1,1) Similarly dp[i][1] , and kept getting WA on 1st test itself and lost midway :( Did you mean that the last part has to be done for the complete string or till mid of the string

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

          Till the mid of the string!

          In order to stop at the right moment I had a variable that stored the expected number of cells at the i-th step. If the number of zeros and ones at the i-th step did not match that number, then the loop would stop and output the solution.

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

        I tried to check all diagonals. Is there something wrong with this approach ?

        1 0 1 1 1 1 1

        0 0 0 0 0 0 0

        1 1 1 1 1 0 1

        first I check (1,1) and (n,m) then [(1,2),(2,1)] & [(n-1,m),(n,m-1)] and so on always updating my answer as ans+=min(total zeros,total ones)

        Idk why I always failed at test case 2 ?

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

          I did the same approach and it worked, you can check out my submission.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 5   Vote: I like it +21 Vote: I do not like it

      each line from both sides(that has the same color) should be the same so we count how many ones and zeros from each two lines and get the minimum from both and add it to the final answer except the line in the middle we don't need to change it I just couldn't code it with for loops it was hard I should've tried recursive way

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

      Take a square, calculate its distance from (1,1) , (n,m) , say d1 and d2. Now use d = min(d1,d2). Put all squares with distance 'd' in array[d]. Do this for d from 0 to (n+m)/2. Then for each array[i], calculate how many elements you need to swap so that all the elements are same. Answer will be sum of swaps for all arrays.

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

      observation : pair of cells at the same distance from 1,1 and n,m must have same no.

      now we just need to implement it and the best way is https://mirror.codeforces.com/contest/1366/submission/83470989 (the code is very small so i guess there is no need to explain the implimentation)

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

    Just in case you require a clean implementation of C, ignore otherwise

    CODE
»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Feeling great. For the first time solved 5 problems in div2 contest. Thanks awoo. Hoping that my solution would pass the system test.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What was in Test case 17 for F? :(

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +86 Vote: I do not like it
    puts("2000 1999 1000000000");
    forn(i, 999) printf("%d %d %d\n", i + 1, i + 2, 999999);
    puts("1 1001 1");
    forn(i, 998) printf("%d %d %d\n", i + 1001, i + 1002, 1);
    puts("1999 2000 1000000");
    
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's wrong with this code. Problem B : Your text to link here...

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

    Please help??

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

      Alright so I believe you got the algo wrong, the idea is to find the largest segment of numbers possible, by unioning segments that have an intersection with the current segment (initially the current segment is of size 1, and has value = [x, x]). Here order matters, you can't find the largest union with cur across all the segments [l, r] that they give, you'll have to find the largest union in the order of input. Have a look at my submission for more clarity: Link .

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

    if there are no pair[l,r] contain x then the answer is 1, but in your code it's 0

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

    Initialise L = x, R = x. Iterate through segments in line. If there is overlap between [l,r],[a,b] update the [l,r] segment to their union.

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

    Initialise x to 1 and in the last if condition replace r-l+1 by r-l..this works fine

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

      You can calculate answer in the end as $$$ Ans = R-L+1 $$$

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

        But what if that condition is never met : Example : x=1 , l= 2 , r=4 ,m=1,n=5 epsilon_573

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

          Answer will be 1. Because only x=1 can be 1.

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

            I think you should say Ans = max -min +1 instead of r-l+1 just a bit of confusion over there . Hola !!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the 2nd test case for D? please tell

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I feel I was/am so close to solving E ... can someone take a look ? 83459283

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That C. I first implemented a solution to traverse through all diagonals and then realised it isn't the right strategy (because of test case 1, part 2). I should look at the test cases carefully before implementing some crap smh. C turned out to be easier than I thought after making an observation (which you can see in my submission).

D was tricky. I don't understand (yet) why my solution fails (also, it's brute force maybe? so it'd TLE anyway). Maybe I need to look through some probable bugs in my code... Any ideas about D? I think I've seen a problem similar to F before but never solved. Any ideas on it too would be good. Thanks. I found the problems really interesting.

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

    Can you tell about C? I couldnt come up with any idea

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

    What observation did you make in C ?? after first reading I thought I had to convert all the strings into a palindrome (if they are not obviously),Moreover the test cases created more confusion.I still can't get the question clearly :( My bad

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

      Observe that if you start your journey from the cell (1, 1) and (n, m), the reachable cell after the i'th step have to contain the same number(either 1 or 0). So decide greedily which one will minimize your answer.

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

        Will our choice at length n-i of string would depend on our choice of i done earlier ?? (Will the value at cell(i,j) change )

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

          I didn't get your query clearly. can you elaborate on it ?

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

            for example if the matrix is [[1,0,0] , [1,1,1] , [0,0,1]] the final matrix will be of which form ??

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

              stunareeb_09 there can be two possible forms we can obtain. they are

              1 0 0   1 1 0
              0 1 0   1 1 1
              0 0 1   0 1 1
              

              with the cost of changing the cells (2, 1) and (2, 3) in the 1st possible form and the cells (1, 2) and (3, 2) in the 2nd possible form.

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

        What about the testcase 1 1 0 1 How do you handle cases like these where some paths after i'th step will be completely independent of each other ?

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

          This is the case when the length of the path is odd. In this case you never have to change any value of the middle cell of the path since they are independent.

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

      See that all squares that are equidistant from (1,1) and (n,m) need to equal.

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

    .-._._-_.-_.-._-..
    In D, you have to observe that if number has only one distinct prime factor than the answer is (-1,-1), otherwise, the number has at least 2 distinct prime factors.
    If the number is even then it must have an even and an odd prime factor whose sum is an odd number and the result will be (2, any_other_prime_factor).
    If the number is odd then it's all prime factors ar odd and if you sum up any 2 of them then you will get an even number and the result will be (prime_factor1, prime_factor2).

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

      No gcd of two different parity is not always 1.Eg (6,15)=3

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

        Ops, My bad. Yes, You are right. But the main observation is that since the prime factors are relatively co-prime so the sum of them will be coprime to the number itself.
        Let's prove it by contradiction.
        Let the number we are considering be n and the prime factors are f1 and f2 and the gcd of them is g = gcd(f1, f2).
        So we can write f1 = g * a and f2 = g * b for some positive integers a and b.
        So f1 + f2 = ga + gb = g(a + b).
        Since n % f1 == 0 and n % f2 == 0, so n % g == 0.
        Observe that if g > 1 then f1 and f2 can't be the answer.
        Since f1 and f2 are coprime so g must be equal to 1.
        Hence the sum f1 + f2 will be coprime to n.

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

          30 = 2*3*5

          gcd(2+3,30)!=1

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

          No, it's not. Suppose n=30, and its prime factors are 2,3 and 5. So sum of 2 and 3 isn't coprime to 30.

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

            Sorry for my poor observation :(. The answer should be (factor1, n/factor1^k). I will come up with the proof later.

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

    Let the prime factors of a = p1^x * p2^y * ..* pm^z. Take d1 = p1 and d2 = a/p1^x Since both d1 and d2 have no prime factors in common, their sum d1 + d2 has no prime factors in common with a which gives gcd(d1 + d2, a) = 1.
    Obviously the answer is -1 if any of d1 == 1 || d2 == 1
    Code of this approach 83482353

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve G? I couldn't optimize my DP from n^3 to n^2.

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

    Let $$$f[i][j]$$$ denote the minimum answer for suffix $$$s_i$$$ and $$$t_j$$$. If $$$s_i=t_j$$$ you can update with $$$f[i + 1][j + 1]$$$. Otherwise you have to match $$$t_j$$$ with some $$$k > i$$$ with $$$s_k = t_j$$$ and clean up the stuff between $$$s_i$$$ and $$$s_{k-1}$$$. Notice that before reaching $$$s_k$$$ the character labels don't matter: it's either append a character or delete one. So you essentially have a bracket sequence and you should delete some of the positions to turn it into a correct bracket sequence. Now you can either delete the current character and update by $$$1 + f[i + 1][j]$$$, or, you can skip the first balanced portion starting at $$$s_i$$$ and update by $$$f[\text{to}_i + 1][j]$$$ where $$$\text{to}_i$$$ is the right end of the balanced bracket sequence starting at $$$s_i$$$. You can precompute $$$\text{to}_i$$$ in $$$\mathcal O(|s|^2)$$$ and run the DP in $$$\mathcal O\left(|s||t|\right)$$$.

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

      Addition: $$$\mathrm{to}_i$$$ can be found in $$$\mathcal{O}(|s|)$$$. Maintain the bracket positions in a stack. (83439327)

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

      That assumes that if we don't delete a character or match if some character of t, we'll preserve the bracket sequence starting at that charactet. Why would we always preserve it?

»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

It took me 47 minutes for A and 6 minutes for B.

Life's weird

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

    I solved B, C, E and didn't solve A. Life's weird indeed.

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

      Update: Nope. My E got hacked. I guess I'm just stupid today.

»
4 years ago, # |
  Vote: I like it -25 Vote: I do not like it

Solved A and B fastly in first attempt. After that just saw my rank getting worse and worse. Sed life.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems B and C were really nice. I didn't manage to solve D during the round, but it was also really nice. I just think that problem A was quite boring... Beside problem A, the contest was really nice!

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

Can anyone give me testcases where my Solution for B fails?

Edit: Nvm got it.

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

    Just change the last line of your code to cout << "1" << endl and see the magic.

    Because at the end, a[x]=1 is always true. Feel sorry for you tho.

    Edit: ok

»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

 200IQ play be Deathly_Hallows.

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

Kind suggestion for the future contests — please be consistent with moduli (is that plural from modulus?) over multiple tasks — there's less gotcha when in every task we deal with the same number.

»
4 years ago, # |
Rev. 9   Vote: I like it +6 Vote: I do not like it

Why is A- min((a+b)/3,min(a,b)).

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

    after each move, total sum of a and b decreases by 3, so (a + b) / 3 will hold the answer, and min(a, b) because in case min(a, b) * 2 < max(a, b), the logic above wouldn't work, because in the best case you can decrease min(a, b) by min(a, b), case a = 18 b = 2 ans = 2

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

    Case 1: If a >= 2 * b or b >= 2 * a, answer is clearly min(a, b).
    Case 2: Now, let's assume this is not the case. Now, every time we will choose 2 from the larger pile and 1 from the smaller pile. A time will arise when the larger pile will become smaller (else it's Case 1). We observe that after this time arise the difference between the 2 pile sizes is at most 1. So, when we are unable to make any other tool, the remaining items in the piles can be (0, 0), (0, 1), or (1, 1). So, we must have utilised all the remaining items.

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

The description of B is really confusing and I was stuck at B for an hour. l_i≤c,d≤r_i this statement has two meanings: 1.l_i<=c and d<=r_i 2.l_i<=c<=r_i and l_i<=d<=r_i

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

is the hacking just for fun and not rewarded with points?

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

    In Educational and div3,4 rounds, Yes !!

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

      Bro help me plz in D

      Let we have N ,

      Now unique prime factorisation of N = p ,q ,r ,s

      Now how can we claim that gcd((p + (q*r*s---)) , N ) = 1 , can u please explain

      For ex : N = 210

      then unique prime factors = 2 3 5 7

      then how gcd((2+(3*5*7)) , 210 ) = gcd(107 , 210 ) = 1 ?

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

    I you hack somebody which then falls behind you in ranking, you will raise one position. So just hack the ones right in front of you.

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

    Why so many hacks in D?

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

      Because D is the new G

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

      because they failed with this case:

      500000 9999991 9999991 9999991 ....

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

      There was no pretest to eliminate solutions with complexity N(sqrtN) whereas required complexity was nlogn :

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Educational Rounds always feel like Div 1.5

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

    can relate, i'm doing 3 problems in div2 and div3, but in this educational I sucked a lot

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what is wrong in my code for problem C?

https://mirror.codeforces.com/contest/1366/submission/83448870

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

    I think your solution is failing for test cases where n>m. Let's say n=8 and m=2 then your solution might give Wrong answer.

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

One of the best contest till now! But I could not solve the errors in C on time.

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

Will $$$O(n*\sqrt{a_i})$$$ solution for D pass?

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

https://mirror.codeforces.com/submissions/karthik1999rocks and https://mirror.codeforces.com/submissions/karthikchunduru.

These both accounts belong to the same person and he's changing his codes a bit to not get caught. He has cheated in previous contest too.

MikeMirzayanov

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please explain C?.
Thank you

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

    C is simple. Since all paths are palindrome, we need to have the bits as same at same distance from (0,0) and (n-1,m-1), unless they are equidistant from both(it'll happen only if n+m-1 is odd).

    For eg, take {{1,1,0},{1,0,0}}. Here n=2,m=3 and n+m-1= even. At distance 0 from (0,0) and (1,2) we have 1 and 0, we need to change any one of them. Similarly at distance 1 from (0,0) and (1,2) we have 1,1,0 and 0, we need to change any 2 of them. So finally the answer for this case is 3.

    We can ignore the ones that are equi-distant from (0,0) and (n-1,m-1), because the paths would be palindrome anyway. Hope that helps! 83443782

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

In problem D, why can't we choose any pair of prime divisors of A[i]?

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

    It's possible that their sum will be divisible by some other prime factor. Ex: A[i]=3*5*7, choose 5 and 7.

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

    case a[i] = 2 * 3 * 5, if we choose (2, 3), gcd(2 + 3, 2 * 3 * 5) = 5 # 1. A good strategy is choosing (2 * 3, 5)

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

    Take the example of 30. The prime factors of 30 are 2,3 and 5. Now if we choose 2 and 3 __gcd(2+3=5,30)=5>1.

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

    If A(i) = 210, no pair of prime divisors will satisfy the condition.

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

      i wrote a basic brute force. Then saw this. All the multiples of 210 didint satisfy the condition.

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

    Right, so what is the good strategy for choosing such pair-(d1, d2), where d1 + d2 isn't a factor of A[i]?

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

      Notice that we need the stronger condition gcd(d1 + d2, A[i]) = 1. Now let us suppose not. Then there is a prime divisor p that divides both A[i] and d1 + d2. To block this from happening, notice that if we ensure for every prime divisor p of A[i], p divides exactly one of d1,d2, then p won't divide d1 + d2. So if A[i] has more than one prime factor, we can pull out a prime factor completely(as the highest power that divides A[i]) as one divisor, and the rest as the other. Otherwise, A[i] = p^k for some k, and prime k. Then clearly there is no solution, as p will divide all non-unit divisors.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem C?

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

    All values which are having same manhattan distance from the source node and the destination node must have same values for the path to be palindromic. , I hope this helps ,

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

      can we find all possible paths from (1,1) to (m,n) like bfs and store it in this (vector<vector> paths) and then check cost to make each path palindromic sequence?

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

        Wouldnt It give you TLE! As all possible paths will be approx (n+m-2)!/((n-1)!*(m-1)!),by lucas theorem I think and it will be too much to get all the paths, Think intuitively.

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

      can you share your code?

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

What is the tricky case that people are getting hacked on for problem E?

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

    I managed to hack myself using this:

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

    The test case I was using is

    3 3
    2 5 6
    1 5 6
    

    Basically, a lot of solution worked backwards, but never end up checking if the smallest value is actually in the array

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the idea behind A...I managed to solve it somehow but my approach seems to be very different from most submissions

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Couldn't solve A and B so didn't attempt the contest. Sed Lyf

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I did problem-C just after the contest. I saw the pattern was not able to do it in time.

»
4 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Self hacking!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What about 1366E - Два массива?

It is somehow related to stars'n'bars. I can create min and max positions for every bar, but I cannot think of a way how this works out in calculating ans.

Sombody explain?

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

    one observation is if you are starting the ith subarray from index j then the (i+1}th subarray will definetely start from index p which will be always more than j... if you get the above point .. then make dp[i]--no of ways ways to start the ith subarray; dp[i]=dp[i+1]; suppose that there are 2 point from where ith subarray can start than dp[i]=2*dp[i+1]...and 1st subarray can only start from 0th index of array a; dp[1]=dp[2]. code-- 83476050

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

      Sorry, I do not understand at all.

      We have for every element in b[] a most left possible position where the segment can start, and a most right position where it can start.

      So, how do we come from there to some dp?

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

Was i the only specialist who could not solve problem A?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry for asking such a trivial question, could someone pls explain me the logic of A question??

»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Next time editorial before contest!

»
4 years ago, # |
  Vote: I like it +42 Vote: I do not like it

For people looking for solutions before the editorial comes out, I discuss the solution paths for all problems starting at 1:56:00 here: https://www.youtube.com/watch?v=qc07Al4sYHA.

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

Is there a dfs sol for C? I tried but couldn't solve it.

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

Ok so this works for D. Can somebody explain why?

If $$$ num = p_1^{a_1}.p_2^{a_2}.p_3^{a_3}....p_n^{a_n}$$$

then split into $$$ d1 = p_1^{a_1} $$$ and $$$ d2 = p_2^{a_2}.p_3^{a_3}....p_n^{a_n}$$$

If only one prime factor, then there is no solution.

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

    That's simple. If num had a prime factor p, that divided d1 and d2 both, we'd have gcd(d1+d2,num)=p >1. To resolve this case, we need to get the highest power of any prime factor in num, and assign it to d1. Now, if d2=num/d1, we can rest assure that, there can't be a p, such that it'll divide d1 and d2 both (easy to follow). So, p can't divide d1+d2, and thus we have gcd(d1+d2,num)=1.

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

    d1%p1 is 0 and d2%p1 > 0

    This implies, (d1+d2)%p1 > 0

    Now, same goes for p2,p3,p4... as d1%p2 > 0 and d2%p2 is 0

    So, None of the primes divisors divide (d1+d2). Thus gcd(d1+d2, num) is 1

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

      Been looking throughout the comments for this. Thanks kind stranger!

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

    This works because gcd(d1,d2)=1 implies gcd(d1+d2,d1*d2)=1

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

how to solve E!!

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

    So here is my approach. First of all we can see the array A must contain all the elements of B and if not then there is no way to partition the array.

    Now if there are multiple occurences of any bi in array A then we take the rightmost index having this value because since the array b in strictly increasing if we take this value in more than one subarray then the condition bi<bi+1 won't hold true.

    After we have got the index for each of the m elements in array A let's take any i s.t bi<bi+1 and we have the element bi at index id1 and element bi+1 at index id2 in array A.So now the the minimum of array from index id1 to id2 should be equal to the bi as if there is any other element which is smaller than bi then again some subarray will contain it and it will become minumum of that subarray and the condition of array b will be voilated and there is no way to partition the array.

    After we have checked all the above condition we are sure that there is some way to partition the array. Now for each element(the m indexes which we have got from array B in array A) we try to find how much we can go left in array A such that it will remain the minimum from that index. We can do it with the help of sparse table which stores minimum for each range and then applying binary search to find the leftmost position s.t it is minimum from that position to that index. After that multiplying all the ranges for each index we will get our desired result.

    Here is the link to my solution https://mirror.codeforces.com/contest/1366/submission/83514102 and here is a similar problem which can be done using this technique https://www.hackerearth.com/problem/algorithm/class-monitor-c76dc24a/

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/1366/submission/83460041

For C I've used the method of equidistant pts from 1,1 and n,m should be same

But I'm getting WA on test 2 , can someone help ?

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

    Your construction of distances if fairly complecated and most likely wrong.

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

    Previous Comment Why don't you check this out? I have explained my approach (similar to yours) and also attached my code. It might help!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain what exactly problem B statement says?

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

    You get some segments and you are allowed to swap the elements of an array which are within these segements.

    Then you should tell on how much different position a special element x can be moved by these swaps.

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

      can you pls tell me what is wrong with my code 83494327

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

        Well, it does not work like that.

        Use a simpler aproach. Before the first segment there is one possible position, it is x. After the first segment there are two posibilities:

        • x is in the segment, then all positions in that segment are possible, so there is a segment of possible positions of x
        • x is not in the segment, then x cannot be moved

        Think about how the segment of possible positions change while there are processed more input segments.

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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

    Changing Hello Codeforces! to Hello Hackforces! would be better :D

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what is wrong with my solution for C? https://mirror.codeforces.com/contest/1366/submission/83477191

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Tutorial for D-Two Divisors

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help what's wrong with my code https://mirror.codeforces.com/contest/1366/submission/83479883. I have traversed the matrix from both ends and calculated total number of ones and zeros of each step. Adding the min(ones,zeros) after each step to the answer.

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

    why are you swapping m,n if n>m ?

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

      Because I wrote my code assuming m>n and I am swapping their values if that's not the case. I think we can do this, right?

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

        if you swap m,n the structure of a[n][m] will change. for exa — check this test case

        1

        4 2

        1 0

        0 0

        0 1

        1 1

        your code output is 1 (right ans is 2) as it is considering a[n][m] as

        1 0 0 0

        0 1 1 1

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

          I made the required changes and it worked. Thanks a lot. This is why I love this CF community!!

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

      Is the logic at least correct?

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The time limit for problem D was very tight. Probably, it can lead to some correct solutions failing too. Please check this awoo adedalic

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

Problem E. Can someone please help me find issue with my solution? Was able to pass sample test cases but it failed on submission.

awoo Thanks for the great contest. If possible can you check?

Solution Link : https://mirror.codeforces.com/contest/1366/submission/83481690

Here is my greedy approach. For each element (at index i) in B, I keep three variables

0-indexed
start[i] and end[i] : denoting the range in Array A in which B[i] is minimum.
start[i] denotes index in array A from where B[i] can start being minimum (first occurrence of B[i] from where it can start being minimum). 

mov[i] : the index of the last occurrence of B[i] in range (start[i], end[i]), such that B[i] is minimum in range (mov[i], end[i]) in Array A (I calculate this for B[1, m-1])

Note : That means for B[i-1], I can choose subarray ending at index from end[i-1] to mov[i] - 1
I calculate answer for each i from 0 to m-2
ans = 1
ans = ans * ((mov[i+1] - 1) - end[i] + 1) for all i in range 0,m-2

Example : 
A     : 12 10 15 20 20 25 30
B     : 10 20 30
start : 0  3  7
end   : 2  6  7
mov   :    4  7
ans   : 2  1 

ans = 2 * 1 = 2
»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

My solution for D is kind of strange.

Firstly I tried only checking all the pairs of prime factors of n. That algorithm wasn't always correct, it fails for example on n=210.

Then I wrote a brute force solution and ran it on all n<=10,000,000. There were only several pairs of divisors that were found by the brute force which weren't found by the original solution.

Those pairs were: {{2,9}, {2,15}, {2,21}, {2,35} ,{3,10}}. So I modified the original solution to firstly check those pairs and only then proceed, that got accepted :)

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

    This only happens for multiples of 210. Found the same pattern just before 5 minutes of round end but couldn't implement in time.

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Problem D was just designed to satisfy hackers.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In problem E I didn't notice that B is increasing but was trying to solve for general B The best I could come up with at the contest was O(NM logn) Using DP[starting_point][segment_index]. So I was wondering if there is a better solution for that version of the problem!

»
4 years ago, # |
  Vote: I like it +64 Vote: I do not like it

While thinking after the contest, I've come up with a great visualization for problem A. So I want to share it.

If we think of our resourses left as a 2-dimensional space (amount of sticks, amount of diamonds) crafting one item moves us towards origin with a rules of a chess knight: it is either $$$(-1, -2)$$$ to craft a sword or $$$(-2, -1)$$$ to craft a shovel. So, now problem actually asks how many turns can you make with the knight in a position $$$(a, b)$$$ without moving to negative coordinates.

We can draw the grid out and see multiple cases. Now it becomes relatively easy to see that sticking close to main diagonal ($$$X = Y$$$) prevents us from falling to $$$X$$$-axis or $$$Y$$$-axis early and allows making maximum possible moves. However it is not always possible to reach main diagonal, if $$$X$$$ is more than $$$2$$$ times greater than $$$Y$$$ (blue area) or vise versa (green area), we will cross the axis faster. In such cases least coordinate does only matter and define the answer ($$$Y$$$ for blue area and $$$X$$$ for green area). Considering red area, sticking close to the main diagonal will balance out coordinates thus each move will reduce sum of coordinates by $$$3$$$, so we can repeat this $$$\lfloor \frac{X+Y}{3} \rfloor$$$ times. So this is the answer here.

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

I'm gonna lose it. WHAT IS TEST CASE 12 OF F???

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

awoo would you please take a look at this...

It seems that the hacking got stuck and now there are some hacking attempts in queue for over 30 mins :(

queue

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why do we generally get the editorial for educational rounds a bit late than general rounds(where now a days we get just after the contest)? Is there some specific reason or its just that the writers prepare it late?

I thought that they might be waiting for the hacking phase to end but in div3 rounds ,editorials were out ever before the end of hacking phase.

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

MikeMirzayanov When i press "Hack it!" button i see this massage "Illegal contest ID". What is the problem?

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

    May be you clicked on hack it without open the code.. 1st open the code then need to click hack it.but now hack phase over

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

      Yes, i can hack after i open the code, but the hack button still works only in the interface of code viewer. This is not very obvious and i still think this is bug.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody tell why my code gives WA 83494327

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

    I don't quite understand what you intended to do while swapping. Nonetheless, one simple counter-example that I can think of is: 9 5 2 4 6 1 3

    In this example, the first swap can reach from 5 to [4,6], the second swap does nothing. But in your code when you swap, you somehow push [1,3] into v.

    You shouldn't need the inner for-loop though. You can simply keep track of the range, e.g. [4,6] after the first swap, and extend the range if [a,b] overlaps it.

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

      I push [l,r] in v if this segment has x in it. If it doesn't have x I check if there exist a segment in v such that [l,r] and that segment in v have some common numbers . The swap is intended to check the second condition . for ex- when a=1 ,b=3,x1=4 and y1=6, it swaps the value bcoz I assume a>x1. So for them to overlap somewhere a<=y1. After swap a=4,b=6,x1=1,y1=3.Since 4<=3 is false [1,3] is not pushed. The program works fine on the counter example. UPD:Actually I got the answer,the problem was arising bcoz of swapping. If in a iteration I was swapping , I was not restoring values of a and b for next iteration. Btw thanks for your help.

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

        Ah you’re right. Sorry for being misleading. Glad you found the problem!

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

Problem E is deceptively easy. There are a few things to notice. we consider the contiguous sub-arrays as tubs. 1> There can be no element less than b[j] occurring in that tub in the next tub.

2>As we iterate through n->1, we go on marking the LATEST element which is same as b[j]. We go on decreasing j from m-1 to 1 as we visit, and mark in the visited array the latest occurrence of the element b[j]. Notice that only latest occurrence is important. This is because of point 1>.

3>Now we also mark the latest element less than b[j] with index<j.this is because we can obviously not include that element in our subarray otherwise the minimum would be less than b[j]. 4>now there are only visited[j]-marked[j] possibilities. As the elements after the mark[j] have to be included in the previous tub otherwise the minimum would be less than b[j].

5>we also note that the minimum of the array must b[0],and the last subarray ends at n-1 index.

6>we simply multiply all the possibilities, and we are done.

Here is the attached code https://mirror.codeforces.com/contest/1366/submission/83496548

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice problems. Thanks.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why is there no Tutorial for round 89??? :(:(:(

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help with the solution and approach with problem C?

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

    Elements which are equidistant from (1,1) and (n,m) should all be same(Handle cases when m-n is even) .Hope this idea helps , in case you need more help you can go through comments above there are some pretty good solutions.Don't know why the Editorial is late.

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

      Thanks but I am not able to understand some codes , I have understood 3/4th of the logic. We store the number of zeroes and ones at the sum of indexes. But the traversal to count the answer is confusing me

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

        Can you post the code you are trying to understand

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          #include<bits/stdc++.h>
          using namespace std;
          int main()
          {
          
          
          	int t;
          	cin >> t;
          	while (t--) {
          		int n, m;
          		cin >> n >> m;
          		vector<int> zero(m + n - 1) , one(m + n - 1);
          		for (int i = 0; i < n ; i++) {
          			for (int j = 0; j < m; j++) {
          				int x;
          				cin >> x;
          				if (x == 1) {
          					one[i + j]++;
          				}
          				else {
          					zero[i + j]++;
          				}
          			}
          		}
          
          		int ans = 0;
          		for (int i = 0; i < (m + n - 1) / 2; i++) {
          			ans += min(zero[i] + zero[m + n - 2 - i], one[i] ]+ one[m + n - 2 - i]);
          		}
          
          		cout << ans << "\n";
          	}
          
          }
          
          
          
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I have understood the logic of the logic for the filling of one and zero array. But the logic for the second loop why is it till (m+n-1)/2 ?

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

              because you add the last half with the first half (1st one with last one,from first 2nd one with from last 2nd one.... like this).

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

              Look at an example matrix .. to be equidistant from 1,1 and n,m that should be maximum sum

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I think it is a sign of strength and nobleness to publish the editorial as early as possible, awoo

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

very weak tests

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

    Ikr, I got E accepted in the last 3 mins for the first time in div2. Today I got up to find out it got hacked :(

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

      that s sad:))

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

      but i noticed that a lot of participants were hacked on problem E, before the hacks there was over 700 participants who solved it and after the hacks the number decreased to 500

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

        Yea, because a very simple case was missing from the main tests. I realized it the moment I saw I got hacked. But yea, there's always a next time..

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey MikeMirzayanov , I have got TLE on D whereas i have used O(NlogN) Solution. When i resubmitted it after final standing it got accepted. Solution from contest — https://mirror.codeforces.com/contest/1366/submission/83442824 Solution After contest -https://mirror.codeforces.com/contest/1366/submission/83505708 They both are same solution.. Kindly look at the issue and try to resolve if possible

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

    The judging time is not a constant for a problem, so you re just unlucky. Try your best in the next round

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

where are the editorials?

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

The system notified me that the code coincided with another person's code at 1366B, so my submission was skipped. Code coincidence is just a coincidence, and my code has always been in this style. This is an easy problem to solve. The code length is very short. Code coincidence should be a relatively common thing. I don’t know how to fix it. (My English is not good, this text is generated by Google Translate)

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

    Happened to me once. But its mentioned in the rules, if you can prove that the coinciding source code was present somewhere online before the start of the contest you'll have your rating back, but if you were compiling it online on Ideone or something publicly you'll have to forget about this contest!! If its the latter start compiling offline on your system. https://mirror.codeforces.com/blog/entry/8790

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

      Thank you for your reply:D.My code is completely written by myself, and the similarity of the code is a coincidence. . .

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

    Do you use any online compiler?

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

      No, I just use VSCODE

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

        Can you share link to two solutions?

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

          Your solution 83404399 for the problem 1366B significantly coincides with solutions Arsengotovitsaksoru/83400791, iwriaw/83404399.

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

            MikeMirzayanov

            I think codeforces should look into these matters as for such small source codes, plagiarism detector should be turned off. There is a very high chance of coincident codes.

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

why my submission give tle with unordered map 83516884

but work fine with map 83517023

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

When will tutorials out?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That. Was. Fun.

Maybe my 1,740ms solution for D seems weak, beacuse I get 34 attempts to hack. And they can only hacked my 1,996ms solution for D.

That was really fun.)

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Any editorial??

»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Educational round and no editorial, how ironic! We need EDITORIALS.

»
4 years ago, # |
  Vote: I like it +53 Vote: I do not like it

awoo.

I got this message:

"Your solution 83403019 for the problem 1366B significantly coincides with solutions Arianfk/83399024, diogoaos/83403019. 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."

But I didn't copy any code from anywhere! The solution was very short, of course it could be the same. I don't understand why only I got kicked from the contest.

I didn't cheat, I hope this is fixed (I think I did well on this round, wanted to see my rating change, very disappointing).

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

    MikeMirzayanov

    I think codeforces should look into these matters as for such small source codes, plagiarism detector should be turned off. There is a very high chance of coincident codes.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/1366/submission/83524020 Can anyone tell the issue with my solution for b?

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

    The first test in your code (when you compare l and r to x) enters even if b is true.

    So, for this test case.

    1
    5 4 2
    1 5
    3 5
    

    The correct answer is 5 (all the range), and your program answers 3.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Where is the editorial?

I'm a Chinese and it's difficult for me to watch the editorial videos on Youtube without vpn

Is there anybody warm-hearted who can put the editorial videos on websites that Chinese can visit without vpn?

Thanks

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

    Is using vpn a problem ?

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

      No.

      But I'm lazy.

      Could you recommend a stable one?

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

        Paid ones there are plenty, but if you want a free one try softether vpn client. You can make an ssh account in vpnjantit.com and connect to your preferred server.

        If you're a student you can rent your own server from azure for free and use it as your own vpn server using softether vpn server manager.

        Both are stable but the latter is much more reliable

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

common man , in all this where is editorial

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

awoo please upload editorial.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks all the authors because this contest makess me #specialist for the first time.. I know its a little tag but when you touch a new tier , its great feelings <3

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I would like to sincerely thank the writers and coordinators of this round for taking the time to avoid confusing guarantees, especially in problem G. It is great to see Codeforces taking steps to improve, especially since it is already such a great platform with an amazing selection of great problems!

My reaction to first reading the problem at 54:13 and how happy I was that this adjustment was made might cheer your day :)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where is the editorial?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone could hack this? For problem D, I use brute force and memorize the answer. 83545291

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

    UPDATE: I think it could be hacked by the numbers with the most factors. Here is the file. But I couldn't do uphack. Anyone could help me. Link

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Finally Published the Editorial .More than After 1 day.