Educational Codeforces Round 85 [Rated for Div. 2]
By awoo, history, 5 years 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 Neon 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 jqdai0815 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 mosemAlanfgar 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 IQOver20 0:02
B arknave 0:02
C Siberian 0:03
D sevlll777 0:16
E LJC00118 0:19
F IceWiz 0:31
G Cirno_9baka 0:25

UPD: Editorial is out

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

Comments Comments (375)
| Write comment?
»
5 years ago, # |
  Vote: I like it +529 Vote: I do not like it

.

→ Reply
»
5 years 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 :))

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

→ Reply
»
5 years 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

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

I hope the problem statements will not be long

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

    why?

    → Reply
    • »
      »
      »
      5 years 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.

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

    I hope some day people will stop writing stupid comments

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

→ Reply
»
5 years 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!

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

Hope the best for everyone <3

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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 !!!!!!!!!!!!!!!!!!

    → Reply
    • »
      »
      »
      5 years 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:

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

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

Hoping for no queueforces and strong pretests!

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

Hoping for strong pretests

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

→ Reply
  • »
    »
    5 years 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?

    → Reply
»
5 years 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 :-)

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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...

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

good luck all))

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

.

→ Reply
»
5 years 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

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

    How do you know tests are poor?

    → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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' ......

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

Hardest Div2 C I have ever seen.

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

    See 631 Div2 That was more harder than this one!

    → Reply
  • »
    »
    5 years 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

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

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

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

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

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

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

        → Reply
      • »
        »
        »
        »
        5 years 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).

        → Reply
    • »
      »
      »
      5 years 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?

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

Video tutorial for C

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

Any hints for C?

→ Reply
  • »
    »
    5 years 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;

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

    just above you

    → Reply
»
5 years 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.

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

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

    → Reply
    • »
      »
      »
      5 years 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 ;(

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

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

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

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

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

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

    nvm I misread your comment.

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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://mirror.codeforces.com/blog/entry/4088)

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

    Obscured by using an algorithm template? :thinking:

    → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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)

    → Reply
    • »
      »
      »
      5 years 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

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

    iamxlr8 A with strong test case?

    → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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

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

Incredible code by DreamLolita

https://mirror.codeforces.com/contest/1334/submission/76152622

https://mirror.codeforces.com/contest/1334/submission/76137503

https://mirror.codeforces.com/contest/1334/submission/76111293

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
  • »
    »
    5 years 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.

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

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

      → Reply
  • »
    »
    5 years 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

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

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

      → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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)

    → Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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.

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

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

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

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

What was test case 2 in D?

→ Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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]).

    → Reply
    • »
      »
      »
      5 years 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.

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

Can anyone tell me the complexity of Problem C?

→ Reply
»
5 years 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!

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

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

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

This C is so hard lol while D is braindead.

→ Reply
»
5 years 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).

→ Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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.

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

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

    → Reply
    • »
      »
      »
      5 years 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?

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

What is hack case in problem A?

→ Reply
»
5 years 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:)

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

how to solve F and G?

→ Reply
»
5 years 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++ ?

→ Reply
  • »
    »
    5 years 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

    → Reply
»
5 years 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://mirror.codeforces.com/contest/1334/submission/76172390

→ Reply
»
5 years 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.

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

    you can use bitset :D

    → Reply
    • »
      »
      »
      5 years 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$$$

      → Reply
»
5 years 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 ?

→ Reply
  • »
    »
    5 years 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)

    → Reply
»
5 years 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)

→ Reply
  • »
    »
    5 years 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) ;

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

      it worked using this line struct {(){ios_base::Init i;ios_base::sync_with_stdio(0);cin.tie(0);}}_

      → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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?

    → Reply
  • »
    »
    5 years 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.

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

He's back. 76138708 , 76144561 , 76160631

→ Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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

    → Reply
»
5 years 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.

→ Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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.

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

Pretests for problem A are too weak..

→ Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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)

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

Does Educational Codeforces Round has FST after hack?

→ Reply
»
5 years 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

→ Reply
»
5 years 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$$$.

→ Reply
  • »
    »
    5 years 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.

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

      Wow. Short and beautiful

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

      Wow! Now, my proof looks stupid :(

      → Reply
      • »
        »
        »
        »
        5 years 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 :-)

        → Reply
    • »
      »
      »
      5 years 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.

      → Reply
  • »
    »
    5 years 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).

    → Reply
  • »
    »
    5 years 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 :)

    → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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);
    → Reply
»
5 years 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.

→ Reply
»
5 years 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://mirror.codeforces.com/contest/1334/submission/76179771 https://mirror.codeforces.com/contest/1334/submission/76175619

They did the same crime at previous round too (Codeforces Round #632 (Div. 2)). https://mirror.codeforces.com/contest/1333/submission/75904417 https://mirror.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 .

→ Reply
»
5 years 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.

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

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

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

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

    MikeMirzayanov Please review this account DreamLolita and its submissions.

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

    Is he a robot?

    → Reply
  • »
    »
    5 years 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.
    → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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

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

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

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

      I didn't get what you want to say ?

      → Reply
      • »
        »
        »
        »
        5 years 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

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

is this solution correct ?

→ Reply
»
5 years 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)$$$

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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

    → Reply
»
5 years 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

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

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

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

Problem A systests are garbage!!!!

→ Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
    • »
      »
      »
      5 years 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

      → Reply
      • »
        »
        »
        »
        5 years 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.

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

          weird, I also failed on pretest 2 because of that

          → Reply
        • »
          »
          »
          »
          »
          5 years 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
          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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.

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

C is educational, taught us the importance of fast IO

→ Reply
»
5 years 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 :(

→ Reply
»
5 years 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);

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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

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

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

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

    I uninstalled it.

    → Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years 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.

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

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

What is the hack case for C ?

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

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

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

    No reduce, no gain.

    → Reply
    • »
      »
      »
      5 years 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 ?

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years 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".

→ Reply
»
5 years 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

→ Reply
»
5 years 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'

→ Reply
»
5 years 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.

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

    give me a test case only if u interested.

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

https://mirror.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 ?

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

    Many codes written in c++ also got TLE due to large input/output. You can use Fast IO to avoid TLE!

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

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

→ Reply
»
5 years 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?

→ Reply
»
5 years 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"?

→ Reply
  • »
    »
    5 years 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.
    → Reply
»
5 years 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://mirror.codeforces.com/contest/1334/submission/76201302

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

    you should have used fast input output metods.

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

      scanf/printf??

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

        Yes scanf printf will work

        → Reply
        • »
          »
          »
          »
          »
          5 years 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?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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.

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

For B. Middle Class , can anyone tell me what's wrong with my code 76205050 ?

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

    It is a rounding issue because you use float for some reason. Use long long instead.

    PS: Edited

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

      whether I output "i" or "cn" it doesn't matter actually they both are same.

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

      could you please give some example where taking float will fail.

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

        float is 32 bit, it "overflows" the exact precision. Maybe double works better here. I am not sure how much bits double uses for the number, but float seems to have not enough.

        However, long long does not overflow in this problem since 64 bit.

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

    Its working if we use long long int but not for float(because of rounding issue).

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

If I hack my own solution, will I be out of the competition?

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

Here are my solutions to this contest in case anybody wants to refer them

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

Anyone who is able to explain me this code : https://mirror.codeforces.com/contest/1334/submission/76166237,

Gets a FREE COOKIE !!

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

10+ new testcases are added for problem C. Will they re-judge every solution over them once again?

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

I have some doubt in C, Just after reading the question I immediately wrote an equation, to kill Ith monster :

f(I) = min(f[I-1] + max(0,a[I] - b[I-1]), a[I])

I couldn't come up with any base case due to cycle. Can we make further progress in this direction?

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

    you can see my solution i did the exact same thing

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

can anyone know ... if i hack a solution will that test case be added to system tests for all solutions of that problem????

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

can anyone plz check the codes of this guy https://mirror.codeforces.com/profile/DreamLolita.

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

For Problem C

If the explosion kills the next monster, it explodes too"

How to solve if it didn't explode too??

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

    You need to shoot all monsters which are not killed otherwise. Every shoot decreases the points by one. Count the shots, you need to output them at the end.

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

Well, I just realized that I did an HUGE overkill in problem C using a sparse table and binary jumps to calculate the answer fixing each of the positions as the starting one. I definitely should start thinking of easier ways to get accepted submissions :P

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

Has editorial published?

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

    Editorial won't be published until the hacking phase is over

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

rank 1 div2 :3 How to hack it?

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

    I think this guy is a bot!! xD

    do have a look at his submissions for A,B,C.

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

      I don't know. I had not seen it before :(

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

      Bots can't solve problems (yet).

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

    He has obfuscated his code using a script so that his code would be pretty much unhackable. But that's against the codeforces rules. He did same thing in the last contest(#632) so he was debarred from the final standings.I hope he would be debarred this time too.

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

What are the hacks for problem B??

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

solved

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

    problem is with this statement " avg=(i+1)*x; " i and x are of type int so result will overflow. declare i and x as long long or cast RHS to long long as avg=(long long)(i+1)*x;

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

There's no testcase for B where the test has, 1000 tests and each n value is 10^5. Wasn't it obvious to include that?

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

    Remember, the sum of n cannot exceed 10^5

    That means, if you make n=10^5,then t=1 must hold.

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

    It's guaranteed that the total sum of n doesn't exceed 105.

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

As open hacking phase is finished, but still solutions of some users is in queue. Can someone explain what does it mean ?

Also When will the ratings be updated?

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

    All the solutions will be judged again including hacks. Then the final standings are released and after an hour or so you'll get your rating

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

Fastest System Testing I ever seen...

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

why is system testing so slow PS: I didn't participate in this contest but I want to stalk my friends's ratings.

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

The longest system test I have ever seen.

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

    It seems that sth went wrong with the website. All judgements have been paused.

    Just be patient, such things take time.

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

Why is System Testing taking too much time? Are the test cases are more than usual or is there any problem with Codeforces server?

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

    I think it is because that Problem A pretests are too weak. Many different main tests apend to system tests.

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

    I think, this is problem with Codeforces server. For last few hours Codeforces wasn`t avilable three times. Too much online during carantine

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

      Even before servers getting down it took 3 hours to judge submissions done till 57th minutes of the contest.

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

        It's because of A. There were a lot of hacks and it's highly likely that most of the hack cases are different. So like KisekiPurin2019 said, all these test cases get appended to the main test cases. So in all probability, there could be 200-300 main tests for A

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

when will we get to see the final standings?

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

Lets guess how much more time it will take to have the full testing. XD

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

Will we get final standing today??

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

Telegram Channel reports: "Due to a power outage, Codeforces and Polygon are unavailable now." Maybe some problems arose as a result of this? Codeforce I believe in you!

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

Maybe the system testing is affected by the COVID19 and it is in the home quarantine now.

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

Are their servers broken??...System testing is stuck at 88%...Why is it taking so long??!!

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

System testing got TLE at 88%

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

    Actually, an hour ago or something, codeforces was down. So that is RTE not TLE xD

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

      seems like the joke has gone above your head XD

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

Will the system testing continue? Or will the round be unrated?

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

    I don't think so. The round becomes unrated only if something happens during the contest. The contest is completed without any mishappenings.

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

Please, keep on system testing!

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

Can someone give strong small tests cases for F? I'm trying to upsolve but can't submit due to system testing.

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

When system testing gets TLE

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

)

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

The contest was rated but my ratings, didn't update; when will the tutorial be posted?

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

    Seems like codeforces is in some kind of server related trouble. System testing isn't finished yet. Once it finished, you will get your rating.

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

    Unfortunately, the testing of the round is not over yet.

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

Keep calm guys, hopefully before the next round starts the Edu(85) final result will be published.

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

who know why the rating does not change?it says that rated for div.2!

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

    System testing is somehow stopped due to some server issues. Once the round has been tested completely all the trusted participants will get their new ratings.

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

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

CF, please don’t die, we love you. Just complete system testing.

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

    I am becoming a master this round,wish it can continue.

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

      I was about to become expert.....then i got HACKED!!

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

      Finally become master gyh20,thank you codeforces!

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

Why codeforces is arranging day long system test in recent time?

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

I want to practice but it is still testing...!! OMG...

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

System Testing Sucks ):

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

All the contestant are in Home Quarantine. Only CF is the true friend at this moment.

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

12 hours hacking phase + 12 hours system testing

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

bmerry Can you explain your non-segtree solution to F?

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

    Sure. Let's call an element of a "special" if it gets output by the function. Let's say that $$$a_i = b_j$$$ is special. For any k such that $$$k < i$$$ and $$$b_j ≤ a_k < b_{j+1}$$$ we need to remove it; this is what cull counts. Note that each element which must be removed will be counted exactly once by this. Additionally, any non-special element with negative cost should be removed; negsum is a prefix sum of negative costs to help find these.

    Now we process $$$a$$$ backwards, maintaining some DP state. dp[idx] is the minimum cost for the suffix processed so far if the next special element must equal b[idx], ignoring elements of the suffix until the next occurrence of b[idx] (but including the costs from cull). If $$$a_i$$$ appears in $$$b$$$, say as $$$b_j$$$, then there are two possibilities to update $$$dp_j$$$: either $$$a_i$$$ is special, in which case we continue from the next occurrence of $$$b_{j+1}$$$ in $$$a$$$; or $$$a_i$$$ is not special, in which case we continue from the next occurrence of $$$b_j$$$ in $$$a$$$. Either way we need to adjust for the negative costs in between.

    Running time is $$$O(m + n\log m)$$$ (log factor from lower_bound), but I think it could actually be reduced to $$$O(m + n)$$$ since elements of $$$a$$$ are at most $$$n$$$ and hence one could built a looking table to do the lower_bound queries in O(1).

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

Bhai 100-200 jyaada lele par system testing krwa de....

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

How much more time will be taken for system testing of this round ! It's stuck at 88% and also editorial is not out yet !

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

Maybe for over 150 testcase of problem A then CF get TLE at 88% LOL

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

I love almost everything of Codeforces but their system testing is not up to the mark.It takes too much time to check all the submissions.They should improve their system testing time.

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

    This time server went down, causing some issues.

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

3 hours ago I saw system test was going 88% and I slept

now the percentage is still remain

what the heck is going on

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

Maybe is Um_nik who wants to prove that he is worth as much as 1000 cyans. As shown in the movie : https://www.youtube.com/watch?v=TXju58mzzaU

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

I have no idea if they can't or they don't want to prepare strong tests for during the contest . A lot of solutions got hacked or got WA (lot more than usual) in A,B,C (mostly A and B) which is just sad . I strongly hope the test data for the next contest will be strong :) but anyway I'd like to thank codeforces for making this situation (quarantine) less boring and more exciting

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

.

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

System testing 100%

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

    Few contest before it rolled back after reaching to 100%. How many of you remember that moment ???

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

Is the code after ddl counts? It seems the code which submitted after ddl counts in system test?

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

    It counts in system test not towards your contest standing or rating.

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

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

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

System tests are finished

sys

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

Did the whole world going to quarantine, motivated the coders to rise and participate more in coding to prove superiority in the field of quarantine lifestyle?

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

Codeforces servers right now:

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

the queue after every Educational round is frustrating, you guys need to figure this out I don't know maybe not allowing people to submit between the end of the round and the system-tests and maybe reduce the hacking phase to 6 hours instead of 12, it is really slow to rejudge all the submissions made during the last 12 hours on hundreds of tests...

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

Getting aged waiting for rating change O_o

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

awoo where is the top hackers for this round ?

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

    Unofficial top hackers (without unsuccessful hacks)
    greencis 174
    Java 94
    hackVerly 55
    _BadLoser 55
    TheScrasse 40
    yijan 36
    allexceed404 32
    dapingguo8 31
    vovanstrr 26
    harshchhatbar 26
    Amir_Reza 25
    surung9898 23
    rocks03 22
    LinkinPony 22
    nikolapesic2802 20
    Moustafa. 20

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

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

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

From implementation(A),greedy(B) and creative thinking(C),to graph theory(D),math(E),data structures(F) and string algorighms(G),this really is a perfect contest.Thanks!

→ Reply