FCB1234's blog

By FCB1234, 3 weeks 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 FCB1234, Grzmot, isaf27 and Mateuszrze. Also thanks for:

KAN and _kun_ 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  
  • +552
  • Vote: I do not like it  

»
3 weeks ago, # |
  Vote: I like it +142 Vote: I do not like it

Clashes with El Clasico:(

»
3 weeks 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.

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

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

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

    FCB stands for something else. ;)

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

      I am curious. For what my nick stands?

      • »
        »
        »
        »
        3 weeks 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

»
3 weeks 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 :(

»
3 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

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

»
3 weeks 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 !!

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks 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.

»
3 weeks 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)?

»
3 weeks 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.

»
3 weeks 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 .

  • »
    »
    3 weeks 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!

»
3 weeks ago, # |
  Vote: I like it +87 Vote: I do not like it

What do the hoodies look like?

»
3 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

FCB1234, are you Indian?

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Good Luck on contest!

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

Is there any way to buy these hoodies ?

»
3 weeks 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I will try my best to prove myself! Fighting!

»
3 weeks 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.

»
3 weeks 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
  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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

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

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

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

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

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

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

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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.

  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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 :)

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

    but is it determined?

  • »
    »
    3 weeks 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 —

    • »
      »
      »
      3 weeks 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.
  • »
    »
    13 days 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?

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

      The onsite round will be used

»
3 weeks 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! _kun_ FCB1234

»
3 weeks 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. :)

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

    I'll hack you down!

    • »
      »
      »
      3 weeks 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. :)

»
3 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Score distribution?

»
3 weeks ago, # |
  Vote: I like it -22 Vote: I do not like it

Lol. Why is there an unusually large number of reds and nutellas participating in this round?

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

likle adn subvurncwe

»
3 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

which one is more important elclasico or contest? ;)

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

    football is for monkeys :D

»
3 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

FCB1234 I hope you will upload editorial shortly after contest.

»
3 weeks 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.

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Barca 5 — 1 Real :))

»
3 weeks ago, # |
  Vote: I like it +83 Vote: I do not like it

>those names in A

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I got pointless WA in D because I wrote some code inside a function rather than in main.

»
3 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

How to solve F?

  • »
    »
    3 weeks 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.

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

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

      • »
        »
        »
        »
        3 weeks 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).

        • »
          »
          »
          »
          »
          3 weeks 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?

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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).

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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.

  • »
    »
    3 weeks 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).

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve c ?

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

    Put 1 at all indices where a[i] != a[i+1] and also the last index if a[n] == 'a'

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks 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, Captain-America-123234's variant with regexes: 45058519

»
3 weeks 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?

  • »
    »
    3 weeks 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!

    • »
      »
      »
      3 weeks 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 :(

  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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"

          • »
            »
            »
            »
            »
            »
            3 weeks 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?

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

    Bruh me too xD

»
3 weeks 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)

  • »
    »
    3 weeks 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.

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

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

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

    Check for same subarrays in all permutations.

    eg : [123 456 78] [78 123 456] [456 123 78]

    answer is sum over f(subarray.length) where f(x) = x*(x+1)/2

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

      I came at this conclusion very quick but didn't know how to do this?

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

        There are a few ways to code this:

        1. Rolling hash (seriously overkill)
        2. Just iterate over the subarrays in a total M * N time
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          may be i'm a bit not confident in implementation. Thank You

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

    Sadly I didn't think it through, and almost coded a rolling hash solution :(

  • »
    »
    3 weeks 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;
    
  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

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

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

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

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

  • »
    »
    3 weeks 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

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

      Nice solution!Amazing!

    • »
      »
      »
      3 weeks 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.

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

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

  • »
    »
    3 weeks 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.

»
3 weeks 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.

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

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

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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]

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

    You can check iteratively. The same thing as hashing, but much easier. I almost coded the entire hash solution before i realized what i was doing ;_;

»
3 weeks 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)

»
3 weeks 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?

  • »
    »
    3 weeks 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]

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

How to solve F??

»
3 weeks 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.

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

What is the hack for B?

  • »
    »
    3 weeks 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...

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It says pending systests, but systests have already started?

»
3 weeks ago, # |
  Vote: I like it +205 Vote: I do not like it

As wise man said, please stop creating problems.

  • »
    »
    3 weeks 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 :( .

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

      What did you gain from it not reading??

      • »
        »
        »
        »
        3 weeks 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).

    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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.

    • »
      »
      »
      3 weeks 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.

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

    +1

  • »
    »
    3 weeks 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 :)

»
3 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

I hope strong cases for F.

Nice tasks :)

»
3 weeks 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, _kun_) or by 300iq? :)

»
3 weeks 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!

  • »
    »
    3 weeks 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.

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

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

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    3 weeks 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!

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

That 700 lines for G from tourist...

»
3 weeks 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

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks 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

»
3 weeks 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.

»
3 weeks 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:)

»
3 weeks 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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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 :)

        • »
          »
          »
          »
          »
          3 weeks 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"

      • »
        »
        »
        »
        3 weeks 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!>.

        • »
          »
          »
          »
          »
          3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

man why was I soooo sloooooow solving C

»
3 weeks ago, # |
  Vote: I like it +77 Vote: I do not like it

A notorious coincidence

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

    Very mysterious...

  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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.

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

how to get a random hoodie?

  • »
    »
    3 weeks 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.

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

      problem B, round 412?

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That person can betray you and make unsuccesful hack

»
3 weeks 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

  • »
    »
    3 weeks 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

»
3 weeks 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 !!!!!

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

    Revolution begins

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

      Last time it happened in the summer 2016 :D

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

        It happened. Congrats to mnbvmar.

      • »
        »
        »
        »
        3 weeks 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.

    • »
      »
      »
      3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +55 Vote: I do not like it
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Will you explain,How u did it ? This is not the expected correct code.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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)

    • »
      »
      »
      3 weeks 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.

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

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

»
3 weeks 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);).

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

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

    • »
      »
      »
      3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +53 Vote: I do not like it

Who (outside of top 50) gets hoodies?

»
3 weeks 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?

  • »
    »
    3 weeks 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.

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

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

      • »
        »
        »
        »
        3 weeks 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).

        • »
          »
          »
          »
          »
          3 weeks 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

          • »
            »
            »
            »
            »
            »
            2 weeks 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.

»
3 weeks 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

»
3 weeks 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.

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

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

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

http://codeforces.com/contest/1043/submission/45014931

why am I not getting AC when i clearly should??

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Messi got injured in this round.

»
3 weeks 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

  • »
    »
    2 weeks 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.

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

Sadly,this contest changed the world rankings !

»
3 weeks 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?

  • »
    »
    3 weeks 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.

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

      Consider using 100000 maps. I passed in 600ms.

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

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

    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

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

»
3 weeks 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)

»
3 weeks ago, # |
  Vote: I like it +68 Vote: I do not like it

when will random winners announce ??

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Are there any contests available this week?

»
3 weeks ago, # |
  Vote: I like it -41 Vote: I do not like it

are there any contests available this week?

NOIP is coming..

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

Where does randomness come into picture when solving F? I don't understand. I have seen plenty of people use random number generators when solving problems that involve calculating prime factorization but I never understood it. Can anyone please explain or point to some source. Thanks.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am trying to solve E with the following solution (Python 3) — https://codeforces.com/contest/1043/submission/45127707. But, I am getting a TLE on test-5. Do I need to rewrite it in C++ or is there something that can be done in this solution? The solution is in O(N x logN)

»
12 days ago, # |
  Vote: I like it +11 Vote: I do not like it

So who won the random hoodies?