Educational Codeforces Round 44 [Rated for Div. 2]
By awoo, history, 7 years ago, translation, In English

Hello Codeforces!

On May/21/2018 17:45 (Moscow time) Educational Codeforces Round 44 will start.

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

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov and me.

Good luck to all participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Benq 6 143
2 crhkr 6 202
3 mjhun 6 210
4 nhho 6 210
5 krijgertje 6 223

Congratulations to the best hackers:

Rank Competitor Hack Count
1 step_by_step 248:-25
2 greencis 31:-6
3 zero-light-some 15
4 Necrozma 12
5 Codefocres 11:-1
703 successful hacks and 490 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A dotorya 0:01
B dotorya 0:03
C dotorya 0:10
D Benq 0:21
E ThePilgrim 0:07
F Deemo 0:49
G Marco_L_T 0:44

UPD: Editorial is uploaded

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

Comments Comments (222)
| Write comment?
»
7 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Finally, educational round, I miss you!

→ Reply
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I love this round. As, educational, it teach me a lot.

→ Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

What happened to BledDest? I have not see him in any educational contest for a while.

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

    He just got a bit busy with his exams at university. Might be back soon when they are over.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is an educational round? How is it different from a normal one?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +47 Vote: I do not like it

    It is meant for we to try multiple types of problems, even if they might not be very original. Each problem has not a specific score, but rather is just the solving time that makes your score. This means that, for example, solving A+B+D and solving A+B+C within the same exact time will give the same score, even if D might be more difficult than C. Finally, hacking is not enabled during the contest, but a long (12-24 hours) hacking phase takes place after the contest. After that, system tests are run, as for normal contests.

    → Reply
»
7 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Please, choose more comfortable As, Bs and Cs in future rounds, so that they're not just silly implementation problems :)

→ Reply
»
7 years ago, # |
  Vote: I like it -25 Vote: I do not like it

The third lucky number,

It's palindrome number,

Double the sum of it's digits equal to any digit of it square,

The number which product of it's digits equal to any digit of it square.

→ Reply
»
7 years ago, # |
  Vote: I like it -73 Vote: I do not like it

What about div.3 ?

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

    There is one line in bold in the post, read it again, it answers your question.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      Sometimes even bold is not enough for some people to see. They need bold header.

      rated for the participants with rating lower than 2100
      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are the problems easy?I'm new in here.

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

    See the problems of previous educational rounds. Then you can get concepts about how the problems are

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Thanks all the authors to put the great effort and valuable time for preparing this educational round, these rounds are very helpful for learning.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't you delay this contest by two hours awoo

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are tasks sorted in difficulty order?

→ Reply
»
7 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Wish everyone high ratings :D

→ Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

First educational round rated for purple :)

→ Reply
»
7 years ago, # |
  Vote: I like it +36 Vote: I do not like it

aaand 10 mins delay :/

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

    :( was waiting for it and now have to wait more!!

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

      But the participation has crossed 7000 :)

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

        Yes! I hope their server does not gets down just like the first Div-3 where they had a huge number of participants.

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

      thats the sence of Codeforces... You wait... And wait... And then wait more... And finally the round becomes unrated :c

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

    someone know why delay 10min ...?

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

      Because the problem statements haven't be translated yet and KAN has to rush it! :D

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

      Someone's girlfriend didn't register

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

      I don't know why, but I was late to get breakfast and now I can participate in the round so I am thankful for it :)

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Rly?

→ Reply
»
7 years ago, # |
  Vote: I like it +97 Vote: I do not like it

That moment when the round gets delayed and you suddenly have 10 minutes but you don't know what to do with them.

→ Reply
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

What is test case 7 in C?

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

    Idk, but I changed my solution from int to long long and it worked, maybe you forgot long long?

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

      I did take long long , but still failed.

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

      i changed int to long long too, but my WA didn't change..

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

    Try:

    3 2 5

    1 3 3 4 6 7

    Answer is 10

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

    I ran loop from 0 to n-1 instead of 0 to m-1 and got WA in test 7 once. Check it

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Approach for C? I had thought to take the lowest number as one barrel with the least vol and then take another barrel such that a[i]-a[0]<=l and ai is maximum. Now if we have n-2 numbers between these such that a[0]<=a[j]<=x then we have an answer otherwise 0. Is this approach correct?

PS I failed on TC-#7

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

    Well, you can't do that. Because solution isn't optimal. What you need to do (I did it in this way, maybe there are easier ways) is find maximum number p such that a[p]-a[0]<=l. Then, from p to what number left, "erase" numbers bigger than a[p] (make them join group where a[p] is last element) so res+=a[p] for every decreasing p that has numbers bigger and not used. (sorry for bad english..) When you finish with the big numbers. Go from i=0 to remaining numbers that you didn't used. And that's it. I hop you at least understand something. Check my submission for more details.

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

    maybe the number of a【i】will exceed n-1

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is hashing needed in F?

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

    We can hashes subscripts for each letter within each query range.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, can somebody explain the solution for F (Isomorphic Strings)? My guess is some form of hashing, but I could not come up with a way.

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

    You need segment tree, but I don't know why do we need hashing. Isn't it enough to just check if length of sets is same or not? Appreciate counterexaple

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

      for example, aab and abb are not isomorphic.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        f(a)=b and f(b)=a , am I missing something UPD: I am stupid, nevermind

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

          then f(s[1]) = b != t[1]

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

          What the problem meant is: If you replace every character in s with f(s[i]) you should get string t. Meaning that "aab" and "abb" are not isomorphic since running s through your function would create string "bba" and not "abb".

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

    Your guess is correct.

    For a given query {x, y, len}, find the first occurrence of each letter which is after position x. Now if this occurrence is after position x + len - 1, we ignore it. Otherwise, let's say the position is x + p, then we know that f(s[x + p]) = s[y + p]. This means that the occurrences of character s[x + p] in s[x, ..., x + len - 1] should be on the same positions as the occurrences of character s[y + p] in s[y, ..., y + len - 1].

    Well, to check if these positions are actually the same, we can keep an array c[letter] for each letter where c[letter][i] is 1 if s[i] = letter and 0 otherwise. Then, using polynomial hashing on these c arrays gives us a O(1) comparisons of the occurrences.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

E was such a nice problem.., although was unable to do it during contest!!

→ Reply
»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Problem D. — I thought h1 was a typo in h_1 ≤ H: no sand should go over the fence; because of the no one clause, but as reading whole statement and asking to judge, turns out it wasn't ;'(

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

    you could have sent question if you weren't sure.

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

    Wait, so only the first pillar has to be less than H? The rest can be greater?

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

    LMAO, now I know why my solution was wrong

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

      Just found out that. Wasted a lot of time on D and then solved E with huge penalty.

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

    I think it isn't clear, but you should check that "h_1" <= H. If there were an example 1,2,1,0(H=1), It would be good.

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

    Honestly, I don't really see any problem with this line. The formula says the right thing, the description extends it meaning. I probably could have added it to notes, I agree.

    Chelslay says the right thing, you should have asked earlier if you thought we made a typo.

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

      Oh, I added a couple words now, by the way.

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

      Yeah, I also have to admit that I didn't read the statement carefully. What I'm sad is that I asked for it so late. If there were more time, I could solve it. ( since I got AC just before ;) )

      → Reply
»
7 years ago, # |
  Vote: I like it +27 Vote: I do not like it

for D, first condition that watched me h[i] <= H first time, after get WA on 7, h[1] <= H

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

    Oh my god. I didn't even realize that until I see you comment...

    → Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

ideas:

E: Sort, now the boxes can contain consecutive elements so we can dp

F: Let's calculate the hash for each character using a segment tree.

G: Sum the ranks of all possible teams (i,j,k), then for every edge (u,v) subtract the rank of (u,v,k) for every k. Finally add the rank of (u,v,w) for every triangle (u,v,w) in the graph

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

    Read accidentally, got spoiled. :o

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

    D?

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

      Run two binary searches. one for 1,....,K and another one for K + 1, .... LARGEST_VALUE, ... K + 1

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it +3 Vote: I do not like it

        I currently submitted a solution only by mathematical manipulations, previously I was squaring a number bigger than 1e9.38513673

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

          Oh, wow. That's a very impressive approach! Thinking final sequence as symmetry first, and removing redundant tail part. I really learned many things from your code. XD

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

          Hey! Can you explain what you did ?

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

            I firstly calculated the max height I can reach such that I have enough sand bags to come down, then I calculated how many sand bags are left from reaching that height and then coming down to the ground . After that I calculated the length of the plateau by diving the remaining bags with max height and if now there is some remaining bag , I just increase the answer by one because that can be compensated by a dual move of that height when we reach that height while coming down. We can prove that it will always be equal to one of the coming down heights.

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

    Can you elaborate how to dp in E please?

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

      f[i]=is possible to put in boxes the pencils from i to n?

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

    Hash can also be calculated by maintaining a prefix array of hash

    → Reply
»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

is it rated?

→ Reply
»
7 years ago, # |
  Vote: I like it +29 Vote: I do not like it

E solution... wrong.... so sad.... :( Is it rated...?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Can someone explain their solution for E? I was thinking about something involving cliques but couldn't figure it out.

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

    first sort all numbers, now you just need to group consecutive elements, we can use dp to solve this problem. Let dp[i] indicate whether the first i elements can be successfully grouped, dp[i] is transferred by dp[l] | dp[l + 1] | ... | dp[r — 1] | dp[r]. l, r is the interval endpoint that makes dp[i] exactly satisfy condition, As i increases, l increase, r increase, so you can use deque to maintain.

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

Is finding all triangles in a graph something well known to the community? I managed to find this which works in O(M3 / 2) but this is my first encounter of this algorithm.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It is an standard task. There is a simple sqrt-dec algorithm.

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

      Can you give me some hint / any tutorial about that algorithm?

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

        If you have time, you can just wait for editorial.

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

        I came up with this algorithm:

        Let's call a vertex heavy if it has degree >= sqrt(M).

        Let's call a triangle heavy if it contains at least one heavy vertex.

        1. We can count the light triangles as follows: Iterate over all edges (u,v) were both u and v are light. Now for every light vertex w adjacent to u, check if (w,v) exists in the graph.

        2. For heavy triangles, let's iterate over every heavy vertex u, and mark its adjacent vertices as visited. Now for every edge of the graph check if it has both of its endpoints visited.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C ? I got WA on test 8 :(

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sort. The first element (in the sorted array) will be taken for sure so, find the maximum array index which is less than or equal to (first element + l), if there are less than n elements then print 0 and exit. Else, starting from this index move backward and pick greedily such that there are enough of elements ahead of it. Hopefully, it is correct.

    → Reply
»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

→ Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

OMG, in problem D i thought i CAN NOT make pillar higher then H...

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

Why everyone is doing hash for F? There is a 24-hours hacking phase await... (don't know if random power base can save us from this)

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

    Is it possible to hash large subsets with one modulo? I thought about this during the contest but decided that collision probability would get too high...

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

    Can you explain your solution ?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +9 Vote: I do not like it

      It works like this:

      First we replace each letter in S with the distance to the nearest same letter on the right, or ∞ if there's no such letter. E.g. "abacaba" becomes [2, 4, 2, ∞, 2, ∞, ∞]. This takes O(n) time. Now instead of a sequence of letters, we have ≤26 interleaved linked lists — one for each letter type in S.

      If substrings X and Y are isomorphic, then all elements of linked lists that form X must be identical to those which form Y, except the last elements, since they point outside our region of interest.

      Therefore, X and Y are non-isomorphic, iff there is an index i, s.t. X[i] != Y[i] && (X[i]+i < len(X) || Y[i]+i < len(Y)). To find i, we quickly (using a lcp array) iterate over all j, X[j] != Y[j] and check X[j]+j < len(X) || Y[j]+j < len(Y). We will do at most 26 iterations, because X[j]+j >= len(X) means that j was the last occurrence of the letter at j.

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[PROBLEM C] Could you tell me where i wrong? My solution got wrong answer on pretest 6 https://ideone.com/Xfb3Ek

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

    Tets: 2 3 2 1 2 3 4 5 6 Your Answer: 6 Correct Answer: 4

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

      please figure out my false

      → Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Problem E was a subtask of this problem : Here

→ Reply
»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

38507649
I made a stupid mistake in 985F - Isomorphic Strings.
Come and hack me >///<
But I still love ♥ 127 ♥

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you believe it, I assumed that the positions in A were sorted. Couldn't figure out this till the end and got WA. Not complaining, but the examples could have been 'unsorted'? :(

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

    Same for E, (cost me one WA) but to be honest it's up to the contestants to read the problems carefully.

    → Reply
»
7 years ago, # |
  Vote: I like it +122 Vote: I do not like it

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E? (My greedy solution got hacked)

→ Reply
»
7 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Seems that uwi is on a killing spree for Problem F...

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

    I tried to hack solutions of rolling hash of 2 const modulo after waking up, but the contest had finished.

    To hack rolling hash by 1 const modulo is very easy by birthday attack.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D?

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

1000000000000000000 1 For this case how the answer be 1999999999

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

    1 2 ... 999999999 1000000000 999999999 ... 2 1

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

      no sand from the leftmost spot should go over the fence; What does it mean then?

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

        Only h1 must be less than or equal to H (so that it doesn't get over the fence). For other pillars they have no restriction on their absolute heights; their heights only need to have at most difference of 1 to their neighbors' heights.

        I've been thinking wrong about this during the whole contest, and I had no idea why I was getting WA on test 7. Now I feel really bad that I couldn't realize this :(

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

          Okay, then why the answer to the case 20 4 be not 6? here 1 2 3 4 5 5 = 30.

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

            1+2+3+4+5+5=20.

            If 1 is your h1, meaning that it is the pillar that is leaning against the fence, then the other side has to descend from 5 to 1. It can't just stop at 5 abruptly.

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

          I got 5 wrong submissions because of this. Luckily I realized it during the contest. Misreading statements is one of my specialties.

          → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why are "acc" and "cac" not isomorphic for problem F?

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

    because it is not bijective. f('a') = 'c' and f('c') = c(for 3rd character of 'aac')

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody idea for E.

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

    Code

    My solution for E:

    first we sort all pencils.

    we define dp[i]: is it possible to solve problem for pencils 1 to i.

    and d[i]: greatest j (j <= i) that dp[j] = 1.

    now we put x = d[i — k] and after that if a[i] — a[x + 1] <= d then dp[i] = 1 else dp[i] = 0.

    and d[i] = i if dp[i] = 1 else d[i] = d[i — 1].

    (sorry for bad English)

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

      Why are you taking x = d[i — k]? Can you elaborate more on that?
      UPD : Got it NVM.

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

        In last box there are at least k pencils so we have to find rightmost j that
        j <= d — k and dp[j] = 1 now check that pencils j + 1 to i can be in one box or not?

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

      In Problem E,why is that if a solution exists, there exists partitions such that they form contiguous segments of the Array.Thanks in advance .

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

        First we sort the array so in each partition (max — min) will be minimize.

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

    -sort the array

    -find a slow dp solution : O(n^2)

    -try to optimize it to a faster dp solution : O(n * logn) or O( n )

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -54 Vote: I do not like it

D was the worst possible type of tasks for me. It's a pity it appeared in the contest, even more that it was placed before E, which was quite easy for me.

Also I'm not sure that the round should be rated as I started coding D because at the time of making a decision, E was not solved by anybody (so E appeared to be harder than D), due to the error. Issues in E had impact on many participants. I believe I got 3 problems instead of 4 due to that.

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

    Wait, this happened about half an hour into the contest. Wasn't that your fault to spend the rest of the time on the problem of your weaker topic instead of reading the other ones? I'm sure that the ranklist after half an hour tells nearly nothing about the difficulties of the problems.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -30 Vote: I do not like it

      I checked more precisely. At the time I was looking at the next task (after solving C), there should have been 23 E solutions accepted already, this was the last one:

      http://codeforces.me/contest/985/submission/38494892

      At the same time there was 0 accepted solutions to E and there were 11 accepted solutions to D, the last one: http://codeforces.me/contest/985/submission/38495105

      I have no reason to lie, as I said I expect a positive rating change. If I had seen these numbers when I was making a decision I would have started with E.

      I just have a feeling that the issue with E is sufficient to make this contest unrated. I was impacted indirectly but many people were impacted directly.

      Besides — there was incorrect author's solution, this fact should make the whole round unrated, given ACM rules. I object to policy of making rounds rated just to please the maximum number of people. Rounds should be unrated unless they ran perfectly in 100%.

      What do you think MikeMirzayanov?

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      UPD: My fault... See comments below.

      Well, it is a good round ... but problem D. (No offensive).

      Even though problem D itself is a good one, but it is not very friendly to the CPPers.

      We need to handle two long long multiplication carefully. ( Aha! I know it! I avoid this! )

      And then math functions bring floating errors! ( WHAT? TIM_20180519215120)

      Should "handling floating errors" really be the part of the contest?

      My key point is : D is a good problem, but it shouldn't make certain languages better than others.

      (Making D's limit into 109 would be a better choice, I don't know any brute force that can pass 109 but not 1018).

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

        We had a solution and didn't really want it to pass. It's like one step easier than the intended one.

        All calculations in my solution are performed using only integer types and fit into long long.

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

          Thanks for replying.

          We had a solution and didn't really want it too pass. It's like one step easier than the intended one.

          OK, then I have no problem with D's limit.

          All calculations in my solution are performed using only integer types and fit into long long.

          So, you mean that long double is intended to fail ? Should "using long long instead of long double" be a part of the contest ? Maybe it should be but I don't know ?

          Really, worst time ever : getting WA on test 7 but the logic of the program is absolutely right, struggling whether to submit again or to give up.

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

            If you have to multiply numbers that big then you are doing something wrong? I mean, use long double as much as you want to if you are sure in the correctness of the answer you get. Or you can think a bit more and get a much smaller estimation on the borders of binary search.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              ← Rev. 4   Vote: I like it 0 Vote: I do not like it

              No, not that, I said I avoid long long mutiplications.

              I got WA using ceill(n/X) but AC (preliminary) using following code:

              for(; n>0; n -= X, ++Ans);

              I don't think it is wrong using ceill(n/X).

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

                Actually, you output 2e+009 instead of 1999999999. Maybe this was the problem, not the precision of calculations?

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

                  Yeah, I just saw that.

                  Thanks. Sorry for bothering.

                  It's my fault. TIM_20180519215120

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

                  No problem, it happens :D

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

        I pass it using long double...(after contest q_q)

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

          ...

          TIM_20180519215120

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

          I am getting WA using long double...I am pretty sure it's due to floating errors.38530049..Please help

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

            only use long double when you dont need accurate number

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

      To make it more clear — maybe it wasn't understood for the first time.

      If there were no issues, that would have been my fault 100%. However in this particular case, my decision was biased by the bug in writer's solution.

      I also think that it might be the case with more people as the difference in accepted solutions between D and E is very small, while it should be something like 250 for D and 450 for E, but I guess that many more competitors jumped to D as they saw that nobody was able to solve E for almost an hour.

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

        Most people also do the problems in order because they expect them to be in order of difficulty.

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

    The worst excuse ever.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it -6 Vote: I do not like it

      It is not an excuse as I will probably get positive rating change after this contest (at least this was my knowledge when writing this post)... And I'd rather give it up for unrated round as I feel that this contest was interrupted by the bug.

      It just demonstrates the subtle impact of the issue. I based my decision on the number of problems solved and I got stuck on D until the end of the contest and I have a reason to believe it would not have been the case, but for the mistake.

      As regards previous comment — it is not true. After 40 minutes I should have seen comparable number of solutions to both problems. If I see around 30 solutions on D and 0 on E, it is a clear indicator for me that D should be easier than E (not everyone should follow this logic).

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I got RUNTIME_ERROR in pretest 7? 38505110

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

    The error is caused in this line:

    while(cnt && abs( *(s.rbegin()) - *L ) > l )

    You are trying to access to the value pointed by L, but a few lines before, you erased that value from the set. I saved *L in a variable before deleting it from the set, and the Runtime Error was gone, but now it gives Wrong Answer. I'm not really sure what's the idea behind your code, so I can't help you with that. I hope this comment helps you solving the problem :)

    PD: there is another error in that line: you forgot to check that the multiset is not empty before trying to erase an element from it. That may cause Runtime Error too. Bye!

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help with a good test case for problem E ? cannot Figure out where it could go wrong. #noob

→ Reply
»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Hi, I just wanted to mention that it seems that users with rating above 2100 are registered as official contestants... or at least they don't disappear when I unset the "show unofficial" checkbox.

Hope that doesn't causes any problem.

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

    Educational rounds are rated for users with rating below 2100, but it doesn't mean other users are unofficial. I think, In those rounds all users are welcome to participate officialy.

    → Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

In contests page, the hacking phase for this round seems to be for 12 hours rather than a day.

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem D is similar to SRM 721 Div1 Easy.

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

For problem F,if the size of alphabet is up to 10^5 or larger and other constraints remain the same,is there any approach to solve it?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone tell me Problem F why my solution get WA on test 16's 9259th query? I have been debugging for more than five hours. qaq. this is my submission code: 38512729

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

As a novice, I have a question for everyone. Why did I submit the same code twice, but one got AC, another got WA. 38509969 during the game. 38524984 after the game

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

    Submit with diagnostics. Perhaps you have some undefined behavior due to the overflow or memory access.

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

    emmm.. I think your code "if(n-que.front().w<k)" has a little bug. if the queue is empty, then your code will runtime error?

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

      maybe you are right. modified code got ac...thanks...but i still can't understand why i got a different result

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C:Why I got TLE Verdict?38494646

I didn't use while() so there are some troubles on sort?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

System test has finished,so is it rated?

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

    why not rated?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      Issue of the writer's solution was wrong on Problem E

      (And not clear words on Problem D?)

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

        so it's unrated? but Problem E's tests are right?

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

          The test case was fixed after 45min the contest started(and affected some verdict).

          I think some contestants waste the time because of the issue, so it's good that this contest change to unrated (or semi-rated).

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

            is this contest really unrated.

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

              UR?My Rating was changed a few minute ago.

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

            Why not wait 10 more minutes and then discuss whether it is rated?

            :)

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

when will the editorials be updated?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The rating were changed so it's rated

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

does hacking a solution not effect our rating

→ Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Is there any solution for F except O(N * 26)?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Thanks for div2 only contests !11!1

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

__i use ideone to run the code but the solution is copied and i get unrate. Does my computer have malicious code? Explain me, please.

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

    ideone is by default public. you can see submissions in https://www.ideone.com/recent. Maybe someone copied from there. keep your submissions private from now on. Its an incognito type icon near stdin below input text box.

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

      Thank you very much ! I ever never know :D

      → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Where is the editorial ?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

In Question C,I had got time limit exceed in test case 19 in java while with same algorithm (same code) in C++ is able to pass all test cases.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D,

when I use round() function to round the division operation to nearst integer value it causes me WA in testcase 18 though the round function isn't making any difference!

accpeted sol: http://codeforces.me/contest/985/submission/38600567

wa sol : http://codeforces.me/contest/985/submission/38600584

round() is not making difference: http://codeforces.me/contest/985/submission/38600633

and all of this solutions provide correct output -1 in my local machine!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Thank you.

→ Reply