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

Hello Codeforces!

On Jan/29/2020 17:35 (Moscow time) Educational Codeforces Round 81 (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 problems and 2 hours to solve them.

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

Good luck to all the participants!

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

Hello Muscat

Hi Codeforces!

As a special prize for the Educational Round 81, we would like to invite the top participants to take part in our Hello Muscat ICPC Programming Bootcamp, which will take place in Oman, from March 19 to March 25, 2020. The prize will cover the participation fee, accommodation, and half-board meals for the entire duration of the bootcamp (except flights)!

There are three requirements to satisfy:

  • You took part in at least 10 rated contests on Codeforces
  • Your max rating should be less than 2400
  • You should be eligible for ICPC and/or IOI 2020+
Fill out the form→

Good luck to everyone!

We are also excited to announce that we are working with our partners to provide free participation (flights not included) for the teams going to the ICPC World Finals 2020, which will take place in Moscow. If you and your team qualified for the Finals, fill out the form below to see if you’re eligible.

Apply Now→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 nickluo 6 177
2 KrK 6 184
3 NoLongerRed 6 185
4 Anadi 6 200
5 neal 6 204

Congratulations to the best hackers:

Rank Competitor Hack Count
1 GiantTornado 58
2 rachit_raj 51:-1
3 harshraj22 41:-5
4 Ahmad__ 35:-1
5 _sad_ 33:-2
1096 successful hacks and 873 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A antontrygubO_o 0:01
B neal 0:05
C IgorI 0:07
D NoLongerRed 0:06
E A_Fan_of_the_AK_King--lk 0:14
F Combi 0:23

UPD: Editorial is out

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

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

Educational Rounds always have good problems. Hope for a good contest.

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

Finally a contest ! Hope the gap between rounds will decrease

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

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

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

    It feels more longer to users whom Div.3 contest is unrated for.

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

2f04e47240ec34bbe32.png

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

Petition to MikeMirzayanov to decrease the gap between forthcoming contests.

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

Looking forward to interesting problems

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

Vovuh are you the Vladimir Petrov who won IMO Gold in 2018?

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

Lets hope that the frequency of contests increases.

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

Problems are difficult!

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

B and C are difficult.

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

Even if the problem is not original, I think providing links to such problems and solutions during contest violates the CF round rules. Let us keep silence until the end of the round.

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

Finally solved the first problem. Heading for second. So much to learn...!!

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

I guess, someone accidentally swapped B and D :)

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

    D is easy if you know some number theory, but B is just casework, I don't think it's harder.

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

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

A Problem of APIO 2016:Boat

A harder version of problem F.

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

    I consider C as a problem which I've solved it before.Unfortunately,I couldn't remember it exactly while the round.Now I can get it.

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

How to solve D?

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

    Find g=gcd(a,m). Divide m by g, i.e. let f=m/g. Find Euler Totient Function value of f i.e. phi(f).

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

      Why?

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

        Okay, we know gcd(a, b) = gcd(b, a%b)

        So gcd(a+x,m) = gcd(m, (a+x)%m) and value of x lies between [0,m-1] that means possible values of (a+x)%m are [0, m-1] because (a+x)%m keeps on incrementing till it completes the full modulo cycle.

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

      do u have any proof ?

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

        Let's say gcd(a, m) = g

        We know gcd(a, m) = gcd(g*p, g*q) where gcd(p, q)=1 and (0 <= p < q). So we have to choose such x those satisfy gcd(a+x, m) = gcd(g*p, g*q). So we all have to do is find the number of co-prime of q those are less than q. So we have to call phi(q).

        sorry for my bad english...

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

          Thanks for your explaination. I still don't understand the final step. I am only able to get phi(q+a/g)-phi(a/g) by the above steps instead of phi(q).

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

            gcd(a+x,m)=gcd(m,(a+x)%m)=gcd(g*q,g*p) note that (a+x)%m will always be less than m and can take up any value from 0 to m-1. So finding phi(q) will suffice.

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

              Still didn't get it.Can you please elaborate more?I have the same doubt as tycw.

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

                What we think about should be (a+x)%m instead of a+x. So the range of answer becomes [0,m).

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

                  Okay, but how its ensured that all the numbers we get will be >=a,in phi(m/gcd)?

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

      why

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

How to solve E?

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

    keep segtree on array where arr[i]=cost if you split at i, start by putting everything on the right and leaving the left empty, so arr[0]=a[0], arr[1]=a[0]+a[1]... then start by putting 1 on the left, then 1 and 2, then 1,2 and 3 and so on. when you put a new number on the left the cost for all splits with that number already on the left decrease by a[position[i]], the cost of all the splits without that number (the ones with i<position[i]) increase by a[position[i]]. each time get the minimum in range (0,n-2) (because you can't split at last element).

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

    Another segment tree solution that doesn't require range update/lazy propagation:

    Represent each segment by the triple $$$(suml, sumr, cost)$$$. Define the combination of two segments as follows: $$$A + B = (suml_A + suml_B, sumr_A + sumr_B, \min(cost_A + suml_B, sumr_A + cost_B))$$$ (this operation is not commutative, but it is associative)

    Start with $$$tree[p_i] := (0, a_i, 0)$$$. Iterate $$$i$$$ over $$$[1, n-1]$$$ by updating $$$tree[p_i] := (a_i, 0, 0)$$$, then grabbing the $$$cost$$$ value from the "sum" of the entire segment tree. The answer is the minimum $$$cost$$$ value retrieved.

    Explanation: Fix a split of the permutation to sets $$$L$$$ and $$$R$$$. $$$suml$$$ represents the sum of the costs of $$$L$$$ in that segment, likewise $$$sumr$$$ for $$$R$$$. Now consider how to combine the statistics for segments $$$A$$$ and $$$B$$$. Combining the sums is obvious, but what is $$$cost$$$? Consider there is a point $$$x$$$ within the segments where we want to move all points $$$i > x$$$ from $$$L$$$ and $$$i < x$$$ from $$$R$$$. If $$$x$$$ is in the left segment ($$$A$$$), the new cost is $$$cost_A + suml_B$$$, as we must move all members of $$$L$$$ in the right segment ($$$B$$$). If $$$x$$$ is in $$$B$$$, the new cost is $$$sumr_A + cost_B$$$ as we must move all members of $$$R$$$ in $$$A$$$. We thus pick the minimum of these two scenarios. The updates progressively move elements from $$$R$$$ to $$$L$$$ as the initial split. Be sure not to move the last element, or your answer would always be spuriously $$$0$$$.

    Sample: 69829539

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

Am I stupid? How do you solve D? I got to count numbers $$$b$$$ with $$$0 <= b < m$$$ with $$$gcd(m, b) = gcd(m, a)$$$ but made zero progress afterwards

Edit: As I look at my previous claim I realize that my proof in-contest is flawed. Does anyone know if the statement is actually correct? Looking at the solution given, my statement should be true but I am unable to prove it.

Edit: Just kidding, not flawed. $$$gcd(a, b) = gcd(b $$$%$$$ a, a)$$$ which easily applies to $$$gcd(m, a+x) = gcd((a+x)$$$%$$$m, m)$$$ since $$$a+x$$$ takes on m consecutive unique values, we know it takes on every integer $$$[0, m)$$$ exactly once.

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

    Let $$$d = gcd(m, a)$$$ and $$$m_1 = m / d$$$, $$$a_1 = a / d$$$, $$$b_1 = b / d$$$. Then $$$gcd(m_1, a_1) = gcd(m_1, b_1) = 1$$$.

    In other words, you have to count numbers $$$b_1$$$ with $$$0 \le b_1 < m_1$$$ which are coprime to $$$m_1$$$. This is actually an Euler function, $$$\varphi(m_1)$$$.

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

    Yes, but there is one more condition on b, that b >= a. It can be easily done by just altering the algorithm for calculating the Euler Totient Function.

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

      There must be some reduction to get this statement with b. At least unmodified totient function works: 69784007

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

    We can reduce the problem to couting the number of numbers relatively prime to m on interval [0..m/gcd(a, m)]. Let's say that m = m/gcd(a, m). Firstly you need to factorise m and store vector of unique prime factors. Then you can use the principle of inclusion and exclusion to calculate the number of such numbers that have common prime divisor with m.

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

    I've done it kinda differently compared to the Euler Totient guys here. Using the statement notations, we have a, m, and x. a = gcd*u and m = gcd*v, where (a, m) = gcd so (u, v) = 1 gcd must divide (a+x) so gcd must divide x therefore we have x = gcd*y

    Which brings us to an equivalent problem: find the count of y for which: (u+y) and v are coprime, where y is in range [0, v), aka their gcd is 1.

    For that, I used the principle of inclusion/exclusion because v had something like 12 factors maximum. And because I was in full blown panic mode and couldn't think of Euler.

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

      Can you explain your code how are you computing number of y's so that gcd(u+y,v)=1.??

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

        Do you know about the Inclusion and Exclusion Principle? I'll count the values of y for which the gcd will be different than 1: divisible with p1, p2, ... or pk, where p[1...k] are all prime factors of v. That's done with above mentioned principle: you basically consider all subsets of {p1, p2, ... pl} and you either add or remove their count from the result depending on the parity of its size. https://codeforces.com/contest/1295/submission/69761793 I'm hoping my code is actually correct, as in it doesn't fail after the hacking phase. It's really short once you remove the comments.

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

          Hey bro can you tell how is u + y == v (mod x), and what computation you are doing in your solve function after taking all the numbers from the set.

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

      Great minds think alike!

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

      Nice. But if the range of x is: 0 <= x < 2m Then Euler Phi does not work I guess. Like if a=8, m=12 and for 0<=x <m , The answer is 2 like Phi(3) but for 0 <=x <2m , answer is 4 i guess. Which is not Phi(3) but it is 2*Phi(3). Also if x was: 0 <=x <= 2m , Then the answer is 5. I don't know how to explain that. But if you see, for ==> gcd(a+x,m) = gcd((a+x)%m),m) (according to many comments) which says that no matter what is x's range, we only need to find the Phi(m/gcd(a,m)) which is incorrect for x's various range.

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

    How did you come up with gcd(m,a) = gcd(m, b). Couldn't understand this part.

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

      gcd(a+x,m) = gcd((a+x) mod m, m), so in fact you just need to check which remainders of m have the same gcd as a.

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

        we have to check no of coprime with m in range(1,m-1)?

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

          Not exactly, because you are looking for the numbers in range(1, m-1) which have the same gcd with m as a has (which is not necessarily 1).

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

    How do you make GCD (a, m) = GCD (b, m)

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

      Let X=GCD(a,m).

      So if GCD((a+x)/X,m/X) equals to 1, GCD(a,m) will equal to GCD(a+x,m).

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

I'll bite, how to solve F? :P

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

GG, thanks for all the awesome problems! It was my first time participating in such a coding contest and it did take me some time to get used to many things on Codeforces. As a first-timer, Codeforces is like a gold mine to novice programmers like me xD.

Can someone give me a few pointers on how to improve as I found some questions quite challenging and there are always some nuts who can solve them in like 10min :D

Cheers~

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

How to solve C? My idea was to use hashmap (Key: Value being Char: List of Index) for characters of string S. But got TLE

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

    my_submission

    dp[i][j] -> nearest index of alphabet(j) after index i
    

    and iterate through string t and solve problem greedily

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

    Store indexes for every letters 'a' to 'z' from String s. After storing, sort the indexes of individual letters. At first make a variable idx set to 0 before iterating String t. set ans to 0. While iterating on String t, you can check if current character happens from idx to afterwards in String s by just doing binary search on that character's stored indexes. if idx is not found in stored indexes, set idx to 0 again and now it must be found. just increment the ans when idx is not found.

    just in case when at least one letter in String t is not in String s, then the ans is -1.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it -19 Vote: I do not like it
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it
      • Not only problems but also exercises can be used;
      • Useful, even well-known ideas will be reused in order to introduce them to a wide range of participants;

      These are some characteristics which education rounds follow.

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

        Ok so indirectly u want to say that in educational rounds before solving any question we should Google it??nice

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

          Yes you can google and stay green.

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

            Ok Mr Red xD

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

              Yes you can do it.

              But are you sure that you can solve the problems even if you google it?

              So that's the reason why you are staying green.

              If you still want to stay green,you can google the problems,even if it violates the rules.

              xD

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

It might be a very weird thing to ask as an author, but how to solve F?

It seems that my model solution is a lot more complicated that the ones from the participants.

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

      Thank you! It's amazing how the combinatorial approach to the problem can make the solution a lot easier. Unfortunately, I didn't even think about that, and the probabilistic way lead me to maintaining and interpolating the probabilities as polynomials (which is way harder, obviously).

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

Hi, can anybody make a hack? I receive an error after Hack button..

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

Did you really think this B was appropriate?

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

I just found a cheat in this contest;

At "Hacks" page of this contest. I found ma_da_fa_ka and InsaneNerd hacked each other on problem B. Since it's very funny, I looked into their solution and only to discover they copied each other and the both get accepetd in their latest solotion!

By the way, ma_da_fa_ka's code even didn't have indentation.

By the way, ma_da_fa_ka used bad word as his handle. (lol)

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

    And one of the funniest thing is that ma_da_fa_ka even tried to hack himself,although that hack was unsuccessful. xD

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

    So why Codeforces can't stop them from cheating?

    I think that will be a big problem.

    Wish MikeMirzayanov can manage to stop them.

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

How do I know if D Euler(m / gcd(a,m) )

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

    Instincts....

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

    Let $$$d = gcd(a, m)$$$.
    Since $$$0≤ x < m$$$ and $$$1 <= a < m$$$, we easily conclude that $$$(a + x)$$$ mod $$$m$$$ can take values in the range $$$[0, m - 1]$$$ and we know that $$$gcd(a + x, m) = gcd(m, (a+x)\ mod \ m) = d$$$

    Let's look at the case when $$$d = 1$$$, let $$$b = (a + x)\:mod\:m$$$, our goal is to find all the values of b where $$$gcd(m, b) = 1$$$ which is by definition $$$\phi(m)$$$ given that we concluded earlier that b can take any value in the range $$$[0, m - 1]$$$.

    Now, let's consider the case where $$$d \neq 1$$$. Clearly, the values of b that we are looking for in the range $$$[0, m - 1]$$$ must be multiples of $$$d$$$, so let's enumerate all the $$$m / d$$$ multiples of $$$d$$$ in this range as follows: $$$ 1, 2, ..., (m / d)$$$. Let $$$i$$$ be the enumeration of the $$$i^{th}$$$ multiple, we want to count $$$i$$$ such that $$$gcd(i * d, m) = d$$$, but since $$$d \ | \ m \ and \ d \ | \ (i * d)$$$, we really want to count $$$i$$$ such that $$$gcd(i, m / d) = 1$$$, which turns out to be $$$\phi(m / d)$$$.

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

Problem is saying 998244353 decimal digits. What i was thinking number should be less than 998244353. Can anyone suggest what should i do to avoid such type of mistakes ???

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

Such a bug B!This round shoule be unr!

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

    Agree, I would have spent years trying to debug my solution if I did not decide that solving C first is a better idea...

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

how to solve B?

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

    You can create an array $$$cnt_0$$$ and $$$cnt_1$$$ in which $$$cnt_x[i]$$$ is the number of characters $$$x$$$ are from $$$0$$$ to $$$i$$$. Also, you can calculate $$$delta[i]$$$ which is $$$cnt_0[i] - cnt_1[i]$$$. Then, when the string is repeated again, the same pattern of $$$delta$$$ is going to occur but increased by a constant, because the number of $$$0$$$ and $$$1$$$ that you have from the previous string are accumulated. I'm going to concatenate $$$s$$$ two times to make the pattern visible.
    Let's analyze the following input
    $$$n = 6, x = 10, s = 010010$$$
    $$$cnt_0: 1, 1, 2, 3, 3, 4 | 5, 5, 6, 7, 7, 8$$$
    $$$cnt_1: 0, 1, 1, 1, 2, 2 | 2, 3, 3, 3, 4, 4$$$
    $$$delta: 1, 0, 1, 2, 1, 2 | 3, 2, 3, 4, 3, 4$$$
    Every time a string has finished, delta is going to change in a constant. Let's called that constant $$$d = delta[n] - delta[0]$$$. For each position $$$i$$$ between $$$0$$$ and $$$n - 1$$$, you know that you can reach all the numbers of the form $$$delta[i] + kd$$$, in which $$$k \geq 0$$$ because it is the number of times that the string is going to be repeated. So, for each $$$delta[i]$$$, $$$i$$$ between $$$0$$$ and $$$n - 1$$$, you have to check if it possible to obtain a non negative $$$k$$$ such that $$$x = delta[i] + kd$$$. The only corner cases are in which $$$d = 0$$$, then, if you have at least one solution, you are going to have infinite solutions of this form. Finally, check the case of the empty string if the solution is no infinity. The time complexity is $$$O(n)$$$.

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

      Thank you for the clear explanation.

      I have somewhat awkward question:

      Have you seen similar problem before? In other words, do you feel that your experience has helped you to solve it?

      I was trying really hard to solve it for 90 minutes, but get lost in own thought process. So I wonder if I need more practice or maybe this CP thing is simply not for me ;-).

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

    I don't like problems like today's B where you have to be so careful with corner cases. There isn't any fancy idea behind, just annoying implementation ._.

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

    take '0' as $$$1$$$ and '1' as $$$-1$$$ and calculate the prefix sum $$$pre$$$.

    then for each $$$pre_i + x\cdot pre_n = balance$$$_$$$value$$$, if there is a non-negative integer $$$x$$$ satisfying the formula, add 1 to the answer. if balance_value is zero then add another 1 to the answer.

    if $$$pre_n=0$$$ then if there exists an $$$pre_i=balance$$$_$$$value$$$, then answer is -1; else answer is 0.

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

      why add 1 when balance_value is zero?

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

        Because empty prefix can be a prefix too. So the balance of empty prefix is 0.

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

VERY VERY WEAK test cases for B :(

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

Author is fond of strings i guess.

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

D can also be solved with mobius function(Inc-Exc) 69790210. Let g = gcd(a,m). gcd(a+x,m) is g if and only if g|x. gcd(a+x,m) = gcd(g*c1 + g*y, g*c2) = g. gcd(c1 + y, c2) = 1. Use inc-exc now — neglect non-square free numbers for others if a divisor is prime product for even number of primes than subtract such numbers, for odd add them using the observation that if mu[n] = mu[d]*mu[n/d].

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

Anybody with a good hack for B?

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

How to solve C ?

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

    Let's store index of every letter (in vector, for example). Then, just simulate building of string with fast find of needed index — lower_bound is good for this purposes. 69790270

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

Problem "A" was similar to this problem. Link: www.hackerrank.com/contests/programming-contest-4-cse-ian-of-bd/challenges/number-with-sticks

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

I am not sure about my solution,can anybody hack it.

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

that was one of the worst contest in all of the codeforces rounds. the problems were really bad. i hope to see better contest in future.

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

    why is it really bad? is it because you didn't do well in this contest.

    what a good contest for you would look like?

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

      for starters, a good CF contest wouldn't have more people solving C than B

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

        so what? the problems in edu rounds are equal (there are no points for problems, ICPC style). so solving C more than B is just a matter of swap. so people should see the number of participants who solve the problem and move to that problem. and being stuck in a problem is no good skill. people need to learn to move on.

        and even if the problems were given points and people solve c more than b, it does not yield the entire contest bad.

        you guys just talk trash about the contest while you do not know the efforts made to prepare the rounds. It is a lot harder to estimate how the contest would go for the participants.

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

          That might've worked if they had managed to prepare B well enough to avoid errors in the testcases

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

    Bruh salty. Edus are getting better ever since they reduced it to 6 problems.

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

    BRs82 was one of the worst person in all of the codeforces users.The comments were really bad.i hope to see better user in future.

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

Can someone explain the idea "phi value of m/(gcd(a,m))" for problem D? I mean how we got it?

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

    This has already been explained in previous comments.

    Let $$$gcd(a, m) = g$$$
    We have $$$gcd(a, m) = gcd(a+x, m) = gcd((a+x) \ \% \ m, \ m)$$$
    Notice that as $$$x$$$ increases, $$$(a + x) \ \% \ m$$$ will end up taking all values in $$$[0, m)$$$
    So we only need to find the number of $$$k \in [0, m)$$$, such that $$$gcd(k, m) = g$$$

    Since $$$gcd(ca, cb) = c \iff gcd(a, b) = 1$$$, we can take any integer coprime to $$$m/g$$$ and multiply it by $$$g$$$ to find a suitable $$$k$$$.

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

will there be points for successful hacking during the hacking phase?

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

    The EMPTY STRING is also a valid prefix.

    It was ensured in the announcement.

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

    Educational CF Round and Div.3 Round have no points for successful hacking attempt.

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

69796073

Is it possible to see the hack case for my solution after preliminary result? I really have no idea of the counter example :(

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

I solved E without any range updation datastructure , just use map of values which have arrived and changes the current cost with coming elements and decrementing the cost if already added to the initial cost, it gives me wrong answer on testcase 10, can anybody look into it my submission https://codeforces.com/contest/1295/submission/69796456

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

Can anyone please tell me what is wrong with my code for problem B. https://codeforces.com/contest/1295/submission/69788305

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

    The EMPTY STRING is also a valid prefix.

    It was ensured in the announcement.

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

A was very similar to 101612A - Auxiliary Project

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

What is "Unexpected verdict"? Hack #613188

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

    It means that one of the problem makers' solution is incorrect. (The official solutions had a different answer to each other.)

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

Didn't know much about such a nice function (Euler Totient Function)

Thanx to problem D for increasing my knowledge.

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

I think so many TLE codes are "accepted" in Problem C.

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

    A very simple testcase in Problem C was hacking testcase for many solutions.

    1

    aaaa....a(length is 100000)

    aaaa....a(length is 100000)

    If I woke up early, I could do more hacks.

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

      Why can such codes pass all the test data? Is all the test data random?

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

        Yes, Testdata is too week. But it is no matter, because this is an "Educational Contest" which is for not only algorithm ranking but also hacks ranking.

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

      I think if you hacked at least one problem with this test case, it might be added to final test.

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

        True. So the codes get TLE finally anyway. but my hack score ...

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

Editorial please?

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

Am I the only 8ne who solved C with a precomputed DP

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

When will the system testing start?

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

It's pretty.

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

where's the rating Lebowski

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

For question B: Can anyone explain why the output of

1
3 0
011

is 2 ? Please help, my solution is hacked and I don't know why

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

No matter how hard I try, I could not understand the solutions given for problem D. It would be great if someone could explain me how to do in simple and detailed steps. I would be really grateful to them.

Thank you!

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

    Let X be gcd(a,m),so gcd(a/X,m/X)=1.

    If gcd(a+x,m)=X,then (a+x)%X equals to 0,x%X also equals to 0.

    So gcd((a+x)/X,m/X) equals to 1.

    Find all the x in eular algorithm.

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

when will editorial be published?

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

Waiting for the Editorials!!

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

Has the editorial for this contest been published yet? Or there won't be one?

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

    It would surely be published. Not sure about the release time.

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

expert in a one contest

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

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

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

problem A What's wrong in this?

include<bits/stdc++.h>

using namespace std; long long n; int main(){ int t; cin>>t; while(t--){ cin>>n; if(n%2==0){ for(int i=0; i<(n/2); i++) cout<<"1"; } else{ cout<<"7"; if(n!=3){ for(int i=0; i<((n-1)/2); i++) cout<<"1"; }

}

cout<<endl; }

}

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

    In your loop for(int i=0; i<((n-1)/2); i++), it should be i < (n — 3)/2 instead, as 7 takes 3 resources.

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

Why is this solution so slow? (Problem C):

http://codeforces.com/contest/1295/submission/70937323

As for me, the complexity of this one is O(T*|t|*log(|s|))