When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Anadi's blog

By Anadi, 5 years ago, In English

I would like to invite you to participate in the rated Codeforces Round 519 by Botan Investments. Date and time of the round: Oct/28/2018 18:35 (Moscow time).

This is a combined round having 7 problems and lasting 2 hours, and it will be rated.

Tasks for you were prepared by Anadi, Grzmot, isaf27 and Rzepa. Also thanks for:

KAN and cdkrot for help in preparing the problems; pavel.savchenkov, Nerevar, map, GR1n, rutsh, AlexFetisov and winger for testing the round; MikeMirzayanov for Codeforces and Polygon platforms.

The round is supported by Botan Investments.

Prizes! Top 50 participants and 20 random participants with rank from 51 to 500 will receive personalized hoodie with CF handle.

Scoring distribution will be announced later. I wish you a high rating and looking forward to see you at the competition!

UPD: I'll be on the community Discord server shortly after the contest to discuss the problems.

UPD: Scoring: 500 1000 1500 2000 2250 2750 3500

UPD: Editorial

The round is over, congratulations to the winners!

  1. scott_wu
  2. mnbvmar
  3. HIR180
  4. ksun48
  5. Benq
  6. geniucos
  7. Alex_2oo8
  8. Petr
  9. Um_nik
  10. V--o_o--V
  • Vote: I like it
  • +544
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +142 Vote: I do not like it

Clashes with El Clasico:(

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

    Why do all residents of Kazakhstan like La Liga?

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

    El Clasico clashes with CF #519, not other way around :(

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

    Leo messi is injured, so he has chance to get a hoodie :))

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

    El clasico has started

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

Wow, top 500 will have the opportunity to receive personalized hoodie with CF handle. Hope to receive it. Good luck.

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

Mr Anadi what will you do during contest? watching your favorite team match or answer participants questions ???!

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

    FCB stands for something else. ;)

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

      I am curious. For what my nick stands?

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

        We have just talked about it yesterday, don't you remember? I won't announce it publicly cuz I'm a well-behaved person, but others can still guess :p

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

"Prizes! Top 50 participants and 20 random participants with rank from 51 to 500 will receive personalized hoodie with CF handle." -- That's awesome, I wish to get under 500.

Ah! But i still struggle with Div 2 C :(

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

Wish a hoodie be with you (and me) :D

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

why can't I register for the contest? it says I must have a rating between 9 and 9,999
UPD: it's fixed now !!

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

I'm glad to invite you to take part in Codeforces Round 519. Actually it will be two separate rounds "Codeforces Round #519 (Div. 1 Only)" and "Codeforces Round #519 (Div. 2 Only)". The division problemsets will share many problems, but not all of them will be the same. So, Div. 1 users should register on "Codeforces Round #519 (Div. 1 Only)" while Div. 2 users should register on "Codeforces Round #519 (Div. 2 Only)".

This is what is written in the invitation mail I received.

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

    Email is wrong a bit, this is going to be a combined round.

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

Awesome idea for giving hoodie to random guys, chance for non-red guys get a hoodie.

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

Could we get a picture of what the hoodies look like (for extra motivation)?

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

I like these random gifts, as usually all of the prizes only go to the same top users.

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

unfortunately , The contest will be at the same time as the Clasico match .

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

    If a red said this would it still be -22 contribution dont be rankist!

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

What do the hoodies look like?

»
5 years ago, # |
  Vote: I like it -28 Vote: I do not like it

Anadi, are you Indian?

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

It's a great pity that I cannot join in the match because I have to get up early tmorrow.

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

Look at my registration date. Do you see it too?

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

Good Luck on contest!

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

Is there any way to buy these hoodies ?

»
5 years ago, # |
  Vote: I like it -46 Vote: I do not like it

I don't understand why make it today and in same time with big football game that many people want to watch ?

It is not a round with onsite contest in same time, it is a normal round that can be delayed or shifted one day, there are many people here includes me that want to watch the game and take part in the contest why we can't do both ?

I think it is not late to delay it to tomorrow or just today after the game

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

try a try, ac is ok. Fighting!

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

I have never been so confused. Can't decide whether to give contest or watch El Classico.

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

The random winners will be determined with these two scripts:

Where seed is the number of points of the winner of the next contest, length is 450 (500 - 50) and nwinners is 20.

randgen.cpp
get_ranklist.py
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    What would happen if some concestants share the place and it would be choosen by generator?

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

      they are tied by the time of the last accepted as i know

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

        This does not make sense in cf :) Only in acm :)

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

          i remember this was used previous times when there were random prizes

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

            Then I have no chance :) One person submitted before, one after :D

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

              If I understood it correctly, you do have chance. I think each person is untied by the time of the last submission, so every one gets a different ranking.

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

    Why was seed not taken as max points by winner in this contest? Any reason?

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

      Probably more for historical traditions. Maybe it won't be true for the new random's :)

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

    but is it determined?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it
    1. Is it normal, that randgen.cpp can give number less than 20? For example, with seed 1234, it give 17.

    2. There is invalid syntax in get_ranklist.py in line 59. My python don't now —

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      1. rangen.cpp generates numbers from 1-450, and in get_ranklist.py 50 is added
      2. Replace all — s to — signs. It's a formatting error by copying from somewhere.
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    There will be 3 parallel contests, which's score will be the seed?

»
5 years ago, # |
Rev. 3   Vote: I like it -83 Vote: I do not like it

Please shift the round by 1.5 hrs. El classico comes only twice every year. Please I beg you! cdkrot Anadi

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

Expect problem statements to be short in size. Wishing everyone high ratings. :)

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

    I'll hack you down!

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

      I will be more than happy if you hack me down, at least I will have a chance to recorrect rather then failing on sys test. :)

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

        But what if he performs the hack at 1:59 :)

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

          Even if he did not, it would not pass sys test. No harm in him hacking my code :D

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

          glad to meet ya at the dark side

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

First time participating in a contest. Hope to solve atleast one

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

Score distribution?

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

which one is more important elclasico or contest? ;)

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

    football is for monkeys :D

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

Lol, dotorya_.

dotorya is the last person you should've done this with though.

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

To those football fans competing in this round, I am not saying that you are making a wrong decision, but unfortunately it seems like you have just missed an epic El Clasico match :'(

But well, I am probably missing my chance for hoodie as well, so yeah.

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

Barca 5 — 1 Real :))

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

>those names in A

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

How to solve F?

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

    it can be observed if the answer exists, then it's no more than 7. For each possible answer, check if it's valid by Mobius inversion.

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

      Why is the answer guaranteed to be no more than 7?

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

        Actually, it should be no more than 6, since 2 * 3 * 5 * 7 * 11 * 13 * 17 > 300000, and if the gcd = 1 can be reached, one should at least be able to remove at least one prime divisor for each move(i.e, add another element).

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

          That makes sense. Thank you!

          I have one more question, you said, "For each possible answer, check if it's valid by Mobius inversion." There are N^6 possible answers so how do we check them?

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

            Say if you want to check if it's possible to choose a subset of size k such that their gcd equals to 1. Let f(x) denote the number of possible choices such that the gcd of the subset equals to x, and g(x) denote the number of possible choices such that the gcd of the subset is a divisor of x, so that one can apply Mobius inversion on it. The time complexity is O(6 × 300000). All precomputations can be done in linear time.

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

              Could you please provide the explicit formulas? What I've extracted from your code is that g(x) stands for the number of choices such that gcd is divisible by x (but is not a divisor of x).

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

                Let f(x) denote the number of possible choices such that the gcd of the subset equals to x, and g(x) denote the number of possible choices such that the gcd of the subset is a divisor of x, then Mobius inversion states that , and the answer lies in f(1). So you have to compute to g(x), which only requires one to for each ai, add all its divisors by one.

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

          Actually it is 7. Take 2 * 3 * 5 * 7 * 11 * 13 * 17 and delete each number once. You will have 7 numbers and each must be choosen.

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

          Actually, the answer can be 7, since 3 * 5 * 7 * 11 * 13 * 17 < 300 000.

          Note that you have to also count the initial integer. 1 (initial) + 6 (removing divisors) = 7.

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

    I built a graph where each vertex is a product of distinct primes and there's an edge from a product to a subset-product whenever there is an input number coprime to the subset-product. How many input numbers are there coprime to x? That can be computed using inclusion-exclusion (you need to compute how many are divisible by each number first).

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

    first the do the basic checks and also remove duplicate primes in each number. For each value in 1 to 300000 count number of numbers which have gcd!=1 with that value(lets call gg[val])(using mobius function this is easy). Now we can construct graph with edges between two numbers(x and y) if x divides y/x and gg[x]!=n.

    Answer is shortest distance to a vertex from 1 in this graph +1.

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

    Use dpx — amount of numbers to get 1 if you took already some numbers with gcd = x.

    To calculate dpx, we need to check for each divisor dj of x: is there a number ai such that gcd(x, ai) = dj. To do this, we calculate another DP dqx, a (a is divisor of x)— amount of ai in the array such that gcd(x, ai) = a. Calculation of this dp looks like this (suppose wx is amount of numbers in ai which have x as a divisor):

    for i in rev(divisors[x]): # divisors[x] are in ascending order
      dq[x, i] = w[i]
      for j in divisors[i]:
        if i != j:
          dq[x, j] -= dq[x, i]
    

    It's easy to see that recalculation of all the dq's take no more than (faster in practice)

    Of course, we will keep only one dimension of dpx, a for current x to fit into memory limit.

    And, in the end, we solve the original dpx in the following way: dpx = min(dpy) + 1, where exists ai such that gcd(x, ai) = y.

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

how to solve c ?

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

    Have a variable cur = array[0]. Loop from 1 to n-1. if(cur == a and array[k] = b and array[k+1] == a), then you should swap at k and set cur to b. If cur == b and array[k] == a and array[k+1] == b, then you should swap at k and set cur to a. If you finish and cur == b, then you should swap at n-1.

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

    You can always rearrange the string to make every 'a' stands before all 'b's.

    To do this, we will traverse through the string and find substrings (consisting of consecutive characters) that all characters of it are 'a'. Let's denote the substring S[L, R].

    It's easy to say we will reverse prefix L - 1 (if it exists) and prefix R.

    Total complexity is O(N) with two-pointers. Naive solution in O(N2) is still acceptable with the given constraints.

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

      There is also DP solution: for every prefix of length i store lexicographically minimal and maximal string obtainable by doing first i rotations.

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

    With regexes. To substitute all a+ or b+ (but not b+ (longest) at the ending of the string) by '0' * length_of_a_match + '1' — Perl code: 45056981. Or, Algo_Rhythm's variant with regexes: 45058519

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

Am I the only one who didn't read The string s consists only of characters 'a' and 'b'. in problem C, and solved it for general strings?

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

    I've noticed it just now by reading this comment. I was blown away when I saw so many people solved C so fast. Damn!

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

      I was just astonished by so many submissions, until I went into hacking room and saw a 3 lines code :(

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

    I did the same :( Btw, how can it be solved for general strings?

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

      Our operations are equivalent to appending each character in order to either the beginning or end of the string. In the lexicographically smallest string, we want to put all a's into the beginning of the string. This means that after the first 'a', we put everything but a's into the end. Before the first 'a', we want to put nothing but b's to the beginning of the string, and so on.

      So Greedy still works, you just check if the current letter is smaller than or equal to all previous letters. If it is, add it to the beginning, otherwise add it to the end.

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

        Could you describe more in terms of reverting or not reverting a prefix. For example for string bazab how would you iterate over this string and make greedy decisions?

        If we iterate from last to first char in the string, once we find a we want to reverse the prefix baza and it also means that we want to maximize prefix baz. And to maximize prefix baz we want to reverse it and minimize prefix ba, so we want to reverse ba too.

        Would it work if we store char[] maxOnPrefix and char[] minOnPrefix to make decisions greedy?

        During contest I solved this problem for generic string with dp.

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

          Our operations are equivalent to appending each character in order to either the beginning or end of the string.

          Consider "bazab", iterate over each character.

          "b"

          append a in begining "ab"

          append z in end "abz"

          append a in begining "aabz"

          append b in end "aabzb"

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

            Ok, but how to produce the answer out of this? How to know what prefixes we want to reverse?

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

    Bruh me too xD

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

How to do E? I don't see how you can do it faster than O(n^2)

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

    You may compare the difference of x[i] and y[i], say d[i] = y[i] - x[i] for every competitor For two competitors i and j, if d[i] <  = d[j] then i should solve the second one.

    Binary search on how many competitors have higher d[] then himself and the answer can be calculated using prefix sum.

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

      don't forget to subtract scores of m pairs after that.

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

Does somebody know pretest 3 for C or pretest 7 for D?

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

Why everyone solved D....So,how to solve it?

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

    Split the first permutation into largest substrings which appear in all other m - 1 permutations:

    1|2 3|4
    2 3|4|1
    4|1|2 3
    1|2 3|4

    If the length of the i'th substring is k[i], then the answer is:

    long long ans = 0;
    for (int i= 0; i < numberOfSubstrings; i++)
      ans += k[i] * (k[i] + 1) / 2;
    
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Just finished my code 2 minutes after the contest. I used rolling hash and binary search. For each number i from 1 to n,find the longest subset obtainable starting with the value i. Complexity O(NMlogN). CMIIW.

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

      I used rolling hash and binary search.

      That sounds too complicated :)
      We just need to test 2 consecutive digits in a permutation p[i] and p[i + 1] in order to test whether we can extend the current segment.

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

        won't this actually take O(N^2.M) tho ?

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

          No. We are touching each element of array at most 2 times.

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

    My personal ideas: The numbers from 1 to N can be seen as a directed graph, and I'll count the appearance of the pair (i, j), with i and j are the values of 2 consecutive elements on one permutation.

    If any pair appears exactly m times, then there will be an edge starting from u to v.

    With this given, it's certain that the graph will be a DAG, and there is no vertex having more than one edges pointing at it.

    So we can do a simple DFS from all sources to find the answer. With each source, if the total number of traversable vertices from it is x, add x * (x + 1) / 2 to the answer.

    UPD: I didn't take the TL seriously and my solution got TLE. Damn!

    Total complexity is O(NM * log(NM) + N).

    UPD2: Accepted solution (904ms): 45022094

    UPD3: Improved solution (171ms) from suggestion of mouse_wireless — complexity reduced to O(NM): 45031805

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

      Nice solution!Amazing!

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

      You can build the DAG from the first permutation. On each of the next ones, if you come across an edge that doesn't exist in the initial DAG, just delete it. This can be done in O(1), since each node can have at most one incoming and one outgoing edge.

      In the end, count the connected components in the resulting DAG and for each component add x * (x + 1) / 2 to the result (where x is the size of the component).

      By doing this, you eliminate the log factor.

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

        Right, I overkilled the solution. Good observation, man :D

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

    Oh well, I guess my solution was kinda different...

    Create the array ans[] where ans[x] is the amount of ways which start with number x in all permutations. Also, make the array pos[][] where pos[x][k] is the index where number k appears in permutation x. In particular, for num[m][n] (where num[x][y] is the yth number in permutation x), ans[num[m][n]] = 1. Now for any i with n-1 >= i >= 1 (a for loop where i decreases from n-1 to 1), take next = num[m][i+1]. Then, if for some j (1 <= j < m) num[j][pos[j][num[m][i]]+1] != next, we will have ans[num[m][i]] = 1. Otherwise, ans[num[m][i]] = ans[next]+1. Indeed, we know the value of ans[next], since we loop through i in decreasing order.

    Therefore, the answer for the problem is the sum of ans[x] for all x with 1 <= x <= n.

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

How to solve E? My idea was to do some sort of complementary counting but not sure how to get the sum for every team for person i in a fast way. Maybe there was some other observation?

Also how did everyone solve D. I used hashing+binary search, and I thought it was weird so maybe someone has a better solution.

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

    min(xi + yj, xj + yi) = xi + yj iff xi - yi ≤ xj - yj.

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

    For E, sort by x-y values since if x+b < y+a, then x-y < a-b. Then use prefix sums to calulate the sum.

    For D, I used hashing too, hope it doesn't give TLE in systests.

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

    min(x[i] + y[j], x[j] + y[i]) = min(y[j] — x[j], y[i] — x[i]) + x[i] + x[j]

    a[i] = y[i] — x[i] a[j] = y[j] — x[j]

    min(x[i] + y[j], x[j] + y[i]) = min(a[i], a[j]) + x[i] + x[j]

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

Can someone point out why my code for D is getting TLE for testcase 9 ? I guess it's O(mn) which shouldn't give TLE. I maybe wrong though.

The main idea is simple: Consider a directed graph with n vertices, with an edge from i to j iff the numbers i, j are adjacent in all m permution. Note that for any vertex, ,and which vertex (if any) v is connected to can be checked in O(m), so for all vertex doing this takes O(mn). Now the answer is where ci ranges over the sum of connected components.

Code for D

Could've implemented E easily had I not spend more than one hour implementing+debugging this :/ (got the idea for E within a few minutes)

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

Is E solved using the fact that min(a+b) = (a+b-abs(a-b))/2?

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

    min(x[i] + y[j], x[j] + y[i]) = min(y[j] — x[j], y[i] — x[i]) + x[i] + x[j]

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

    I rather used the fact that xi + yj < xj + yi is equivalent to xi - yi < xj - yj -- and then you can just use variables zi = xi - yi.

»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

How to solve F??

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

The problems were nice and interesting. But maybe the set together was easy.

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

What is the hack for B?

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

    My solution was a brute-force check if constructing a valid x is possible for a given k. Got hacked because I initialised x to -1 each time, but x[i] can take value -1 sometimes...

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

      Isn't a[i]-a[i-1]>=0?
      The second line of the output should contain l integers — possible lengths of the lost array in increasing order.

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

        That's the output. a[i] is the input array — that need not be in any particular order. Look even at the third sample (1 5 3)

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

It says pending systests, but systests have already started?

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

As wise man said, please stop creating problems.

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

    This round was much easier than usual cf rounds, A, B, C, D were pure ad-hocs, and E too was easy. I didn't even read E because it was E :( .

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

      What did you gain from it not reading??

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

        I prefered hacking other's solutions because I didn't thought E will be so easy, only to realise it later that it was simple ad-hoc,(binary search).

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

      I directly jumped to E after solving C. This was good chance for me to solve 4 question first time if I wasn't that over-confident.

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

    This time I can agree actually

    Or maybe just another notorious coincidence?

    problem F is from polish contest, author is polish

    https://szkopul.edu.pl/problemset/problem/4ftrK3Aqy2bpLk32N7wmjdZR/site/?key=statement

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

      My vote is on notorious coincidence (read: the author knew this problem). It's not the same problem though, N is higher and maxA is lower. Modifying a problem so it has a different solution is fine.

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

      Sorry, I didn't know this problem. I don't know all problems from POI.

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

    +1

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

    Thumbs up for the problem D.

    This is the first time it was interesting for me to read the story in a problem. I have never experienced that feeling while reading problem statement. The only artificial smell is that we're asked to find the number of different ways to eliminate ambiguities. At first I thought that the problem would ask us about deciphering who is trying to fool us (from the neighbours) and trying to lead the investigation astray :)

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

I hope strong cases for F.

Nice tasks :)

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

Was the last problem created by the authors, by coordinators (KAN, cdkrot) or by 300iq? :)

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

https://codeforces.com/contest/1043/submission/45019500 Any idea why this got a TLE? It's o(nmlogn) if I'm not mistaken. Could someone check it and let me know? Thanks!

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

    I think long long for every variable is causing TLE. Try to avoid putting long long everywhere.

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

    Use vector instead of map. I also got TLE for that.

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

How much cases do you have for model solution of G?

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

    Judging from the solution, it seems there are about 7 ~ 9 cases. Great!

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

That 700 lines for G from tourist...

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

why wrong answer in test case 2 is considered as a penalty in problem B. Link to the solution in which wrong answer in pretest 2 is considered penalty :

Your text to link here...

Please take a look into it

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

    Because only a fail on test case 1 isn't considered a penalty, and 2 ≠ 1.

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

    Wrong answer (or TLE, or MLE, or RTE, or...) on anything greater than test 1 counts as a penalty — even if that case is a provided sample. Only test 1 is excluded.

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Why this code for E gives runtime error? https://codeforces.com/contest/1043/submission/45014978

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

When easy problems are attached with unnecessarily long question sentences, it is only an English reading comprehension contest for those who are not English speakers.

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

Great contest , nice questions, nice tests, and I actually understood questions with reading only one time:)

»
5 years ago, # |
  Vote: I like it -70 Vote: I do not like it

Contest featuring most advanced algorithms to date:

(A) Binary Search (B) for loop (C) for loop (D) Binary Search (E) Binary Search

"Balanced contest"

I actually liked the adhoc nature of the contest though

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

    It seems you use binary search where it is not necessary =) I have 0 BS's in solutions of this contest.

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

      Thank you for your insight. I have updated the topics.

      Updated list:

      (A) loop (B) loop (C) loop (D) loop (E) loop

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

        According to your classification, 95% of the problems will have "for loops" topic :)

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

          Some REAL quotes:

          "95% of the problems ARE 'for loops' topic, it's just people came up with this pesky term 'algorithm' to describe basic operations"

          "I agree with Iightcode, he is genius"

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

        It would be ok to see such comment from somebody, who solved all these problems in about a hour. From you it seems like one more comment of type <I want contribution!>.

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

          <I want contribution!>.

          What you think about anything I post is your own business. But why is it not ok to post what I want to say? I don't meet a rating threshold?

          And by the way, if you really are going to set such requirements for others at least meet them yourselves.

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

            You can post anything that you want to say. As I also can. As we both do. And no, I try not to judge people by their rating, rather by their words (as in your case too).

            I set such requirements because you said (implicitly) that problems were easy and (explicitly) that contest was badly balanced. Maybe it was really easier than average CF round, but it should be said by somebody, who really feels that problems were easy (for 2 hours, of course). I didn't say it and you did. That's why you should meet such requirements and I shouldn't.

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

              Sorry if I seemed like I was insulting the round. I actually like the round because it focused more on thinking than algorithm.

              I never meant to say round was easy, just that problems could be solved without advanced algorithms and more thinking.

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

man why was I soooo sloooooow solving C

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

A notorious coincidence

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

    Very mysterious...

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

    Yes, they are the same person, have you ever spotted ksun48 and mnbvmar in the same location?

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

      I think I might've. But there was snoweverywhere so I could not tell for sure.

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

      My point wasn't that they are equal. The point is, that two nutellas got AC 2 ms under the TL.

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

        And CF top 1 didn't pass it at all.

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

          that's the difference between C++11 anh C++14 :))

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

Can someone help what is wrong in this? http://codeforces.com/contest/1043/submission/44997704

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

how to get a random hoodie?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it
    1. In the next contest become top-1 and make sure that nobody's gonna score more than you.

    2. Run the script locally with seeds (your score), (your score - 50), (your score - 100) etc until you find a seed where you win a random hoodie.

    3. Make a corresponding number of unsuccessful hacking attempts.

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

      problem B, round 412?

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

      How about giving up first place if second place person's score can get you hoodie?

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

        That person can betray you and make unsuccesful hack

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

I misread problem C and did not know that there are just two letters. Does my code really solve it for general ? my code

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

    Uhh, same here, probably I will never realize it if I never see your post. Holy shit man, no wonder so many people already solved it the time I did. mine

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

i think this contest rating changes can change top rated user in CF. i think mnbvmar will be top rated user after rating changes !!!!!

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

    Revolution begins

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

      Last time it happened in the summer 2016 :D

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

        It happened. Congrats to mnbvmar.

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

        You are mistaken. Last time it happened in the spring of current year after CF #470 round.

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

      Or this was simply div2 contest + unsovlable task. Which for best guys in div1 means typing speed contest + every little mistake means -200 rating.

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

    Does it work on test 10 15 42 44 46 (all the even starting from 42)? The answer is 2 (15 and almost any other number (but not 10 and 42) so pairs of neighbours don't work.

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

      Well, probability for that case is 1/n per random try (where n is less then 300000 becasue it's reduced and there's 50000 iterations so it's probably not hackable)

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

      Just tried it and it prints 2. Thing is I also remove multiples of numbers that are among the given so this leaves me with only 13871 numbers.

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

    So, 45023600 gives 4 while answer is 2 (gcd(15, 28) = 1)

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

Why is time limit for D so tight? Some NlogN solutions have passed and some didn't. I don't know if it wasn't the expected complexity.
Update: My two solutions for D: TLE and Accepted. Both are O(NMlogN), just a one line difference (cin.tie(0);).

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

    there's O(mn) solution (mine passed in 200ms)

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

      Yes, I know. Maybe I ignored it thinking O(NMlogN) was enough to pass. These kind of testcases should be added in pretests because they are not even hackable.

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

Who (outside of top 50) gets hoodies?

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

My solution for F (45014411) failed in contest with tle 35:(. But it later passed all 4 times I submitted it in practice just after adding "srand(chrono::steady_clock::now().time_since_epoch().count());". 45021752. It is basically removing duplicates and then removing multiples of numbers and then kind of bruteforce with pruning. Can this solution be hacked and testcases are weak or can it be proved that it will work with high probability?

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

    It seems like you are not using Mersenne Twister in your first solution, relying only on default random function without setting seed (which makes it totally predictable).

    So, for any fixed n your shuffle is just a fixed permutation, which could be inverted. Then hacker could just take a test where bruteforce is working too slow and apply inverted permutation to it. In that case after random_shuffle you will get that bad test.

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

      Thats ok. But even with true randomness should such solution work?

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

        Well, seems like not.

        Suppose we have a number 299 999 and every number from 150 002 to 300 000 which is divisible by 2 — n = 75001. The answer is clearly 2 (gcd(299 999, 300 000) = 1), but you can get it only with 299 999. Note that no numbers would be deleted as duplicates or multiples.

        Let k be the position of 299 999 in shuffled array. You will need to do at least k*(k-1)/2 operations to get there (because your map stores every number you processed so far if ans >= 3, and until position k ans = 12), and if k is big enough, this number is too big.

        I runned your code on test above locally, and it took several minutes to finish (depending on position of 299 999 in shuffled array).

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

          Thank you! It makes me feel better that my solution didn't pass during the contest:D

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

            There is another trick which allows you to reduce the number of candidates even more: You don't need to keep two numbers which have the same set of prime divisors. So if you have 2*2*3 and 2*3*3 keeping just one number is enough. This will reduce the number of candidates to 14548 in the provided test case.

            I used this during contest and my solution passed in 280ms. See 45018592 for details.

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

I think I would have TLE on my own problem D solution with test:

100000 10

1 2 ... 100000

1 2 ... 100000

...

1 2 ... 100000

100000 99999 ... 1

»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

This is not to blame the judges, but kind of disappointed that this submission 45015775 of mine for problem E failed the time limits. I did not think the I/O would be so slow for the problem. This would probably pass within 2.1s or less I guess. Please consider setting a little more kind time limit for problems where solutions with worse complexity has no chance of passing the test.

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

    just add 2 lines in your template and forget about slow IO

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

    No one to blame but yourself. You used fast IO in D because you were afraid of 10^6. You didn't use fast IO in E while it was almost the same input size, 12 * 10^5 but with larger numbers so input/output is even larger.

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

    I also think problem E had too much I/O for the time limit. I usually like to use python to solve problems, and with some trickery it is mostly possible to solve any problem on cf with python (using pypy). However this problem had so much I/O that I was not able to do the I/O in under 2 s. Had to resort to C++ to get my solution to pass.

    I really think the constraints should be made such that not only C++ is able to pass. Currently this problem was mostly testing how quick I could get the I/O, which is not what makes these competitions fun.

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

      A sample solution I made in PyPy 2, 45036971, which might interest you.

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

Messi got injured in this round.

»
5 years ago, # |
  Vote: I like it -18 Vote: I do not like it

I think problem setters need to re-consider limit for python. I have one implementation code of problem D, correct algorithm. However, I got different verdicts from different compilers: — http://codeforces.com/contest/1043/submission/45023038http://codeforces.com/contest/1043/submission/45021411

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

    If you're using Python for anything past Div 2 B, you need to acknowledge the possibility that you can get TLE with the optimal solution. Python is too slow for most problems. Use C++ or Java.

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

Sadly,this contest changed the world rankings !

»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

What's with test case 36 on D. I see tourist got TLE on it, and many of my friends also did. Why did this happen?

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

    Because a lot of people solved it using directed graph. To construct it you need a map of pairs of integers, which is apparently slow. I managed to AC it, but with few pragmas (even then with 998ms) , my submission.

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

      Consider using 100000 maps. I passed in 600ms.

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

        just realised you dont need a graph at all...

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

      I just want to point put that you don't need maps to construct the graph. I'm actually surprised so many people went this path and submitted a sub-optimal solution (by a factor of logN). I guess it was more convenient and nobody thought it would TL.

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

    45024667 vs 45024739,the only different is the space after * author: tourist and the c++ version

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

      Whitespace is ignored by compiler, so technically the only difference is c++ version, which is surprising that just because tourist used different C++ version he drops 100 places.

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

I want to specially thank the problemsetter that came up with problem F. One of the most beautiful problems I've seen lately.

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

tourist getting TL 45001078 on D during contest with C++11, but AC 45024674 post-contest with the same code submitted with C++14. feelsbadman

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

    Still, inserting 1M elements into a map with TL=1s is never a good idea.

»
5 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Polish writers need to "polish" their problem setting skills!!

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

Good contest, it’s a pity that I didn’t have time to write (it coincided with conducting XXVI team championship of pupils of St. Petersburg in programming)

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

when will random winners announce ??

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

Those who got hoodies, share the picture of it. I really want to see how it looks.

»
5 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Are there any contests available this week?

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

are there any contests available this week?

NOIP is coming..

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

So who won the random hoodies?

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

I understand you are not supposed to look a gift horse in the mouth. But does the hoodie really need a gigantic Che Guevara picture? What does it have to do with Botan Investments, Codeforces or programming in general?