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

Hello Codeforces!

On Sep/20/2021 17:35 (Moscow time) Educational Codeforces Round 114 (Rated for Div. 2) will start.

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

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

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

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

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 tourist 6 82
2 LayCurse 6 158
3 LJC00118 6 159
4 mtsd 6 207
5 244mhq 6 212

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Savior-of-Cross 20:-4
2 tzc_wk 12:-5
3 TheAshenWitch 9
4 SSerxhs 9:-1
5 Makise_Kurisu 10:-6
84 successful hacks and 270 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Ormlis 0:01
B KPATKOBPEMEHHOCTb 0:01
C gleb.astashkin 0:05
D tourist 0:12
E tourist 0:21
F Potassium 0:23

UPD: Editorial is out

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

Comments Comments (220)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it -151 Vote: I do not like it

So Mike fixed the problem and found out the cause ?

So many assholes downvoting these days like do you feel important when you downvote ? get a life retards we haven't seen any information about the problem yet

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

    Very bad words for the community

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

      That's what haters deserve it's not for the community i don't see any problem in the question i asked

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

        ok Jhin, voting these days is unfair! but this isn't a reason to say bad words.

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

          I have seen worst it's not a big deal once a guy wrote to the authors **** you and your contest he got upvotes and his comment didn't get deleted and nothing happened anyway these bad words aren't for who's downvoting now they're right but it's for Who downvoted the 1 rev of my comment

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

    Welcome to Codeforces

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

    Join the club bro. Literally everyone has been downvoted before its not a big deal.

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

      it's annoying when it gets repetitive everytime someone ask or say something i got downvoted alot before but not that repeatedly

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

    Sometimes maintaining silence also solves lot of problems.

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

      That's what I always do but sometimes say what you want I don't care about the downvotes after what i said

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

Good luck to everyone!

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

Educational rounds are usually very good, hopefully this one too. Good luck to all!

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

Is it rated?

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

thanhchauns2 go big or go bald...

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

Thank you for this competition, it gives me a chance to advance.

Tomorrow is China's Mid-Autumn Festival. happy mid-Autumn Festival!

→ Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it -30 Vote: I do not like it

Hidden...

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

Tomorrow is Mid-Autumn Festival, which is one of the Chinese traditional festlval. I wish all Chinese participants a Happy Mid-Autumn Festival!

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

    Wishing you a very blessed Mid-Autumn Day!

    中秋节快乐

    顺便一提

    我不是中国人。

    😅

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

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

i have always got negative delta in edu rounds lol hope to break the streak

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

    update negative again lmao:( b was a nightmare c saved my a*s from nosediving into pupil

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

I feel dumb reading D from last 45 minutes and not even understanding how the answers for test cases are being constructed

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

Don't understand why my code of problem C works less than 0.2s on local machine with 2*10^5 & 2*10^5 data while TLE on testcase 6...

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

    can you tell me how do you test for such large test cases?

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

      Hello , in B : 2 3 4 . So why max pair is 6 . I just see AABBBCCCC , and max pair is 4 Can you explain it for me ? Thank you so much

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

        A block of n consecutive letters contains n — 1 pairs of equal characters; so AABBBCCCC contains 1 + 2 + 3 = 6 pairs of equal letters. If a letter coincides with two of the same type, it is counted in both pairs.

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

          Ah i already have the answer , but thanks guys

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

    Maybe you didn't use ios_base::sync_with_stdio(false); cin.tie(0); I got TLE twice because of that...

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

Hey!
Is weightage for every question the same in Edu rounds?

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

Hope I can return to the candidate master.

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

i don't understand how 4700 people solved C.

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

    It's easy, but I don't know why I always get TLE...

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

      Yep, I also got a weird TLE verdict, but after placing the "Fast C++ I/O" stuff I got AC.

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

        Thanks very much for this "Fast C++ I/O"... I got AC after adding it. But I'm really disappointed that this becomes the key point of AC or not...

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

      the time complexity is about O(nlog(N) + mlog(n) )

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

      .

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

        Thanks. This is much faster. I never know it impacts so much.

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

{deleted]

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

How the heck we generate the 'M' sequences in D ? given that we have taken the difference between last element and every element for each item and sort it in increasing order ?

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

    I am sorry to be "that guy" but I think your question isn't very clear. I'd happily help (I solved D) but I can't if I don't understand the question!

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

    i tried to use some priority_queue strategy. Start with a vector which contains all the last element of each array and on each step decrease one from a spot and recalculate the sum. think about (x,y,z,SM) -> (x-1,y,z,SM1),(x,y-1,z,SM2) (x,y,z-1,SM3) (and the priority queue is sorted by the SM) (i dont know if its correct but that was my idea)

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

    I used a BFS ( sort of ) with a priority queue. Initially, i inserted the max sequence in the queue with its cost.

    After that, i kept on processing the top of the queue ( max cost ) and inserting its possible children ( i.e. 1 position different from the parent ) into the queue. Ultimately, since we are using a priority queue, we will visit the nodes in decreasing order. If we ever hit an unmarked node, we can return.

    However, we need to be careful about TLE and MLEs. In order to avoid those, i trimmed the priority queue ( used a set ) from the lower end, if we exceed a MAX LIMIT ( 1.5 mil in my case )

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

The only thing problem C educated me about was that even 1e18 is not enough to keep as infinity in your template

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

    In what cases the answer can exceed 1e18?

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

      You've got just 2 warriors of strength 1, the dragon has 10^18 atk and 10^12 def. The answer is 10^18 + 10^12 — 2.

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

    just use const int inf = numeric_limits::max();
    It will work fine even with #define int long long

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

In C, my O((m+n)logn) solution gave TLE on the 6th test case. Any idea why?

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

    Perhaps you have a logic mistake in your algorithm. I thought I had it too but it turned out that I made a mistake and had to think of a different way to save myself from checking all exponentially many possibilities.

    Edit: oh, derp. I misread and thought that the question was about problem D. Sorry!

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

    same but i somehow passed it by using fast I/O and "\n" instead of endl.

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

    cin/cout are slow operators. Better use scanf/printf (cstdio library), or add ios_base::sync_with_stdio(0) In the beginning on your program, which boosts iostream performance (but beware of combining iostream/stdio in one program!) Just google "how to boost iostream", you should find some tips easily.

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

How to solve D?. I thought of using max heap but was getting the wrong answer in test case 5.

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

    Me too, I was using a max heap too but also get a WA on test 5

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

    View a build as a vertex in a graph (or rooted tree), there is an edge between two builds (vertices) if they only differ in one slot by 1, and the edge's weight is the strength difference of the two builds, then we can perform something like Dijkstra on the source, which is the optimal solution if there are no banned builds (the build consisting of the last item in each slot). we iteratively find a nearest (with lowest strength loss) new vertex (build) like what Dijkstra's algorithm does, and as soon as we find a valid build, print it.

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

Meaningless F with the easiest gf knowledge

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

    What is "gf"?

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

    well… it would be easier if one observe that there are at most O(k^0.5) kinds of length.

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

      Yeah, this is how I've seen this problem solved before. I'm interested in how you would do it with GF, is the complexity better?

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

        Removed.

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

        I'm weak in GF, so you can ask aleph1022 for more information.

        Let $$$A(x)=\sum\limits_{i=1}a_ix^i$$$ be the OGF of subarrays, $$$a_i$$$ is the number of valid subarrays whose length is $$$i$$$.

        Let $$$B(x)$$$ be the OGF of ways to make the whole array and $$$[x^m]B(x)$$$ is the answer.

        It's easy to show that $$$B=1+A+A\times A+A\times A\times A+\cdots=\sum\limits_{i=0}A^i=\frac{1}{1-A(x)}$$$, so you can compute the inverse of $$$1-A(x)$$$ in $$$O(n\log n)$$$.

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

nice problems but i'm wondering why my f is wrong answer on test 13 QAQ

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

In problem D, I was stuck on this approach and was getting WA on test 11. Here is my approach: We can see that $$$4^{10} > m$$$. Initially we can consider the case where we take all the last elements. We define a variable $$$p=1$$$, denoting total number of ways with current elements. Then we can greedily add elements to our set from each row until $$$p \leq m$$$, each time we add element from such row which has largest latest element (from end). Then we can generate all sets and maximize our answer.

But I can't understand why this approach is wrong. :(

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

    If I understand your solution correctly it is similar to the one I thought at first.

    Why do you think adding the element from the row which has the largest latest element produce the next bigger permutation? I believe this is not always the case.

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

      I think I did not make it clear. Let's say we take $$$x_i$$$ (number of elements that are available for us) elements from $$$row_i$$$.Also we take all the elements that are equal to the last element we entered. Then we stop when $$$x_1 * x_2 * ... * x_n > m$$$. Now, my claim is that any other combination which contain some element from some row $$$i$$$ such that it is out of reach of $$$x_i$$$ elements, then it would definitely give smaller answer than the minimal combination that we can form if we do not take elements outside of $$$x_i$$$. But I am not entirely sure about this claim.

      [Edit]: Well I found a testcase which prove my claim false.

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

        My solution is similar to yours which was getting WA on test 13. Now I know why I was wrong.

        Please see the test data below—— 10

        1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

        1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

        1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

        1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

        1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

        1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

        1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

        1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

        1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

        1000 ...(992 elements) ...993 994 995 996 997 998 999 1000

        We can then ban all combinations of the last element in the first nine lines and the last 5 (or any other element greater than 4) elements in the last line to hack your solution

        5

        1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

        1000 1000 1000 1000 1000 1000 1000 1000 1000 999

        1000 1000 1000 1000 1000 1000 1000 1000 1000 998

        1000 1000 1000 1000 1000 1000 1000 1000 1000 997

        1000 1000 1000 1000 1000 1000 1000 1000 1000 996

        you will get Wrong Answer because you have to take the element —— 995 but you don't.

        I'm sorry. My English may be poor.

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

How to solve B?

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

    Find minimal and maximal number of adjacent equal letters, everything is possible in between.

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

      I saw almost everyone solved the problem as you've said. Is there any theory related to the problem? I want to study the topic in a bit more detail. Thanks in advance.

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

        I guess the theory you are searching for is Greedy Algorithms and Math.

        That's because the concept behind "find min and max number of ..." is that we can always arrange the letters in a greedy way (you can consider how you might arrange (a, b, c) = (10, 2, 2) to get the max/min possible adjacent equal pairs)

        After figuring out the above, you may also realize that you don't need to simulate the process but rather can solve it by some Math properties.

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

    WLOG assume a >= b >= c so the max possible same pairs will be in case like aaaabbbbccc => such pairs can be counted as ( a-1 ) + (b-1) + (c-1) = (a+b+c-3) so m<= a + b + c -3 and the min possible pairs will be in case like abacabac in such a case the possible same pairs can be counted as (a-b-c-1) so m >= a-b-c-1 so if m is in between this range we can always have an answer or else no answer

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

      actually the min possible pairs should be abacabac... rather than abcabcabc...

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

terrific terrific terrific terrific terrific terrific terrific sample cases

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

I can't believe I forgot how to do knapsack with items appearing arbitrarily many times and sum of weights a small number >_>

At least I'll remember it now in the future, very educational round :)

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

    +1

    But you can still solve the problem by using FFT or polynomial inv if you haven't oberseved that

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

How should I improve myself to solve problems like B?

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

    Just keep on practicing the questions of the rating that you are targeting from the problemset try doing at least 30 problems of that rating and also try to give every contest either live or virtually for getting the feel of solving problems in contest. Hope you will soon be able to solve B in contests :)).

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

Could someone explain the first sample of F? The way I'm interpreting the problem, the answer should be 0. Problem Statement Preview Since any valid array a needs to have as many [occurrences of $$$A_1= [2, 1, 2]$$$] in it as [occurrences of any non-empty sub-array of $$$A_1$$$], in particular it seems that our array can't contain the number 2. Since $$$A_1$$$ itself has 1 occurrence of $$$A_1$$$ but two occurrences of [2], which is a nonempty sub array of $$$A_1$$$. And then we are banned from using the number 1 as well since it's contained in $$$A_1$$$ and we can't make $$$A_1$$$. And then similarly since $$$A_2=[1,3]$$$ we are banned from using the number 3 and it's impossible. What's the right way to read this?

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

I really liked the problem C (cool implementation of binary search + some key observations). However I did not like the difference in constraints of attack and defense upper limit ( the attack can be as high as 1e18 and defense up till 1e12).

When I first read the problem , I read only the defense constraints (1e12). I reasoned that since was n was also only till 2*10^5 , the answer can never exceed 1e18. So I took 1e18 as INF. I submitted my solution with INF set as 1e18 only to receive a WA . I reread the problem , couldn't figure out a problem until I saw the constraint on attack. Quickly changing some code I submitted again and got AC.

In hindsight I should have been more careful while reading the problem and there was no fault of the authors , however if possible from the next time this can be avoided.

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

Hi everyone, any pointers on how we can solve B? wasn't able to come up with any approach for it.

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

    Think in the maximum amount of adjacents with the same letter and the minimum amount of adjacents with the same letter. Then check if m is in that range.

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

      Hello , in B : 2 3 4 . So why max pair is 6 . I just see AABBBCCCC , and max pair is 4 Can you explain it for me ? Thank you so much

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

        Of course, A-AB-B-BC-C-C-C. The - means each adjacent with the same value, so is 6

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

How to solve E?

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

Can someone explain what does the following line mean in tourist's submission 129351289? I'm literally this line away from solving D :(

if (v[i] < c[i] - 1) {
    break;
}

EDIT: seems this line is not very crucial, my original implementation was not fast enough.

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

Write lots of weird stuffs on problem D and suddenly realized that I had just "invented" trie again.

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

Is there any easier approach for problem A than this one? I couldn't come up with idea immediately.

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

    I took embarrassingly long too! I had it slightly differently.

    Here's how

    Yours is better. And, well, you must admit, this is a very simple few lines of code. It's just that problem A was probably not the usual stuff you'd expect and that's why it took so long to think of!

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

i using cout_cin in contest = TLE 6 https://codeforces.net/contest/1574/submission/129409353 i using printf_scanf after contest = Ac https://codeforces.net/contest/1574/submission/129417724

lol

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

    Just add

    ios_base::sync_with_stdio(0);
cin.tie(0);

    at the beginning of the main function. This boosts iostream, but makes using both iostream and stdio dangerous, as the two are now desynchronised (as the name of the invoked method implies).

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

C tests are bigger than 1e18? :|

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

    Yes.Otherwise it will be WA on 3.

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

    yes. think about strengths are all 1 and x and y are 10^12 and 10^18. so just make it x + y.

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

I used MAP , HASH , priority_queue and greedy in Problem D.But I haven't solved it. So I'd like to know whether Problem D has a high point of about 2000? I think it is much more difficult than Problem C.

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

I want to kill myself . Missed AC on D by a stupid mistake $$$ if(z >= ans)$$$

AC Solution

Wrong Solution

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

https://codeforces.net/contest/1574/submission/129407156 nice submission from alt to hack by yourself

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

https://codeforces.net/contest/1574/submission/129419462 Hey Guys, noobie here.I thought I solved c in (m+n)logn but getting TLE on test case 4. Kindly help

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

    Hi, so I have a question for the community as well, the answer to which influences your case.

    I see that the limits for a solution are the same regardless of the language in which the solution is written. Does that mean, that using Python (without extensive Python optimization knowledge) instead of a much faster (in common use) language like C++ can greatly influence scores on CodeForces?

    I am asking this, because this is exactly what happens on another competitive programming website on which I am a regular organiser (instead of participant) and thus, we don't allow Python there.

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

    Try adding this template:

    Spoiler

    and use stdout.write(str(ans)+'\n') instead of print (important if you print more than 100000 times).

    But yeah this problem had a tight time limit for python. Had to switch from pypy to regular python 2 to get AC.

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

nice last time solved B C and couldn't solve A , now i solved A C and couldn't solve B >:(

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

Just replaced cin and cout in problem C with scanf and printf, and it worked. Just wish I had tried that earlier (>﹏<）

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

    If you want to keep using cin and cout add these two lines at the beginning of the main function:

    ios_base::sync_with_stdio(0);
cin.tie(0);

    As far as I can remember these lines desynchronise iostream and stdio and perhaps do something more which makes using both input methods dangerous, but as long as you are using only cin and cout and these two lines, you shouldn't run into any time limit problems caused by input/output.

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

The fact that the last round had an unexpected (unknown) error, and this round just after 2 days went flawless is one of the reasons I love cf. Great work.

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

    The Pretest runs for the first 2 problems actually seemed smoother than usual, with almost instantaneous results.

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

B. Combinatorics Homework

Input:

1

1 1 3 2

Judge output: YES

I think the output should be: NO

Because you can't make 2 pairs in the context.

[abccc] How can you make 2 pairs? Can you please specify your string that satisfies?

A brief explaination would be appreciated. Thank you.

if(you think comment should be downvoted) continue; 	//keep thinking but don't downvote :-)
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    'ccc' is 2 'cc' pairs, they just share the middle 'c'

    edit: 'adjacent' was probably technically incorrect...

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

      Yes bro.

      exactly m such postitions i that the i-th letter is equal to the (i+1)-th one.

      I could have put more attention to this line. I think CP isn't for me and i should leave now. :-(

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

        For what it's worth, this contest was still meant for div2 despite whatever connotations 'edu' might entail. I wouldn't sweat some brick-y outcomes.

        As for quitting, I'm a fan of people doing things they find intrinsically rewarding rather than pushing themselves due to extrinsic reasons or ego. There are also other cp sites besides codeforces if you want to try atcoder ABC's for instance. Either way, I can only hope you find what works for you.

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

When io issues aren't just affecting python users...

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

I don't know why my program with same time complexity as others which passed don't work. Can anybody please explain why this is happening. This is the link to the code.

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

    Your getmin function takes a vector a directly, so it makes a copy (which takes $$$O(n)$$$) each time you use it, if you change it to take the vector by reference (just adding an &a) you'll get AC.

    Here is the corrected code 129426111.

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

Why did this did not worked for C? https://codeforces.net/contest/1574/submission/129409251 I have seen few submissions which follow the same approach and they got passed. Can anyone plz help?

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

    If you use cin/cout for input/output, ios_base::sync_with_stdio(false); cin.tie(0) should be your best friend.

    Here you are 129426352.

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

Can anybody tell me why my solution to D is failing?

I iterate over all the sums I can get with those numbers, but in order from maximum to minimum. As soon as I have a solution which is not 'banned' I print it out. I guess it should work.

In priority queue I keep two values (sum, chosen items).

EDIT: I had a little bug but now after fixing got TLE. But why? I think I should find the solution in $$$m$$$ operations.

Solution

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

    You are adding repeated states to the PQ. If a build is already in the queue you can skip it.

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

      Yep, fixed it, silly mistake :(. Thank you by the way.

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

        Nice, btw you can only store the build (in the set of visited), the sum is not necessary since it can be deduced from the build

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

          So you mean to change the pq comparator?

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

            That would indeed force you to change the comparator and I think it wouldn't be worth it because:

            You'd have to recompute the sum of the values every time you need it, which increases the time complexity constant, which isn't good, and

            You'd lose time on writing a custom comparator which is not exactly the easiest thing to do and can easily go south, so unless you've already done similar stuff, it's risky, and even if you've got experience with that, it's still a waste of time during the round.

            The only "pro" of this approach would be to save some memory, which is negligible. Much more so than the time you would otherwise save.

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

            No, I mean that the set you added can be only of vector<int>. Instead of pair<int, vector<int>> :)

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

              Oh, got it. But I feel like my approach is better. Even if we are in CP, I think that vector or any kind of collection should hold the values from the same context.

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

              This would then require a custom comparator, though. Unless you do another funky thing and let the strength be the first (zeroth?) element of the vector.

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

Can Anyone help me find error in my code i'm getting wrong output format Unexpected end of file — int32 expected in Test 6.

My approach is: I'm starting with the vector having the highest build(i.e, all the last elements of all rows say top layer) in the priority queue then for each top element of the priority_queue I'm pushing all the new vectors with a new element in one of the rows that can be formed from the next lower layer with the build value of the vector at the beginning of vector.I'm pushing popping until i get a vector which is not in the our set of bad vectors.(soory for bad explaination >_<)

Code

UPD: I was storing some same vectors multiple times. Accepted Code.

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

Problem C has taught me that qsort TLEs and std::sort doesn't

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

    Yes, because the Quicksort algorithm, while having "quick" in its name is not that quick after all.

    Firstly, its O(n log(n)) complexity is just the average case, although admittedly by randomizing the pivot, the only thing stopping your case from being "average" is EXTREME bad luck, so this is negligible. But...

    Secondly, std::sort is a wicked hybrid algorithm optimized for all kinds of stuff and well... it's faster.

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

Seems like tests for problem F were super weak, I hacked many reds without even knowing the question

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

    how can you prepare test cases without knowing the question???

    p.s. i have never hacked so no idea

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

My solution to problem D using trie data structure. First of all construct a trie of the banned combinations. Now we will be iterating over each banned prefix(using a dfs on the trie) and take the remaining values the maximum possible. Here is my submission. Hope it helps someone. Submission:- https://codeforces.net/contest/1574/submission/129429122

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

    "and take the remaining values the maximum possible"

    could you please explain this?

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

      Basically ,what I am trying to do is that go to every prefix which is banned. Now let's assume till index x-1 you have taken the banned prefix. Now, for the index x, you will choose the largest possible value which can be taken for that particular index, such that that the prefix upto index x is not banned. Once you have taken that, for the remaining indices, from x+1 to n,you can just take the maximum value among all possible values for each of the indices (x+1 to n).

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

        Nice idea, thanks!

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

        Based on how you explained it here, I think I have the same! Pretty interesting to think of it as a trie. Then again, I only "know" trie in theory and never consciously used it.

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

    Can you please explain your dfs function?

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

      In the dfs function, what I am doing is that I am going to each node of the trie. Now, this node represents a banned prefix. Now for this banned prefix I will choose the maximum value for the next index such that the sequence doesn't become banned(in my code it is done using the x variable inside dfs function). For the remaining indices ,I am just taking the maximum (stored in the suff vector).The now vector stores the current prefix(banned obviously). Hope it helps.

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

    Almost the same approach but used hashing in place of trie ( as I dont like pointer much ). MY_SOLUTION

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

I think my solution for problem D is kind of different. I passed pre-tests by using the pigeonhole principle， brute force and a trick.

At first, I got a wrong observation: if $$$\prod_{i=1}^n x_i > m$$$, then we can only consider the top $$$x_i$$$ equipments for the $$$i$$$-th slot, because according greedy and the pigeonhole principle, the answer must be already considered. And $$$\max_{i = 1}^n x_i$$$ can be calculated easily by using binary search. Now, we can enumerate all possible builds and get the "answer".

After getting WA on test 13 for a lot of times, I find out a case that the observation did not work. For example:

3
6 1 2 3 4 5 6
6 1 2 3 4 5 100
6 1 2 3 4 5 100
3
4 6 6
5 6 6
6 6 6

And I think out a trick: for a banned build $$$b$$$, for the $$$i$$$-th slot, replace the $$$b_i$$$ with $$$b_{i} - 1$$$, and then take $$$b$$$ in to consider.

The trick appear to cover cases that the observation did not work, and I do pass all pre-tests.

(Hope that I will not get FST

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

129449581 got accepted But 129414197 didn't

There is difference in only one line of program.

When i used (long long) 9e18, it passed. But when i used LONG_MAX i failed.

Can anyone say me what happened? Thanks in advance!

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

    long max is actually the maximum integer that can be represent in type int which is 2147483647. This number is clearly not large enough for your solution.

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

      Yeah! Thanks man!

      in codeforces LONG_MAX is 2147483647 LONG_LONG_MAX is 9223372036854775807

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

Where is the official editorial...

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

How to solve D?

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

    You can use a max priority queue ordered by build strength to generate the most powerful builds in decreasing order.

    First push the max build on the queue, then loop. On each iteration, pop from the queue, check if the build is banned (with a map of banned builds). If it isn't output and stop. Else generate new builds by decrementing at each index of the popped build (so at most n<=10 new builds are generated) and push these builds on the queue ordered by their strength (if they haven't been pushed already — can be checked with a map of seen builds). Since the all the popped build are different at most m+1 builds are popped and at most m*n builds are pushed which is fast enough.

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

nice problems, I love problem D.

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

I got the min-max range logic for B.

But I can't figure out what is wrong with my first approach. Can some help me debug it?

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

I wasted 4 submissions because of using int in problem C :(

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

    .

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

      That's not a good idea sometimes the time limit won't be enough with long long

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

        Does CodeForces compile into 32-bit executables? I'm asking because long longs are slower only in that case. Another competitive programming site changed compilation to 64-bit and now there is no difference besides memory use.

        But additional memory use is not something completely unimportant. Usually it doesn't matter, but problems can easily be made to require better memory use. I've seen a problem (not on CodeForces) which actually required the use of short ints!

        Also, having templates with a couple of useful things like #define st first may be good (I personally don't use that), having multiple dozen lines of code (more than fits on a screen) as a template is most definitely a bad practice, especially at the lower levels. And it's not like templates help much besides obfuscating your code to protect against potential hacks. You can take a look at the submissions of some of the top people on CodeForces and all of the ones I've seen fit on one screen. Some of them are even a very modest couple of lines. And they most definitely don't have bullshit like #define int long long.

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

can anyone help me why am i getting tle in D?129459481

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

It says that this contest will be rated for div 2 participants but my rating hasn't changed after the contest. My rating previously was 1099 and still is the same. Can anyone please tell me why is it so?

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

    See after the contest there was hacking phase. After that within 2-3 hrs you can see the changes.According to indian time I would say by 3PM

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

Why isn't the system testing started yet? It's been 3hr since the hacking phase ended.

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

    The system tests were ran from the very beginning. Notice, how submission status was never "Pretests Passed (3)" or something like that, but straight up "Accepted". I was surprised when I saw that!

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

      Oh, sori sori, I actually meant when will they run all the hacks over the submissions? It had been too late now :/

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

    Still, don't start yet.

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

I think D is not difficult for someone who know how to use heap,maybe it only can get 1300.

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

My rating is not increased yet, why??

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

Since every contest ends up with questions like "when my rating changes" it would be great if stage "System Tests" will be followed by stage "Rating calculation". It would calm down a lot of people.

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

    then there will be questions about why rating is being calculated so slow

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

      Adding percentage of progress (like in system tests) could partially solve this issue too.

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

        I guess rating changes applying is manual work, automatic calculations should be pretty fast. But I might be wrong. Correct me if someone is more familiar with system

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

          I do not beleive in manual rating calculation for 20k members. No way.

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

            I meant only applying changes is manual, calculation is for sure automatic

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • Question D made me very sad. In the process of the competition, in order to avoid the single hash being hacked, I used double hash, which passed normally during the competition and took 1.6s. However, the retest after the competition was timed out due to the new data, but I passed all the samples after changing to single hash.
  • (In the single hash case, obviously, it's easy to create a special sample hack when you know the hash value.)
  • TLE-CODE:129383238
  • AC-CODE:129474392
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    So you used some form of hashing and then stored whatever data you needed on a set either way? At that point I'd use std::unordered_set...

    That being said I used a set<vector<int>> (because std::vector by default compares itself lexicographically) and didn't have any problems with time limits.

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

      "unorder_set" is really much faster, and I've never used "set<vector>" before, thanks for your advice, it's all new to me!

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

        Yes, std::unordered_set and std::unordered_map are two STL containers one should always keep in mind when dealing with algorithmics. They use hashing to provide constant time access! However, in a very pessimistic scenario one could potentially encounter data which has a lot of collisions and then the access would have linear complexity. But understandably -- that simply doesn't happen.

        One another note, std::vector does not have a built-in hashing function, so it's not compatible with the two aforementioned containers straight off the bat. That is why, during the round, I wondered if vectors are compatible with regular sets and that would be if their operator< was built-in. Just like you, I didn't know, but I opened cppreference.com and looked it up.

        Another bit of advice: your way of hashing (don't worry, it's pretty much the only popular way of hashing) by taking elements and multiplying them by a constant and then taking the remainder modulo another constant is rather slow, because the modulo operation is slow. So I wouldn't be surprised if using hashing is still slower than using the logarithmic std::set structure. In fact, looking at your newest submission, that is the case, since it still performs around 3 times slower than mine.

        Better luck with all this new knowledge next round!

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

awoo at least provide us, editorial.

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

Editorial much-awaited!!!!

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

I am new here, How much time taken by codeforces to update rating ?

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

when will we get the editorial of the problems?

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

Eagerly waiting for editorial and updated rating !!

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

    Someone please shoot me, I can't wait anymore.

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

when is editorial published?

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

Is this contest was rated for div 2 participent.

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

Because Till now there is no update in ratings.

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

Are there any chances of publishing the editorial?

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

me waiting for rating change and editorial

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

awoo: please post editorials. For rating changes take your time. but please atleast post editorial....

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

Dont understand why editorials are so slow. -1

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

    why editorials are so slow

    Bz it takes efforts ans time which you must have not ever gone through,

    orz awoo for such beautiful problems

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

      Yes, editorials take a lot of time to create, but I think they should be created before the contest is released.

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

I got +0 delta :")

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

For C, I understand that we would have to check for the lowerbound and lowerbound-1 as candidates for beating a defense of x, but why stop there? why not check lowerbound-2? or lowerbound-3? I get that they increase the cost with attacking against the dragon, but they do the job of reducing the cost while defending against an attack of y right? without this I'm not able to prove the greedy approach. any help will be appreciated ! Thanks!

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

    So assume we have $$$n$$$ knights with strengths $$$a_1 \leqslant a_2 \leqslant \cdots \leqslant a_n$$$. Now assume that the dragon has defense $$$x$$$ and attack $$$y$$$, and let's say that $$$i$$$ is such, that $$$a_i$$$ is the smallest of the strengths greater or equal to $$$x$$$. Now I will show why we only need to check $$$a_i$$$ and $$$a_{i-1}$$$ (if they exist).

    First, we do not have to check any $$$a_j$$$ for $$$j>i$$$ because using greater attack than necessary will not give us any advantage, but may cost us defense points, and thus gold. I think this is fairly straight forward.

    Second, we do not have to check any $$$a_j$$$ for $$$j<i-i$$$ because:
    Assume we use $$$a_j$$$. Then, we lose $$$d = a_{i-1} - a_j$$$ attack points, and gain $$$d$$$ defense points. However, since $$$a_{i-1} < x$$$, then it is guaranteed, that we must pay an additional $$$d$$$ gold coins to compensate for the attack. Notice now, that however much we had to compensate for the defense if we chose $$$a_{i-1}$$$, we will compensate at most $$$d$$$ less if we choose $$$a_j$$$. Thus, choosing a knight with strength other than $$$a_i$$$ or $$$a_{i-1}$$$ will never be beneficial.

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

      Thanks for this, and after I pondered upon the problem I was able to prove that for i<lower_bound-1 the cost of gold will remain equal to or more what we got when we chose lower_bound-1 mathematically.

      This can be proved as, say for a dragon's attack y, and defense x and a array of the knight's power h, we can have (x-h[i]) coins which will be needed to attack the dragon and (y-((∑h) — h[i])) coins to strengthen our defense, which would yield to a total coins of :

      x — h[i] + y — ∑h + h[i] = x + y — ∑h which will be constant for all values of i below the lower_bound — 1. now there might come a point where (y-((∑h) — h[i])) becomes negative, in that case it will be replaced with 0, hence it would be worse than lower_bound-1.

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

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

→ Reply
»
3 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