By pikmike, history, 7 months ago, translation, In English

Hello Codeforces!

On Apr/10/2020 17:35 (Moscow time) Educational Codeforces Round 85 (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 Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Hey Codeforces,

What a crazy month it’s been!

We hope you and your loved ones are taking care of one another and catching up on everything you didn’t have time for on your normal schedules.

We’ve temporarily closed our physical campus and moved our classes online. It’s not as bad as it sounds though — we’ve always known the future is digital, so we were already preparing for this moment. Either way, we’re back.

SPECIAL PRIZE FOR EDU ROUND 85

This digital transformation opens the door to some pretty awesome new opportunities that allow us to get closer to our community, no matter where in the world they are.

That’s why we have a special prize for the next Educational Round, a space in a course of your choice from our Computer Science or Data Science Programs. You’ll be able to study online with us for 1, 2 or 3 weeks under some of the best Data and Computer Scientists in the world, with all fees on us.

The prize will be for the top 3 users who have confirmed their desire to participate in this competition. To sign up for it, leave us your handle in the form below.

Enrollment in the course you will participate in will depend upon the availability of the course, as well as the prerequisites required for that course.

We hope this provides you with extra incentive for the round, and we’re looking forward to seeing some of you soon!

PARTICIPATE

FULL SCHOLARSHIPS FOR BACHELOR’S PROGRAM

On a different note, we’re happy to announce that we’re offering full scholarships for the most talented high school students who want to study in our Computer Science or Data Science Bachelor’s programs at our university.

At the moment, we have two types of scholarships available:

The Full Scholarship. For the best of the best — all tuition costs are covered by the university. Just show up and show us what you’ve got.

The Co-Creator Scholarship. For those who want to help us change education — all tuition costs are covered by the university, and in addition to your studies, you get to help the Harbour.Space team on their mission for 4 hours/day, getting valuable practical experience in the field and working in a team with some of the brightest young professionals in town.

Fill out the form below and we will contact you for the next steps!

FILL OUT FORM

Looking forward to seeing you kick some ass in the next Educational Round, and stay safe!

Best, Harbour.Space University

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 MiFaFaOvO 7 153
2 jiangly 7 195
3 amnesiac_dusk 7 244
4 risujiroh 7 290
5 bmerry 7 310

Congratulations to the best hackers:

Rank Competitor Hack Count
1 greencis 174:-53
2 Java 94:-8
3 hackVerly 55:-2
4 _BadLoser 55:-10
5 TheScrasse 40
2405 successful hacks and 1303 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Isabella_Vesterbury 0:02
B arknave 0:02
C Siberian 0:03
D Sevlll 0:16
E LJC00118 0:19
F IceWiz 0:31
G 9baka_Cirno 0:25

UPD: Editorial is out

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

»
7 months ago, # |
  Vote: I like it +529 Vote: I do not like it

.

»
7 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Wow!!! The last line of announcement is more likely to be said by a ROCK STAR than a university staff!!! /m/ LoL :))

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

»
7 months ago, # |
  Vote: I like it -66 Vote: I do not like it

I really hope there will be problems about COVID-19 and quarantine.

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

Before reload Oh there are No contests after it

After reload Oh What can I do with these contests

»
7 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I hope the problem statements will not be long

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

    why?

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

      Because long statements are more hard to understand, and it feels not right to have language difficulties in a programing contest.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    I hope some day people will stop writing stupid comments

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

»
7 months ago, # |
Rev. 4   Vote: I like it -47 Vote: I do not like it

I hope to become Expert in this contest!! If I succeed I will be Expert in just 7 months of coding!! I hope i can do it!

»
7 months ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

Hope the best for everyone <3

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

    It's probably been said a 100 times before: Hope is a dangerous thing. Hope can drive a man insane.

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

    I want the best for everyone and high rate for them , and they downvoted on my comment !!!!!!!!!!!!!!!!!!

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

      Have you considered the thought I want everyone low rating so it boosts my rating higher? :smirk:

»
7 months ago, # |
  Vote: I like it +108 Vote: I do not like it

»
7 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Hoping for no queueforces and strong pretests!

»
7 months ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

Hoping for strong pretests

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A lot of people enjoy some applications at home, but we enjoy with codeforces forever <3

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    There's no points for hacking in 12 hour hacking phase right? Although the person's solution you hacked would fall on the leaderboard. Am I right?

»
7 months ago, # |
  Vote: I like it -26 Vote: I do not like it

Is it Rated??

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    it says, it is rated for participants with rating lower than 2100. so for you, yes its rated.

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

the penalty for each incorrect submission is 10 minutes ?? What does that mean ? also can we hack even after the contest ? I'm a newbie so please explain :-)

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

    For the people who have the same number of problems solved the one with lesser penalty is higher up on the ranklist, penalty is the sum of the time at which each question is solved and also 10 minutes are added to the penalty for each wrong submission. Also the penalty for incorrect submissions is only added if you solve the question.

    After the contest if you feel that a particular solution from a user has passed the system tests but you think that you can provide a valid test case which that solution might fail than you can try that and if that solution fails that particular user will lose the points gained on that question.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your photo is so cute.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Desperately waiting for the contest

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Me: Codeforces is the savior from boredom. Meanwhile Codeforces : Sometimes it feels, I am the GOD...

»
7 months ago, # |
  Vote: I like it +7 Vote: I do not like it

good luck all))

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to see small queues, let us all first check our solutions on sample input, and then submit....☺☺☺, best of luck guys...

»
7 months ago, # |
Rev. 2   Vote: I like it -37 Vote: I do not like it

I've never seen a contest with so poor input examples

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

    How do you know tests are poor?

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

      I said it wrong. By pretests I actually meant the input examples.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Beautiful Problems, thanks pikmike

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! I'm a newbie.I started doing competitive programming in march'20. Since then I have given almost 10 contests on codeforces but everytime I am able to solve only the first question. How can I improve? Which path to follow?

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

    Solve tasks from here

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

      What's so great about it?

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

        There are a lot of good problems in greedy algorithms topic, which is very helpful in solving B tasks in CodeForces. And also graph problems are pretty good too. Basically, if you are a newbie in competative programming, this site is very helpful.
        Also this site is based on Antti Laaksonen's book, which is wonderful for a newbie

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

    In your level you can try to solve problem 'b' after the contest. And then when your can solve b problem , you can try 'c' ......

»
7 months ago, # |
  Vote: I like it -46 Vote: I do not like it

Hardest Div2 C I have ever seen.

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

    See 631 Div2 That was more harder than this one!

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

    I thought it was super hard for a long time before I realized the explosions only hurt the monster in one direction

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      Yeah, me too, but then it still was hard to implement, IMO.

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

        nah the implimentation was very easy look at my solution https://codeforces.com/contest/1334/submission/76178082

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

        76131257 Boilerplate and input aside, the actual solution has 10 lines.

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

          Hey nice solution, Can you explain me this why are you adding "best" to "cnt" arent we counting it twice? Thanks.

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

        try reading my code: 76135183 :)

        Define $$$f(n) = max(0,n)$$$. If start at $$$i$$$, answer $$$count_i$$$ would be

        $$$a_i + f(a_{i+1}-b_i) + f(a_{i+2}-b_{i+1}) + ... + f(a_n - b_{n-1}) + f(a_1 - b_n) + f(a_2-b_1) + ... + f(a_{i-1} -b_{i-2})$$$

        Replacing $$$a_i$$$ with $$$(a_i - f(a_i - b_{i-1}) + f(a_i-b_{i-1}))$$$, number of bullets needed would be ($$$(a_0,b_0) \equiv (a_n,b_n)$$$ )

        $$$count_i = (a_i - f(a_i - b_{i-1})) + \sum_1^n f(a_i-b_{i-1}) $$$

        So, to minimize the number, we compute min of first term (second term is a constant).

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

      What if the question was like "Explosions hurt both the adjacent monsters"? How will we solve it?

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

        You do chain reactions(explosions) in two half circles starting from the monster with least health, I guess?

»
7 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Any hints for C?

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

    just solve if we start from 1 and store result at each index. then traverse through i=2 to n so for each such i if we pick this as a stating point calculate the cost. it can be done in constant time and update the result to get global minimum. my_sub

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

    Its easy think :: suppose if we start killing from monster i , then cost of killing all monsters will be ai + (a[i+1]-b[i]) +(a[i+2]-b[i+1])+.... etc.;

    so to solve it we can maintain an array d[i]= max(0,a[i]-b[i-1]) {dont forget for i==1} , we should also find sum of whole d[i] array as S;

    through above info , now we can iterate over our array and check for every position as :

    ans= min(ans,S-d[i]+a[i]); in O(N) time;

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

    Thank you for your video solution. I can sleep comfortably....

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

    just above you

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

What's the logic for E? The fact that I couldn't even factorise D (10^15) stumped me. How to solve it without factorizing it? Or does the method draw the factors online from the queries... Very interesting problem to say the least. Thanks.

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

    You can factorize $$$D$$$ in $$$\mathcal{O}(\sqrt{D})$$$ :)

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

      You can loop upto 3*10^7? I thought you couldn't go beyond O(10^5-6) operations ;(

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

        You can go up to around 3*10^8 operations lmao.

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

        Wow, how did you even reach Candidate Master without knowing this?

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

          The inputs are generally O(10^5) and solutions are either O(n) or O(nlogn), neither of which pushes the boundaries. I don't really have a sense of how many seconds stuff takes, just in relation to what it generally is.

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

    nvm I misread your comment.

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

      Do we have to make graph or is there any other trick because most of people doesn't used much space?

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

        Optimal path is x -> gcd(x, y) -> y. Every path from x to gcd(x, y) by going down is valid, and every path going up from gcd(x, y) to y is valid. Answer can be calculated by multinomial coefficient.

»
7 months ago, # |
  Vote: I like it +50 Vote: I do not like it

The person in first place made his code obscure, that is a violation of the rules

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

    It says so right here in the rules:

    It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work.

    (copied from http://codeforces.com/blog/entry/4088)

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

    Obscured by using an algorithm template? :thinking:

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

got TLE on question A , in aprogram with O(n) time complexity , question A and B were easy but with strong test case

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

    Well if you got tle it means your program wasn't O(n)

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

      program of O(n) but i made one silly mistake , i did this :- int n; int A[n],B[n]; cin>>n; here some very big random value was taken by compiler as value of n was taken input in third line,but i was using it the value of n in second line too and my program mulfunctioned

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

    Read all of the input for a tc, even when you have conclude on the answer

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

      i found this error as but by then contest was over.And the fun fact is my program was giving error in third test case , i was checking for loops again and again but didn't checked the declaration part . I am so stupid .

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

    iamxlr8 A with strong test case?

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem F. Please, explain first testcase. I can't got 20. Sum of all p is 41. Max sum of b in a is 16. Why 20 in answer?

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

    4 1 3 3 7 8 7 9 10 7 11

    3 5 0 -2 5 3 6 7 8 2 4

»
7 months ago, # |
  Vote: I like it +80 Vote: I do not like it
  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it -19 Vote: I do not like it

    It's not incredible, it's just obscured.

    Each variable/function/class name is replaced with ReplacementFor_ (eg. the struct TREE becomes ReplacementFor_TREE). Numbers are decomposed in HEX+DEC-HEX form (eg. 0 becomes 0x113c+1395-0x16af). String/char are written with ASCII code (eg. "YES" becomes "\x59\x45\x53"). Moreover, every non-essential spacing, line-break or indentation is removed and then random line-breaks are put here and there in unusual places.

    He/She has made a simple script that obscures the code before submission so that it's harder to copy/paste but otherwise exactly identical to the original one.

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

      Code obfuscation is not allowed, for good reasons. This kind of code is more or less unhackable.

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

    In the last contest, his codes for A, B, C were of quite different styles. I suppose he did this to reduce suspicions this time.

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

      Yeah, I know) Because of this I decided to read his submissions

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

    Can you please tell just basics..what he has written. I was unable to understand

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

      I don't know, it's unreadable for me

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for D? I used OEIS Sequence but got WA on test 2.

  • »
    »
    7 months ago, # ^ |
    Rev. 6   Vote: I like it +15 Vote: I do not like it

    see (https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_algorithm)

    You can start creating a path like

    1 2 1 3 1 4...1 n 1
    

    Then, insert after the n, but before the last 1

    2 3 2 4 2 5...2 n
    

    and again, like recursive.

    The length of the path in every iteration is $$$2*(n-i)$$$ From that you can construct the interval (l,r)

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

    Analyze the cycle for n = 4 and n = 5. Once you do that it's easy to see that the cycle will consist of n blocks, i'th of them will be of size 2 * (n — x) (except for i = n, in that case the block will be just 1) and will look like this : {i,i+1,i,i+2,i,i+3,...}. From that it's easy to restore answer for given l,r.

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

    A general hint for any problem: If you don't know how to solve it, implement backtracking, maybe you notice a pattern.

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

    Wow I was also able to find this but WA on pretest2

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

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

What was test case 2 in D?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For C, I took a damage array and at each position I stored the difference(its zero if difference is negative), then I calculated the sum of all the elements in the damage array and also the element where I would start, which is the least possible a[i] value. I know I count a value twice, I even subtracted that from the final result. What was I doing wrong?

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

    Are you sure you always select the optimal start? It's optimal to select the one which has maximum diff[i] — a[i] (or equivalently minimum a[i] — diff[i]).

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

      $$$i$$$ with $$$min(a[i], b[i - 1])$$$ is the optimal start.

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

        got it! thanks

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

        Sorry, but I don't understand what you wrote.

        i with min(a[i],b[i−1]), doesn't make sense to me.

        The argument of min should be a scalar, it's not the min(iterable) function we're talking about.

        I guess you mean "i with min(min(a[i],b[i−1]))"

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me the complexity of Problem C?

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

Can you imagine the feeling of finding the mistake 2 minutes after the contest end?

I feel really great!

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

    Haha, I feel ya fam! Just keep going, we shall bleed red :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody Explain why this solution using binary search is wrong (Problem C )?? Submission link

»
7 months ago, # |
  Vote: I like it -19 Vote: I do not like it

This C is so hard lol while D is braindead.

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

Problem C: Idleness limit exceeded on test 3. Note: this is not TLE (time limit), but idleness limit.

Does anyone have any clue why these submissions failed with this weird error on G++ x64? I thought this might be because I don't flush the output ('\n' instead of endl), but the second one also failed:

(Edited for clarity).

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

    same problem occured with me too my solution was of O(N) still got TLE

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

      I edited the comment to be more clear. I don't have TLE, I have ILE, whatever this means. I've never seen this error before.

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

    Try removing those print()s and submit 76193796. It turned to TLE.

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

      Thanks a lot! It works without the debug output (76199653), just like my other submission during the contest. But I'm still surprised it didn't get TLE outright: maybe it's because the solution was unable to read all input before the time limit?

»
7 months ago, # |
  Vote: I like it +12 Vote: I do not like it

What is hack case in problem A?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I cannot wait for the editorial.. I solved C question in O(n) time . yet it shows TLE in Case 3. tried everything to remove it. Does it have better solution?? Can't think of any :( If yes, please reply to this:)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve F and G?

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

Is there anyone whose same solution for div2C get TLE in python but get accepted in c++ ?

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

    Codeforces reply to my query regarding the same issue: Unfortunately, this is the way things are on most programming contests: it is not guaranteed that each problem can be solved in every language

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why am I getting TLE on test case 3 for problem C? My solution — https://codeforces.com/contest/1334/submission/76172390

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

G: is it finding (s_i-t_i)^2 * (p(s_i)-t_i)^2 summation across all the substrings using fft. Or are there better ideas.

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

    you can use bitset :D

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

      does bitset actually pass? I didn't try it because I thought it would be $$$26n^2/64$$$

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

What is the usage of input l and r in problem D? I am not understanding what should be output :(

For example, the provided test case n = 3, l = 3, r = 6. The lexicographically minimum cycle is 1 -> 2 -> 1 -> 3 -> 2 -> 3 -> 1. How is this converted to an output of 1 3 2 3 ?

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

    You should take subsegment from l to r(inclusive) from sequence of the cycle(1,2,1,3,2,3,1)

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

      Ahhh, lol, it is used this way. Thanks!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anyone Please tell me why my logic in E is wrong — I thought that if we are given a range from l to r , then we should find a prime number which satisfy r>=l*prime , so that means prime = max prime smaller than or equal to r/l;

finally my answer will be minimum of (r-l*prime + 1 OR r-l)%mod . I applied that logic , but still got WA .

  • »
    »
    7 months ago, # ^ |
    Rev. 24   Vote: I like it 0 Vote: I do not like it

    I got my mistake — i forgot considering that each edge have different weight :-( . Miss read the problem . Also not all edge from 1 to N are connected.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

76190416 can anyone explain why in problem C , TLE occured in my code. I think the time complexity is O(N)

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

    try fast io .

    ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I think there is a mistake in the validator for problem C. In the problem it is stated that $$$1 \leq n \leq 300000$$$, but when I tried to hack, the validator states

Validator 'validator.exe' returns exit code 3 [FAIL Integer parameter [name=n] equals to 1, viola... range [2, 300000] (test case 1, stdin, line 2)]

Why are the bounds different?

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

    +1, WTF? I submitted a solution that failed on $$$n = 1$$$ and spent 12 minutes submitting a fix (because of something unrelated to the test case itself). Now I tried to hack myself and apparently I shouldn't have even bothered, because the test is not allowed?

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

    Unfortunately, this is true. We excluded the tests with $$$n = 1$$$ just before the contest to exclude unnecessary casework, but we forgot to update the statement :(

    We are sorry for that.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

76184731

76186776

and here are the cheaters of the day please take some action against such people

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

He's back. 76138708 , 76144561 , 76160631

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Going live on YouTube explaining A, B, C: https://youtu.be/FDbd_sYP7hM

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

    Great tutorials man. I like your style! I will watch if you have D-F tutorials :D

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

A — check that all p[i] >= c[i], p[i] >= p[i-1], c[i] >= c[i-1], and p[i] — p[i-1] >= c[i] — c[i-1].

B — sort the array and check every suffix.

C — The explosion of the last monster killed is always wasted; we can utilize all other explosions. The number of bullets saved by an explosion is equal to min(b[i], a[i+1]). The answer is the sum of a[i], minus the total number of bullets saved, plus the lowest number of bullets saved by any explosion.

D — The sequence is always of the form 1 2 1 3 1 4 ... 1 n (cycle for n — 1, with each element increased by 1 and the last element excluded) 1. Use simple recursion.

E — The shortest path is always from u to gcd(u, v) to v. To find the number of paths from a to b where b is a factor of a, consider the value x = a/b. Each time we make a move, we eliminate a single prime from x. The number of paths is therefore t!/p1!p2!...pn!, where t is the total number of prime factors (counting repetitions) in x, and p1, p2, and so on is the exponents of the individual prime factors. Multiply the answer for (u, gcd(u, v)) and (v, gcd(u, v)).

F — Use dynamic programming. f[i][j] represents the minimum cost if we consider the first i elements of array a, with j elements of array b already placed. Optimize the transitions with BIT, after noticing that each time, we simply add p[i] to an interval and take care of the case where a[i] is equal to an element of b.

G — Define f(x, y) = (x — y)^2(p[x] — y)^2. Observe that if x and y matches, f(x, y) = 0; otherwise, f(x, y) is always positive. Then we just have to compute sums of the values f(x, y) to determine if two strings match. Optimize the process with FFT after reversing one of the strings.

»
7 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Codeforces should give a note on C problem as it uses fast IO in CPP I had not used until my 6th submission. I am not new in CP as I knew about it but still, they must give a note so that we can check it once in our solution

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

    The problemstatement says there are up to 300000 monsters, each data on one line, each two integers.

    Fast IO is a really basic thing.

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I think I solved C, but reading TLE with python3 :(

First note that if monsters weren't in the cycle (but in a line) then there is only one solution and you have to shoot the first monster on the left and then the next monster that didn't die from explosion and so on …

Now with the cycle you can notice is that if you shoot a certain monster it breaks the cycle and the solution to the line is just shoot next monster that didn't die. Now which monster to shoot first then?

Naïve approach is to N^2 for each monster, shoot it and walk in a circle. But you can also prove that you don't need to solve again for the next monster you pick. Instead, if you solved for i-th monster, (i+1)-th monster will take sol[i+1] = sol[i] + min(a[i], b[i-1]) — min(a[i-1],b[i-2]), that is you're adding current a[i] (unless it didn't die from b[i-1] before) cause you're starting with it and subtracting a[i-1] cause that one dies off explosion (unless b[i-2] didn't kill it). b[i-1] and b[i-2] serve as upper bounds.

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Pretests for problem A are too weak..

»
7 months ago, # |
  Vote: I like it +12 Vote: I do not like it

In pretest , one testcase is missing and many codes are hacked for that particular testcase. (Those codes were Hacked Who didn't check "c(i)-c(i-1) <= p(i)-p(i-1)" this condition) Testcase : 1 2 4 1 5 3

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

    I'm confused because I failed pretest 2 when I didn't check c[i]-c[i-1] <= p[i]-p[i-1], and adding that line was the only change to get ac

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

      You got wrong answer because you didn't check if c[i] >c[i-1] then p[i] > p[i-1] but only checked independently that two array should be non decreasing so that's where you got wrong answer not because of c(i) - c(i-1) <= p(i) - p(i-1)

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Does Educational Codeforces Round has FST after hack?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I get struck in recent greedy questions, but struck less in the previous ones. Why? I can't get it? Please help me with ideas and tutorials how you approach greedy problems

»
7 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Today's $$$E$$$ was a bit tricky to prove.

Firstly, let's represent any number $$$x$$$ by a sequence $$$x_i$$$ where

$$$ x = \prod_{i = 1}^{n}{{p_i}^{x_i - 1}} $$$

where $$$p_i$$$ are all the $$$n$$$ primes from $$$1$$$ to $$$n$$$.

Now, observe that the weight of the edge from $$$x$$$ to $$$y$$$ will be

$$$ w(x, y) = \frac{\prod_{i = 1}^{n}{y_i}}{y_k} $$$

where $$$x = y \cdot p_k$$$. (Why ?)

Now, if we want to go from $$$u$$$ to $$$v$$$ in the graph, in each step we can either add $$$1$$$ to some $$$u_i$$$ or subtract $$$1$$$ from some $$$u_i$$$. As we want to find the shortest path, we will reduce $$$u_i$$$ by $$$1$$$ only if $$$u_i > v_i$$$ and add $$$1$$$ only if $$$u_i < v_i$$$. Also, its optimal to reduce all $$$u_i$$$ which are greater than $$$v_i$$$ before increasing any $$$u_i$$$ which are less than $$$v_i$$$. Both these statements can be proven.

Now, consider all $$$i$$$ having $$$u_i > v_i$$$. In what order would you reduce these? I claim that the order in which you reduce these doesn't matter.

Proof

Thus, the number of shortest paths is the number of ways to reduce all $$$u_i > v_i$$$ to $$$v_i$$$ multiplied by number of ways to increase all $$$u_i < v_i$$$ to $$$v_i$$$.

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

    For your proof block, there is a much simpler proof: if you go from u to w where w divides u and always step by removing a factor, the cost is just the number of factors of D that divide u but not w, regardless of the path.

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

      Wow. Short and beautiful

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

      Wow! Now, my proof looks stupid :(

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

        I was about to start trying something like your proof, but I decided that I'm too old to enjoy grinding through that sort of maths :-)

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

      I agree, If I am going from u to w and w divides u, then cost will be number of divisors of u — number of divisors of w.

      now the cost of going from u to v trhough gcd will be: c1 = cost(u --> gcd) + cost(gcd --> v) = number of divisors of u + number of divisors of v — 2 * number of divisors of gcd

      however, there is another possible path: u --> lcm --> v and its cost is: c2 = 2 * number of divisors of lcm — number of divisors of u — number of divisors of v

      why is c1 always better than c2? I was not able to prove this, and I submitted a solution based on that c1 is always smaller and it got accepted.

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

    Another proof: In any sequence of primes that got removed, we can swap adjacent primes in the sequence and the total weight of the sequence(path) doesn't change. Hence every sequence has same weight(since we can transform one sequence to other using adjacent swaps).

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +32 Vote: I do not like it
    Both these statements can be proven.

    That's what I'm always saying when I can't figure out any nice way to prove it :)

»
7 months ago, # |
  Vote: I like it -15 Vote: I do not like it

I wrote solution for C with O(N) time and O(1) memory in Python3 but got TLE on test 3. I tried to optimize input reading and other possible bad performance cases but still have TLE.

I suppose, that it can be some I\O mistake (like input() on empty stdin) but can't even imagine, where such mistake can be in so simple python code.

76161270

Is there someone with similar problem? (Or maybe someone can find mistake in my solution?)

PS. I even try to rewrite this code in C++ (76168690), but result is the same = TLE on test 3. I definitely miss something important, but I can’t understand what exactly

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

    Try to add these three strings in the beginning of main function:

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh my god, it works! Thank you! Well, I will take this fact about I\O functions into account in the next competitions

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

It is so frustrating when you get TLE bcz you use python. Today in Problem (C) it happened with me. I think it can be avoided, like most of the times in first 4 problems, what went wrong this time, constraint seemed fine for pypy but shows TLE.

»
7 months ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

I have found two plagiarism cases in the last contest(Educational Codeforces Round 85 (Rated for Div. 2)).

Here's the submission links: https://codeforces.com/contest/1334/submission/76179771 https://codeforces.com/contest/1334/submission/76175619

They did the same crime at previous round too (Codeforces Round #632 (Div. 2)). https://codeforces.com/contest/1333/submission/75904417 https://codeforces.com/contest/1333/submission/75907575

Ahnaf.Shahriar.Asif just copied the code from Shafin_Ahmed and added some extra lines to avoid plagiarism checkers.So we can call it plagiarismforces. Kids should get some education from it :p .

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

"Educational" is not in the process of solving problems, is in the hacking phase. Especially,in Problem A.

»
7 months ago, # |
  Vote: I like it +29 Vote: I do not like it

[submission:https://codeforces.com/contest/1334/submission/76137503]

I cannot understand any of DreamLolita submission. Someone please explain it?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +79 Vote: I do not like it

    MikeMirzayanov Please review this account DreamLolita and its submissions.

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

    Is he a robot?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +70 Vote: I do not like it

    I think it's a violation of Codeforces Contest Rules and the participant should be punished:

    4. It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work.
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In C if i declare input arrays as global array it does n't give TLE.else it gives tle. TLE: 76195191 76196229

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

    Because if you declare array locally space will be allocated for each testcase that will consume additional o(n) time.

    But mine got accepted even if i use local array .76145135

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

    for every test case, your array size is N, not n

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

      I didn't get what you want to say ?

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

        in the solve function, which is called every test case, it's allocate array with size N, which is 300007

        so the total is T*N = 150000 * 300007

        if it's only allocate the necessary size, which is n, it's guaranteed the total n in all test cases does not exceed 300000

        make it a global with size N is also ok, because only allocate it once, not every test case

»
7 months ago, # |
  Vote: I like it +53 Vote: I do not like it

Solution to problem G:

Similar to this problem, we define the distance between two strings A and B of length $$$n$$$ as follows:

$$$ \begin{aligned} \operatorname{dist}(A,B)=\sum\limits_{i=1}^{m} (A_i - B_i)^2 \cdot (p_{A_i}-B_i)^2 \end{aligned} $$$

Then we can see that when $$$A$$$ is $$$s$$$ and $$$B$$$ is a substring of $$$t$$$, $$$B$$$ is an occurrence of $$$A$$$ if and only if $$$\operatorname{dist}(A,B)=0$$$. However, in this problem, we want to know $$$\operatorname{dist}(s, t[j:j+|s|])$$$ for all $$$j$$$-s. To do this, we can expand the formula a little:

$$$ \begin{aligned} \operatorname{dist}(s,t[j:j+|s|])=\sum\limits_{i=1}^{m} \text{ } &t_{j+i}^4 - 2(s_i+p_{s_i}) t_{j+i}^3 + (s_i^2+4s_i p_{s_i} + p^2_{s_i}) t_{j+i}^2 \\ & - 2s_i p_{s_i} (s_i+p_{s_i}) t_{j+i} + s_i^2 p^2_{s_i} \end{aligned} $$$

Note that the first and last terms only have to do with on $$$j+i$$$ or $$$i$$$, so they can be easily calculated in $$$O(1)$$$ with prefix sums. The three terms in the middle are related to both $$$i$$$ and $$$j+i$$$, but if we reverse string $$$s$$$, it will only depend on $$$-i$$$ and $$$j+i$$$. To solve for all $$$j$$$-s, it turns out to be a typical FFT problem. So the whole task can be solved with 3 polynomial multiplications, which is fast enough to pass the time limit.

Don't forget to set $$$eps$$$ a little larger to avoid precision problems. My submission: 76170703

Complexity: $$$O(n\log n)$$$

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

    I had a slightly simpler (but most likely slower) FFT solution. My actual submission was dangerously close to the time limit, but I've since come up with a slight modification that's faster.

    For each letter c from 'a' to 'z' in turn, and for each position where S could be placed, count the number of positions where T contains c and S contains either c or p[c]. Sum these counts over all letters, and you can now tell whether each position is a match. For a given letter c, create a 0/1 array U where U[i]=1 where T[i]=c, and similar a 0/1 array V where V[i]=1 where S[|S|-1-i]=c or p[c]. Then to get the count you just convolve U with V via FFT. It's almost certainly slower than the solutions other people have described because it requires 26 convolutions, but should be fast enough.

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

    Here is a very simple bitset solution for G, that can pass with pragmas:76287369

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

Can someone please tell me why am I getting TLE on this code for E

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

    You could've pre-calculated inv modulo before queries.

»
7 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Problem A systests are garbage!!!!

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

    Yeah right! There was 1006 test case overall and none contained the case where the increase in plays is less than the increase in clears. I wonder how did they put the test cases

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

      i got hacked... still i m happy cz i got AC in C

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

      actually pretests did contain this case. I failed pretest 2 when i didn't verify that increase in clears <= increase in plays

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

        Well I got accepted in contest without checking for it there’s no magic going on.

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

          weird, I also failed on pretest 2 because of that

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

          Pretest had something like this

          5 2
          5 3
          

          which you passed because of checking

          if (p[i] != p[i - 1] && c[i] != c[i - 1]) { b = false; break; }

          But it fails for this case

          5 2
          6 4
          
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Yeah thank you I know that. But this does not justify the available system tests There’s only 4-5 cases to check and they couldn’t do so in 1006 tests. The number of hacked solutions for A speaks for itself.

»
7 months ago, # |
  Vote: I like it +17 Vote: I do not like it

C is educational, taught us the importance of fast IO

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

Can someone please check my code for problem C and tell why it is giving TLE, I think what I wrote is clearly O(n) 76183582

UPD : Used fastio and got it accepted after contest :(

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm really mad with myself :(

I got problem E wrong (WA on Test 22), because I didn't add these two lines to my code. I would have got 101st place as well. :( if (temp > 1) primes.add(temp);

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

    Basically, for D's such as 6 or 15, my prime list is {2} and {3} respectively, instead of {2,3} and {3,5} respectively.

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

    Lmao, I've also had issues with this! I wrote factorization several times, and I knew I had to add "if (temp > 1)" line, but I accidentally wrote "if (temp > 0)" instead, and it took me 20 minutes and 4 attempts to fix it xD

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

cf predictor is not working for me anyone has the same issue?

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

    I uninstalled it.

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

    From the last contest my cf predictor working again..today don't know , what will be happened. Bofore last 3 or 4 contest it was give me wrong prediction too.

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

      Actually it takes some time to refresh . If you do a submission and immediately check cf predictor it still predict till your last submission . Check after 2-3 minutes of submission , it will predict correctly.

»
7 months ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

Almost 1/6th of the submissions of A have been hacked and its not even been 2 hours yet.

nice.

»
7 months ago, # |
  Vote: I like it +33 Vote: I do not like it

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

What is the hack case for C ?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For a unsuccessful hack attempt how much score reduce ? please help anyone..

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

    No reduce, no gain.

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

      Then if i hack other solution , no effect on my score or gain rating + point ?

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

        No, also no gain. But the other one falls down in ranking, because one less solved. So you should hack the ones right in front of you in ranking.

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

        In this contest no fall and no gain . generally its +100 points for successful hack and -50 points for unsuccessful hack.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem C — "Circle of Monsters", is there any solution got accepted in java?. in practice, i tried the same as the top scorer "MiFaFaOvO" in java, but it says "Time limit Exceeded".

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Some tests for A 4 3 2 1 3 2 4 4 2 5 3 5 6 2 2 2 3 2 3 1 1 2 2 145 1

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How do i see div 2 ranking on standings page? It shows div1 participants as well, even if I untick 'show unofficial'

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't understand this line as a result GOT wa "Note that both of the statistics update at the same time (so if the player finishes the level successfully then the number of plays will increase at the same time as the number of clears)."

Still didn't get it.

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

For c problem, if any person has set Max to less than 3*10^17. U can hack c. Many persons asking me,so I shared. I hacked 5 in problem C.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1334/submission/76160649

This is my link to the code for C this is in o(n) still tle in 3rd case any reason for this like if any further optimization required ?

»
7 months ago, # |
  Vote: I like it +25 Vote: I do not like it

screencast of me trying to prove B and E for an hour

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

    nice

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

    Thanks!. i would like to confirm some this line on your problem C solution.

    if(a[i] > b[p]){ ans += a[i] — b[p]; a[i] = b[p]; }

    What I'm getting is that this is to find the blasts that doesn't instantly kill the i+1 monster so add a[i] — b[p] to ans as in the number of bullets it will take to kill after explosion. And after that we find the minimum of all a[i]..a[n] and add it to the ans as the starting point and we don't have to do anything anymore because the blasts will insta kill everything. Correct me if I'm wrong, and thanks for the video!

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

Is there any efficient way of doing the hacking? Some people hack like a killer machine (+20, +30). Can you just tell us if there is any faster way of doing that rather than seeing hundreds of codes?

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Why when I want to hack a problem a message is shown "Illegal contest ID"?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • If you click on "hack it" it will show you "illegal contest ID".
    • Follow this way,
    • Open his solution and click on '#' button (Right Corner) then there is button "hack it" click on that you can hack from there.
»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why my solution in C gets tle in test 3 https://codeforces.com/contest/1334/submission/76201302

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

    you should have used fast input output metods.

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

      scanf/printf??

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

        yes, or ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

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

        Yes scanf printf will work

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

          Yeah I got AC. But, why?? Like cin cout isn't working but scanf and printf working. Anyway, I am facing problem on finding solution on greedy problems. How do you guys approach? Any tutorial for beginning?

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

            You can start by solving B problems or questions whose rating is between 1200 to 1500 in codeforces and has a tag greedy. From that, you can easily learn about how greedy works.

          • »
            »
            »
            »
            »
            »