By awoo, history, 5 weeks 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 kefaa2 6 212

Congratulations to the best hackers:

Rank Competitor Hack Count
1 DreamingLeaf 20:-4
2 tzc_wk 12:-5
3 ooooxxxx 9
4 SSerxhs 9:-1
5 fireblaze777 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 rasengans 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

»
5 weeks ago, # |
  Vote: I like it -39 Vote: I do not like it

Hoping this to be a Successful Contest unlike previous one, Good Luck to all the Participants & May you get Positive Delta, cheers :)

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

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

    Very bad words for the community

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

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

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

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
  • »
    »
    5 weeks 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.

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

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

    Sometimes maintaining silence also solves lot of problems.

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

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

it's on mondayyy when we have school :'(

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

Good luck to everyone!

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

»
5 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Is it rated?

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

thanhchauns2 go big or go bald...

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

»
5 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

So, Codeforces is back Bigger Better Stronger you must check out the blog How to grow in CP

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

Why people have time to dislike people's comments -_- , edited : OK

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

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

    Wishing you a very blessed Mid-Autumn Day!

    中秋节快乐

    顺便一提

    我不是中国人。

    😅

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

Just became pupil in the last contest I gave hopefully I can maintain that today :)

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

DELETED

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

Excited for this round! Hope I'll increase my rating today :)

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

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

It seems like I'm facing my greatest fear in my first contest.

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

usually comments start after the round ....

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

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

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

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

    same here. today i am able to understand problem D.

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

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

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

      there are different methods just go into google you will find stack overflow articles according to each language..

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

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

        AAA --> there are two pairs (0,1) and (1,2) AAAA --> there are three paris (0,1), (1,2), (2,3) for n --> there are n-1 pairs.

        2 3 4 --> (2-1) + (3-1) + (4-1) = 6 pairs!

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

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

          Ah i already have the answer , but thanks guys

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

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

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

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

Hope I can return to the candidate master.

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

Finally reaching to Pupil. Hopefully will reach the Specialist too soon.

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

i don't understand how 4700 people solved C.

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

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

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

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

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

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

      .

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

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

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

    just because i didn't added fast I/O i couldn't solve C :"(

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

    It's as simple as x+y — (sum of strength of all hero's) ,but since the values may over flow on addition, you need to do subtractions first. There will be two cases you just take min of both. Got accepted without fast I/O too.

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

    It was a just a implementation problem, it did not involved any particular algorithm. I and most people got stucked in choosing minimum condition else 7-8k submissions was not a big deal.

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

{deleted]

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

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

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

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

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

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

    In what cases the answer can exceed 1e18?

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

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

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

Do I deserve them? Thanks for so many downvotes! It`s make me feel happy.

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

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

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

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

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

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

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

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

Meaningless F with the easiest gf knowledge

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

    What is "gf"?

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

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

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

        Removed.

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

        I'm weak in GF, so you can ask alpha1022 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)$$$.

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

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

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

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

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

How to solve B?

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

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

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

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

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

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

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

      How did we derive the min (a-b-c-1)??

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

        if u see the minimal case 'b' no of a's will be utilised 'c' no of a's will be utilised so we will be left with a-b-c number of a's so the no of pairs that can be formed is (a-b-c-1)

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

    Simulate the problem. Try taking only 1 number of a,b,c. Then check for which value of m we can get "YES"... Then try with 2,3,4 numbers of a and rest if them are 1 b and 1 c.... Now check for different values of m.

    Note: If we have 1 1 1 and m = 20.. Is it possible to achieve something like this? So we can conclude that there must be some range or largest value of m for which we can't find valid string. Now try to find out the maximum range ( upper value). Similarly we can say we must have some lower value of m for which we can get valid string. So the problem requires you to find the range. If m lies in the range then you should print "YES" otherwise "NO"

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

It was my first time when I soved a problem immediately after a contest finished. What a weird feel...

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

terrific terrific terrific terrific terrific terrific terrific sample cases

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

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

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

How should I improve myself to solve problems like B?

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

    Solve B problems on a2oj ladders

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

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

    i don't have a good solution but when I get stuck on problems like that I generally open paint and try to visualize the information that's provided, and that really helps me out.

    edit: practice of similar questions through ladders helps for sure

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

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

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

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

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

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

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

    Find the minumum and maximum number of pairs you can make with given values of a,b,c and if m is lies between maximum and minimum then print YES otherwise NO.

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

How to solve E?

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

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

Nice problemset, specially loved problem C but I think it was a little imbalanced.

Personal opinion, there was a clear gap between problems C and D . If I were to set points for this set, I'd set:

500 - 750 - 1250 - 2000 - IDK - IDK
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think people messed up c ,which making a choice for minimum among lower bound and previous to it, other than that it was pretty straight-forward

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

      Phoenix_021, exactly!

      I made the same mistake first time around, did not consider the value left to the lower bound. Cost me ~10 minutes to debug and correct, but it was fun.

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

      Last line of problem C. I need to keep this in my mind. This silly mistake cost me very much I am going to kill myself.

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

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

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

    You can use next_permutation function with the base string of all opening and then all closing brackets for example n=3 ((())).

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

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

lol

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

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

C tests are bigger than 1e18? :|

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

    Yes.Otherwise it will be WA on 3.

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

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

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

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

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

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

https://codeforces.com/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

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

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

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

»
5 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

does any one coded A using swap function!!

code
»
5 weeks 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 (>﹏<)

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

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

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

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

I think it should be a hint in problem c to use fast input output but it was a good contest many thanks for problem setters for clear requirements!

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

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

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

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

    in the string abccc the chars at pos 3 and 4 make a pair and the chars at 4 and 5 make a pair

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

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

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

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

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

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

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

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

Can someone hack my C 129392269

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

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

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

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

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

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

          So you mean to change the pq comparator?

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

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

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

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

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

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

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

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

»
5 weeks 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.com/contest/1574/submission/129429122

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

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

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

        Nice idea, thanks!

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

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

    Can you please explain your dfs function?

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

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

»
5 weeks 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 principlebrute 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

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

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

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

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

Yayy I finally have a chance to become a pupil, also I want to ask if it's normal for someone to reach pupil after 18 contests?

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

Where is the official editorial...

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

How to solve D?

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

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

Can anyone please help me with a test case where my solution for B is failing? My solution: 129451176 My approach seems almost the same as mentioned in other comments but still it fails.

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

    For test case: 1 4 4 3

    Your code outputs "NO" while the correct output is "YES"

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

      Thanks! I also got WA on this test case, couldn't figure this case myself though.

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

nice problems, I love problem D.

»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    .

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

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

        Oh! Sorry I didn't knew about it. Thanks for correcting!

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

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

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

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

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

    same issue

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

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

      Oh I see. I didn't know that. Thanks a lot.

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

    Have a testing time after hacking. Please wait.

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

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

    • »
      »
      »
      5 weeks 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 :/

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

    Still, don't start yet.

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

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

My rating is not increased yet, why??

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

Have the ratings been published?

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

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

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

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

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

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

            Yeah, that will be automatic. Any idea by when can we expect the rating changes?

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

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

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

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

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

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

awoo at least provide us, editorial.

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

Editorial much-awaited!!!!

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

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

when will we get the editorial of the problems?

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

Eagerly waiting for editorial and updated rating !!

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

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

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

when is editorial published?

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

Is this contest was rated for div 2 participent.

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

Because Till now there is no update in ratings.

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

Are there any chances of publishing the editorial?

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

me waiting for rating change and editorial

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

for the B problems we check whether the given m ranges between minimum possible pairs and maximun possible pairs , but i dont get the intution behind it , can anyone explain it to me , and also does this approach work with similar kind of problems ?

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

    For me B was similar to A, it is slight variation of that here we can have let mx be the max amount of equal adjacent pairs now we can change the orderging to decrease the no of such pairs by 1 to mx-1 and so on... , similarly going till certain value after which you cannot decrease that value of mx , which will act as your minimum value.
    Yes it works with similar kind of problems .

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

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

Dont understand why editorials are so slow. -1

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

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

      Lol there have been editorials published in a few hours after the contest.

      orz awoo for such beautiful problems how about u solve them first before writing genric nonesense in the comment to get contribution or whatever

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

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

I got +0 delta :")

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

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

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

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

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