By awoo, history, 5 months ago, translation, In English

Hello Codeforces!

On Apr/29/2021 17:35 (Moscow time) Educational Codeforces Round 108 (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!

Once again, it is time for another exciting scholarship opportunity from Harbour.Space!

This time we have partnered with PhazeRo to open the door for an exciting career in technology for the most talented people in our network.

In partnership with PhazeRo, we are offering a full scholarship to study for a Master’s in Data Science at Harbour.Space while working as a Junior Data Scientist at PhazeRo!

Scholarship Requirements:

  • Bachelor's Degree
  • Professional fluency in English
  • Proficiency with data mining, mathematics, and statistical analysis.
  • Experience with Tableau, SQL, and programming languages (i.e., Python, R, Java)

Scholarship Highlights:

  1. Study in Europe’s most exciting tech cities
  2. Full tuition fee covered (€22,900)
  3. Competitive compensation for the internship at PhazeRo (€700 / month)
  4. Opportunity to join PhazeRo full-time after graduation

Codeforces and Harbour.Space

Some of the advantages of working at PhazeRo:

  • Possibility of a job upon graduation
  • Immerse into an International Company
  • Diversity Program
  • Professional Development
  • Be part of a company that is building the region's largest engineering team

We have previously partnered with other companies like OneRagtime, Hansgrohe, Coherra, and Remy Robotics to empower young talents around the world and help them boost their tech career.

We are always happy to see Codeforces members join the Harbour.Space family. Apply now to get a chance to learn from the best in the field and kickstart your career!

Keep in touch and follow us on LinkedIn for more scholarship opportunities. And follow us on Instagram to evidence student life, events, and success stories from our apprenticeship program students.

Good luck on your round, and see you next time!

Harbour.Space University

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 neal 6 186
2 vepifanov 6 188
3 Um_nik 6 251
4 Farhod_Farmon 5 65
5 noimi 5 76

Congratulations to the best hackers:

Rank Competitor Hack Count
1 zhoumofei 50:-50
2 mufeng.wei 24:-4
3 SSerxhs 22:-9
4 mahesh_dubey 13:-1
5 haminh0307 11:-5
463 successful hacks and 1684 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Geothermal 0:01
B turmax 0:02
C eecs 0:04
D abc864197532 0:04
E noimi 0:28
F rainboy 1:16

UPD: Editorial is out

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

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

Finally a contest after long break. Well, break is needed to set some things right.
Happy coding.

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

I hope I get that scolarship ...

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

I think preliminary rating change in educational rounds will be great.

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

    Wow! such big brain! and after every hack, rating changes of all 25,000 participants will be recalculated! No problem sir! I will put the word through to Mike

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

      Uhm no? Just do it twice. Once after the contest ends, and the second one when the hacking phase ends. Stop trying to act smart you idiot.

      PS — We have rating predictor extensions so prelim rating changes are not really needed.

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

        It would be helpful if you could share the extension you find good.

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

          Search cf-predictor on your favorite search engine.

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

            thanks.

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

            Why do you suppose that all existed search engines will redirect him to the same exact extension you have just mentioned?

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

        now, from this case, I'm not sure that having predictor extension with such difference is enough :)

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

9th rated contest of the month. Hail Codeforces!

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

A long break bruh, Codechef also postponed the Lunchtime.

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

    Lunchtime is Tomorrow. And Amazon is hiring via Lunchtime.

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

      Did anyone ever recieved any message from companies hiring through codechef ?

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

        Yup I did recieved ... and one of my friend landed an interview too

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

          Explain. What was your rank in cookoff and April long. what about your friend

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

            Not in april ...through jan;s long chanllege . We both were under 200 , I was in div.1 and he was in div 2

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

          Is this from cookoff or long challenge? because you know what long challenge means :)

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

            You can get selected from long too ... if there is no plag in your codes. Codechef do check for plag you know.

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

              and the hiring is internship or full time?

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

                They were hiring for internship n full time ... Time time I guess it is for coders with experience

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

              Lol Came for editorials, But stayed for the joker.

              This is his solution https://www.codechef.com/viewsolution/43852245

              this are other coders solutions https://www.codechef.com/viewsolution/43852488 https://www.codechef.com/viewsolution/43852283

              see how there all there codes contain roast, lund and other stuff.

              Seems like u got interviews even after cheating

              Please Flag this person People. I am 100% sure he has bought the solution over telegram. The user is arpit0891 https://www.codechef.com/viewsolution/43852283

              and i also have his linkedin.

              Please flag this user. he might have cheated in codeforces too

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

                Actually It was me who took his solutions and sold it on telegram . He gave me his password for some work.

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

                  Nope. You can check submission time on codechef. He submitted 40 minutes before the contest expired. Also i know this is a fake profile vj12. so do that someplace else. You sure have a lot of time arpit0891 to do this fake stuff and upvote your own comment from different profile.

                  But assuming you are genuine. This is still bad. Indulging in cheating is as bad as letting others cheat. Thanks for making it more easy for us. Regards

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

                  After this leak I stopped using that account . I made a newone and participate though that only .

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

                  That happened in January 2021,Feb 2021 and then March 2021, I hope all are leaks else they will be cheating.......

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

                  The account is closed as of now .

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

          And which division ? Like i can participate in div3 and get a lot better rank than div1

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

      I don't think we stand a chance though. cheaters will get interviews and you will get nothing. no reject mails even.

      so please take your time, read what i have written (https://discuss.codechef.com/t/are-cheaters-getting-interviews/88769/6) and give a f***k . cause the whole of admin team doesn't seem to give one

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

Another edu heh? Great.

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

i am very excited to participate the contest,wooooooo~

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

Almost every edu round I was "educated", but I still participate in every round...

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

"The penalty for each incorrect submission until the submission with a full solution is 10 minutes"

Does this mean that only time will be taken and there wont be a -50 or -100?

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

Today codeforces educational round. Tomorrow codechef lunchtime. Day after Tomorrow CodeJam Round 1C. Practice & Compete & Improve.

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

hope i remain expert after this contest :)

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

Time to start the vacations with an educational round. Excited!

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

I wish B/C not to be a observational shit like printing the array upto k and then upto n-k lol.

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

Hakcers will try to hack the solution in 12 hrs, while cheat busters will try to match the solutions in 12hrs.......

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

i hope i do best in the contest and happy coding to everyone

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

Have a great rating change

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

Nice contest!

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

Today's Problem Difficulty. Pls forgive me for not enlarging the image as I dont know how to do that.

Today's Problem Difficulty

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

    B and D is almost same difficulty level though

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

      B<A<C<<D<<<<<<E/F

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

        C took me an hour... D took me 10 mins...

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

          How did you do it? I did similar to longest palindromic substring. fixed pivot for both odd length subarray and even length subarray and then extended both sides.
          Time complexity: n^2

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

            Basically, yeah, what you did.

            For each position in the array i I tried generating an even length subarray and uneven length subarray that begins with that position as the middle or one of the middle elements. At each iteration add one more in each end so that the new subarray is continuous. Notice that moving through them like this maintains the position of the ones inside, so you just have to see what difference the new ends would make. O(n^2) time, O(n) memory.

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

              Is this a standard way of traversing substrings? or is this question is similar to any standard problem?

»
5 months ago, # |
  Vote: I like it -81 Vote: I do not like it

sometimes unexpected bruteforce works . Today it worked for problem C for me

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

    Can you wait till the end and not spoil solutions?

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

    Its not "unexpected" since its not hard to figure out why it doesn't tle

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

      yes and I coded only after I got n*root(n) bound for it :(. If we do only, take contribution from 1 to size of students in university for Ks. As, if the size of such universities is more than root(n), then their number will be less than root(n), so n*root(n) here and if the size of universities is less than root(n), then O(n) such universities can be there but k:1 to root(n) for such, so again n*root(n). So, overall complexity is n*root(n). The complexity might be less than this, but this was enough.

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

      He did TLE after the hacking phase with the additional tests

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

    i too did bruteforce in C. Got TLE. can you tell me where I went wrong? I can't think of any more optimisation. :/

    https://codeforces.com/contest/1519/submission/114607388

    link to my submission.

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

      Your brute force solution works in O(n^2) time as you try every n university for every possible k (which k==n), it won't pass since n^2 = 10^10 ~ 100 seconds. But if you observe the problem, you will see that after the number of people in university > k, you don't need to check it again as the number of teams will be 0. You can somehow remove that university from your checking list (effectively). This will improve the solution a lot. My submission: https://codeforces.com/contest/1519/submission/114578952

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

        Thanks a lot!

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

        But why doesn't n^2 work when time limit is 2 seconds. I have encountered this situation in some other problems as well. Sometimes, n^2 works for 2 seconds sometimes it doesn't. Is it because of the heavy calculations ?

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

          Whether n^2 works in 2 seconds or not depends upon the size of n. Although I would try to give a rough idea that what kind of solution can run in 2 seconds. In one seconds a normal loop would run near about 10^8 times in c++. It is only a rough estimation. In C the value of n was 2 * 10^5. If we square it, the result goes to 4 * 10^10. To run this solution at least, 400 seconds are required (again a rough estimation). So it definitly won't run in 2 seconds. Your assumptions that sometimes an n^2 solution runs in two seconds would be right when n is small. For n valued this large, an n^2 solution would never run, if the test cases are good.

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

      Probably You are getting TLE due to a very little mistake. Do check it out here. Link to Explanation

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

Speedforces

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

Does anyone with O(2*n^2) space got MLE in D?

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

    You will get MLE because final answer can be equal to 5*10^17 which needs to be stored in long long int. 2*5000*5000*8 contiguous allocation is not possible (In case you used DP).

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

      YA right but my O(N^2) python also getting MLE in 11 , I wonder why?

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

        Because Test 11 forces python into long arithmetic. If you will different algorithm to get rid of O(n**2) memory allocation you'll get TLE on 11 test. Then you'll need to do a little math, to get rid of excess of multiplication in your formula. Python often turn out to be pain here on codeforces :)

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

      Same happened with me. MLE

      AC

      cost me atleat 400 rank.

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

Probably there's like around 5 people right now writing "SPEEEED FORCES"(joking of course:)). I think this problem could have been avoided if E was more "div2-solvable", I mean around 60 people solved it and a good amount of them are red coders. There's no point I think in making A-D so standard(especially D) and E that hard.

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

    Pretty crazy variance. Solving A through D could either get you 60th place (with an implied rating of about 2250 according to cf-rating-predictor, which is orange), or as low as 2400th place (with an implied rating of about 1640, which is blue).

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

Really liked $$$E$$$. I wonder if everyone solved it the way I did.

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

    Interesting. I just used a known algorithm, which is given a graph cover it with paths of length 2 using a DFS. Seems most other people did it this way as well.

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

      Can you describe said algorithm? I wasn't aware of it's existence.

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

      Interesting! I didn't know about this algorithm.

      As I understand (after reading the Editorial to the task dorijanlendvaj posted), to apply this algorithm you transform the task in the following way: Each line through the origin will be a node. Each Point will be an edge and it connects the two lines to which it can be moved. Now we want to find edge-pairs which are connected to the same node. Those pairs should be mutually disjoint.

      While I was thinking about this problem I somehow was only thinking about the other way round: For me each point was a node. Two nodes are connected, if the corresponding points can be moved onto the same line through the origin. Now I tried to find the maximum amount of disjoint node-pairs connected by an edge. (This is the Line Graph of the first interpretation).

      So what I learned: Sometimes you should switch edges and nodes in your analysis/interpretation of a problem, maybe this will make the problem easier.

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

        If we consider the points as vertices and connect two vertices iff they'll lie on the same line passing through origin after shifting them. Then this problem will reduce to finding maximum matching in the graph, right? But that is too general. As in our graph let's say a is connected to b,c,d then a is a part of at most 2 cliques which is ({a,b,c,d}) or ({a,b},{a,c,d}) , or, ... etc .

        So by considering a line as a vertex, we have somehow used this property, right?

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

          Hey Zura,

          Theanks for pointing me to the maximum matching problem . That is exactly what should be solved in the second interpretation!

          Im not sure about your other comments though. Which property do you mean? I feel like we lose properties by looking at the linegraph, because the problem can't be solved with a simple DFS anymore.

          Maybe it's good to look at an example? e.g. {(1,2),(2,3),(3,4),(4,5),(5,6),(1,6)} (The first 5 points all can be moved on the main diagonal, and the 1st and 6th point can be moved on a common line) would have those two graphs in the corresponding interpretations:

          Image

          The possible solutions are the same in both cases. Could you explain again what you meant, possibly with the example (or an own example)?

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

            1st and 6th can't be moved on the same line as the first ones' slope would be (2+1)/1=3 and for 6th it is (1+1)/6=1/3.

            Other than that as I was pointing out 1,..,5 forms a clique.

            If 6th point were (2,5) and 7th were (3,8) then 1 is contained in two cliques 1,..,5 and 1,6,7. So by considering when we use a line as vertex we are basically accounting for this whole clique.

            I am unable to understand any further than that though, so waiting for the tutorial.

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

              Oops, i meant (1,6) instead of (6,1). Fixed it in my post.

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

        Why switch if you reduced problem to kuhn-munkres algorithm? You mean that you could do better with dp than O(n*m)?

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

          No, The property that I stated in the previous comment, at most 2 cliques, will help us as we have not utilized all the components of the problem. I don't know how to model this property, but these additional bits help us, and hence we can do better than Blossom's as that is for general graphs.

          Blossom's is for general graphs.

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

          Could you elaborate? Do you mean kuhn-munkres ? This sounds to be an algorithm for bipartite graphs, but the second interpretation doesn't yield a bipartite graph.

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

            Yep, you are right. My mistake.

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

              You can use the Blossom Algorithm though with $$$O(V^2E)$$$ or $$$O(\sqrt{V}E)$$$ with "the much more complicated algorithm of Micali and Vazirani".

              Guess we should stay with the first interpretation, or somehow use the information that the graph in the second interpretation is a line graph of some other graph (of the first interpretation).

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

                Couldn't get it when I read it first time, (an0nym0us_m0use, czhang2718) but now I think I understand :) Looks like it will really work greedily with every connected component as stated above: While doing DFS on a graph until you met visited vertex or deadend-vertex, then you come out of current vertex and connect all unconnected pairs of children (those that were left unconnected when you left them). And if there 1 left — you connect it to current vertex, else — you return in to it's parent as "unconnected" yet. Then parent repeat the process. And the number of unconnected points in answer will be the number of even-numbered-components.

                And that will work for any of two graphs. It's nice that they delayed editorial :)

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

                  Yes exactly that! I also did my submission 114692979 that way and it got accepted right away. The DFS-logic is in the "dfs" method and does exactly as you explain. :)

                  But what do you mean with "any of two graphs"?

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

B destroyed my confidence.

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

Could we solve D with $$$n$$$ times FFT? My $$$O(n^2 \log n)$$$ solution can't pass this TL :(

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

    Numbers were very large, how will you apply FFT?

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

      Just brute-force points of the reversed subarray $$$[L,R]$$$.

      For each $$$R \in [1,n]$$$, we calculate $$$C = A[0..R-1] * B[0..R-1]$$$, and $$$*$$$ presents convolution. Then $$$C[i-1]$$$ is the value of reversed subarray $$$[i - R + 1,R-1]$$$, it's easy to calculate the max contribution of all reversed subarray ended at $$$R-1$$$.

      The single round's time complexity is $$$O(n\log n)$$$ and the total is $$$O(n^2\log n)$$$. You can see my code here: 114607269

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

        Yes, you are right. I wanted to say that FFT will have precision issues while handling large numbers. The sum can go upto $$$10^{19}$$$ for subarrays. Such large values cannot be handled.

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

          I found that issue later xD. At first I even didn't consider precision,and long double has no hope to squeeze in this TL.

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

    FFT has a large constant factor. But also, for $$$n=5000$$$ I think it should be quite difficult to get any $$$n^2 \log{n}$$$ solution to pass, much less FFT.

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

    my solution didn't pass also. 114602456 . looking for a AC solution with FFT. or its impossible with such time limit !!

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

how to solve D

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

In E, I was able to group together the points that can be taken together in one move. But, how to make pairs? is it some sort of matching problem?

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

    I'm not sure what intended is, but we can do tree DP: think of each point as connecting two slopes. Then, create the DFS tree from this graph. Now, the question is what's the maximum number of 2-length paths we can partition this graph into. Then, for each subtree, let's greedily partition it. Let dp[x]=whether we need to reserve the edge going to x's parent. Then we can greedily match x's immediate children with DP value 1, and back edges leading up to x. dp[x]=[whether the count of such nodes is odd].

    Now, we can easily obtain our answer by keeping track of which edges refer to which original points. This is optimal because the number of extra/unused edges at the end is 0 or 1.

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

      This graph doesn't look like a tree.

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

        Yeah it isn't necessarily a tree- we construct a DFS tree out of it.

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

D was so easy compared to C

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

    can you please explain your approach

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

      There are n^2 subarrays, get answer for all of them and print the max

      Probably the best way to iterate over them is by iterating all possible centers

      Use the fact that you can calculate answer for A[0:10000] for O(1) if you know the answer for A[1:9999]

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

    Pls don't make me feel stupid :(

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

      Maybe you need to work on your dynamic programming skill a bit? I personally just thought dynamic programming initially and then realised I can do without the extra memory.

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

        Can you tell me how to do D without extra memory?

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

          In D, i think the best solution is iterating over centers of subarrays and calculating the difference between new and old values. It takes O(n^2) time and O(n) space complexity (just a and b arrays). My submission is here: 114594546

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

    D is simple implementation once you see how the dp works. But getting that idea is not so simple.

    C on the other hand is the opposite. The idea is simple to see, but the implementation has some pitfalls.

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

      The opposite for me

      Took me quite a while to get the idea what to do in C to avoid time limit

      And instant idea in D

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

Nice problems

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

Is Question E a MCBM problem? I was thinking of modelling both of the possible moves as a fraction x/y then try to do matching between points with the one of the same fractions. However, this is potentially O(n^2) so I am not sure if there is a way to optimize it.

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

memory limit was too tight in problem D

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

    Am I the only one who did it in O(n) space?

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

      no

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

      Yeah, you can do it O(n) space and O(n^2) time complexity. Iterate over all points as pivots and iterate over length of subarray to reverse. Then do the same for all gaps i.e. even length subarrays.

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

    No additional memory other than the original array was needed actually.

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

      well , my O(n^2 * 2) DP didn't pass , but I realized after the contest was over that I can change it to only n^2 space , and i coded it and got AC. welp , thats my rating going.

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

      could you please elaborate on how to do this. I used two addition arrays of size $$$n$$$ to store answer for subarrays of size $$$i-2$$$ and $$$i-1$$$. This is because we need to have answer for subarray of size $$$i-2$$$ if we are going to calculate answer for subarray of size $$$i$$$.

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

Any cool observation for C? Couldn't get it faster than O(n^2*log(n)) 114611449

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

    If you observe carefully that was not O(n^2logn) but O(n log n). See there were only n students so they might get divided into n groups but total student will remain n only. You can relate it to graph ques where we mark a note visited and when we come again we found at that node is already visited. We might come again and again to a same node but overall time complexity remains O(n) only. Same way, we might iterate all the n groups but total student remain n only.

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

I used n^2 Space to solve D but it exceeded memory limit. I still wonder how it is possible.

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

    try to replace the vector with an array

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

    In D, any n^2 memory takes 200 MB in worst case. So even if you had 2 such types of memory, it will MLE.

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

    My O(n^2) Space and time dp passes all TC. Video explanation

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

      I will be thankful if someone makes video editorial of E. Why everyone posts editorial of problems solved by 1000's of people.

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

        Actually, You can see I 've just posted for only Problem D for this contest, and I'm trying to post for video explanation of problem E too asap.

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

        Because there 8000 people interested in A and B, 15000-19000 in C and D, and only then there 2000 who solved D and interested in E, and 50 interested in F :)

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

Hey, need a lil help here :3 My JAVA submission for B gives Runtime Error in test 1 verdict, but it seems to work fine on my system. I really can't figure out what's wrong. Would be grateful if anyone can help!

Here's the submission : 114586245

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

How to solve Problem C. I ran into TLE. This is my solution using Heap. I also tried using sorting the vectors, which too ran into TLE. Kindly help

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

Hi, Can someone help me with my submission for problem C . I am getting a run time error for the first test-case which is already given but running that test-case on my laptop is not giving any error and the output is also correct . The link to my submission My_Submission. Thanks in advance.

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

Problem D was super not Python friendly. This is the shit I did to get accepted 114611359.

The reason for the TLEs in Python is basically that PyPy2 and PyPy3 is only 32 bit on Windows. So on Problem D you are forced to use big integers everywhere, which is super super slow. However in the latest update of PyPy (version 7.3.4), PyPy switched to supporting 64 bit on Windows.

MikeMirzayanov Would it be possible to update the PyPy version (to version 7.3.4)? All of these issues with big integers would go away, and it would make PyPy a lot more useable and beginner friendly.

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

In question C, the description was ambiguous, there were not exactly 'n' universities always, rather nothing should've been mentioned about universities!:)

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

    Why not? They never said each university had a competetive programmer. It is possible for a university to have no competetive programmers.

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

      Ohh..I got it now....thanks for clarifying.....I forgot this statement of yours!:)

»
5 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Hello everyone, this was my first ever contest on any coding platform , and I was able to solve just 4 questions and got around 1500 rank. Can anyone tell me whether it is considered good performance or not? Also , what should I do in order to improve? Thanks a lot.

»
5 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Why was B so easy? Usually B is twice as good as A(even for an edu round). We can basically induct on $$$m+n$$$ and B is solved.

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

    That's once you guess what the answer is. And then you can defer the proof until after the contest.

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

If i solved 4 problems, should i solve 5th problem . For improvement i should solve one problem more than what i solved during contest but mostly red coders have solve problem E and my real rating is well below red so i might spend 1 to 2 days up-solving it.

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

    why downvote ? Just asking for suggestion :( You can downvote this one also but please tell

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

Question regarding Problem B: How can we prove that no matter which path we take it will always result in the same cost of N * M — 1 ?

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

    We can prove by induction that regardless of the path you chose, the cost at any point (x,y) along that path will be x*y-1.

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

    The path can be described by a sequence of R (right) and D (down).
    It's easy to prove that swapping a R and a D doesn't change the answer.
    You can reach any sequence, starting from a fixed sequence (e. g. RR...RRDD...DD), with a finite number of swaps.

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

    You can visualize it by realizing that at each point $$$(x,y)$$$ of the path the cost is equal to the area of the rectangle with a diagonal $$$(1,1) -(x,y)$$$ with cell $$$(1,1)$$$ removed. When you move right you add a column to the rectangle, and when you move down you add a row.

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

    You can also prove it like this:

    Consider the conservative field $$$\vec{E}=y\hat{i} + x\hat{j}$$$. Observe that the value required is just the work function. As potential function is $$$U = xy$$$, work done will always be $$$nm - 1$$$.

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

      A stupid question — are you applying continuous calculus to a discrete problem?

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

        Yes. I proved that work done will be same regardless of how you move the particle from $$$(1, 1)$$$ to $$$(n, m)$$$. The problem just asks to consider specific ways to displace the particle, using only the vectors $$$(1, 0)$$$ and $$$(0, 1)$$$.

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

          Ah, got it. We are just restricted to moving along a broken line with horizontal and vertical segments.

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

Can someone please explain the proof why for problem B, the answer is k==(n*m-1)?

I solved with DP and got surprised to see it could be formulated.

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

    Consider any RD from (x, y) to (x+1, y+1), you can see that changing the sequence to DR does not change the cost, and thus any sequence will have the same cost.

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

    Exactly n*m-1 burles needed, for all possible ways. That's why if k is n*m-1 then k is valid. Otherwise k can not be obtained.

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

    Prove by induction. You can assume the proposition true for m×n grid , and establish for (m+1)×n grid.

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

      Can you provide the inductive proof please?

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

        Inductive hypothesis: path value is x×y-1 for any grid such that x <= m && y <= n.

        We try to prove the same for (m+1)×n grid.

        Suppose you are at m×j cell and take downturn to (m+1)th row.

        You need (n-j) more right turns to reach (m+1)×n cell.

        Total : (m×j-1) + j + (m+1)×(n-j) = (m+1)×n-1 , which was to be proved.

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

    I did some few examples on paper and found out that the answer is unique, for every n, m. I couldn't find the formula so just calculated it step by step and checked the cost if it equals k.

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

      I calculated the way going through two opposite corners (algebra), got that both were $$$n \cdot m - 1$$$, and then didn't bother trying to prove it.

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

    Proof for problem B that answer is k==(n*m-1).

    Proof
  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it +56 Vote: I do not like it

    Another possible proof:

    Instead of it costing $$$x$$$ or $$$y$$$ burles, say that it costs $$$x+y$$$ burles and then you get $$$y$$$ or $$$x$$$ burles back.

    In each move, $$$x+y$$$ increases by 1 so the total sum of $$$x+y$$$ is $$$\frac{(n+m-1)(n+m)}{2}-1$$$, the total amount of burles you get back with the increase of $$$x$$$ is $$$\frac{n(n-1)}{2}$$$(you do one with each $$$x$$$ from $$$1$$$ to $$$n-1$$$) and the total amount of burles you get back with the increase of $$$y$$$ is $$$\frac{m(m-1)}{2}$$$(you do one with each $$$y$$$ from $$$1$$$ to $$$m-1$$$). In total the cost is $$$\frac{(n+m-1)(n+m)}{2}-1-\frac{n(n-1)}{2}-\frac{m(m-1)}{2}=nm-1$$$.

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

      oh,nice. I made it hard for myself.

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

      You are using wrong currency.

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

      Consider an arbitrary path from $$$(1, 1)$$$ to $$$(n, m)$$$.

      We claim that at any point $$$(x, y)$$$ along that path the cost will be $$$x \cdot y-1$$$.

      Proof by induction.

      At the start the cost is $$$1 \cdot 1 - 1 = 0$$$ — the condition holds.

      The induction step.

      Assume that the statement is true at a point $$$(x, y)$$$ along the path. The next point in the path is either $$$(x,y+1)$$$ or $$$(x+1, y)$$$.

      In the first case the cost will be $$$x \cdot y-1 + x = x \cdot (y+1) - 1$$$. Similarly, in the second case the cost will be $$$x \cdot y-1 + y = (x + 1) \cdot y - 1$$$.

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

What is the meaning of the Problem B title?

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

    I guess constraints make this ques harder. If it were around 1e9, all would have tried to thought of general formula.

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

Very happy to see some good ad-hocs like ABCD.

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

Screencast with commentary aka Um_nik staring at problem F for 40 minutes in silence

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

My python submission for problem C is getting TLE on Tc 5, I tried implementing it as the same way other people implemented and got AC. MY SUBMISSION FOR PROB C

please help. Thanks in advance.

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

    There are a few smart observations that could help you pass it:

    • We are interested only in the sum so maintaining just the sum of let's say 1st p elements would help.
    • We can limit the search to the maximum size of students in a particular group

    Also, I have observed iterating through numbers (for i in range(n)) is generally faster than iterating through the keys (for i in dict). Also you could try with fast I/O sometimes that solves TLE.

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

    Your code takes O($$$n^2$$$) time because of

    for ii in d:
      for k in range(1,n+1):
    

    If you change it to

    for ii in d:
      for k in range(1,len(d[ii])+1):
    

    then the loops run in O($$$n$$$) time 114686648.

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

I think the official generator for task E is broken since none of the 26 pretests have n > 1e5! Therefore, It'd be best if the authors cut the limit on n to 1e5 and rejudge all the solutions to respect the spirit of competition. awoo

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

    Knowing that there were 26 pretests for E find it strange as well, it's common sense that the only fair option is to reduce n to 1e5 and rejudge everything, if not including max tests in pretests was intentional then the authors are sadistic and should die a painful and slow death.

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

    Nah, I don't think that's necessary. I admit I made a mistake while generating tests, but you aren't really promised the strongest tests anywhere. The constraints are in sync with what the validator checks, so I see no issue.

    Sorry that you got caught by it, be careful the next time.

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

      Fully agree. A lot of people here are interchanging pre-tests with system tests for some reason...

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

      I think you have to be carefull next time

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

This contest was actually educational for me. I learned 2 things: 1) Never trust the ceil function. 2) Don't write iterative dp like it's recursion, always check the order of computations... goddammit D.

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

    and if you want to write a ceil function that doesn't need to convert its arguments into doubles, you can write something like this:

    int ceil(int x, int y){
        return (x+y-1)/y;
    }
    
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh yeah, that's a smart expression. I always did this subconsciously when dividing by 2 (e.g. (x+y+1)/2 ) but it never crossed my mind that it could be generalized. Perhaps ceil isn't as untrustworthy as I first thought, thanks for the tip!

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

I solved problem b but not able to solve a :(

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

Hey! In C problem, I was using comparator on a vector of vectors. When I used '>=' in the comparator it gave a runtime error while using only '>' gave the 'Accepted' verdict.

Runtime code : https://pastebin.com/WQwxwrCd

Working code : https://pastebin.com/sf1e1BTk

Both codes are same except on the 18th line where there is difference of '>' and '>=' in the respective codes. Can anyone explain why this happens?

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

How to get rid of MLE in problem B using Dp can anyone please help? Here is my submission 114621015

Thanks in advance :)

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

    B can be solved using 2D dp. Store true/false in DP states.
    See this sub : https://codeforces.com/contest/1519/submission/114557667

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

      How storing 2 states will cover all possible states there might be different k values for different states right? could you elaborate, please...

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

        The cost of reaching {x,y} from any allowed path is the same.

        So its reducible to a new subproblem starting from {x,y} to reach {N,M} with exactly
        K - (x + y) burles

        If dp[x][y] is false, it means its not possible to reach {N,M} with exactly
        K - (x + y) burles

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

      B is math not dp ;-;

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

        Yes its math.

        But can be solved using DP too. I agree DP is an overkill lol.

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

          if (k == (m-1 + m*(n-1))) cout<<"YES\n"; else cout<<"NO\n"; There, that gets you an AC.

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

            Can you explain why?

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

              Sure
              First thing to notice is, no matter what path you select, the number of D's (down) and number of R's (right) remain the same, just the ordering is different. This hints that there's only 1 score possible. To be completely sure, you can do some dry run for some rectangle grids (square would be too easy)
              Now, once you're convinced that there's only 1 answer possible, you look at the easiest way of calculating it; Move horizontally till the last column and move down till the last row. To move m columns horizontally from 1st row, you incur a cost of (m-1). Now to go down n rows from m'th column, you incur a cost of m*(n-1). Their sum is the answer. Hope this helps.

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

    You have used long long int as the data type for the dp array. You could have avoided the MLE if you had used 16bit-int or 8bit-int as the data type. You can check it out in my submission 114563484.

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

speedforces :P

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

Can anybody tell how to optimize my C's solution further ? 114617580

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

    There can be n lists of size == 1, but you'd still check every of them for i = [2..n]. That would be O(n^2) ~ 10^10. Kick them off from map when their len == i, and stop cycle when i > max_len(m[i]) (map should be empty at this time). But first kick those with len <=2.

»
5 months ago, # |
  Vote: I like it -50 Vote: I do not like it

I made a little meme:

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

Where is the Editorial ??

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

I guess, the test cases were weak for problem C. Sorting the vector of vectors based on their size and stopping once the size becomes less than K can get your solution accepted.

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

    114627098 what is the problem in my code then?

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

    There's an explanation for that actually. If you iterate from each $$$k$$$ from $$$1$$$ to $$$n$$$, you will find at most $$$\frac{n}{k}$$$ vectors that have size at least $$$k$$$.

    That leads to a known sum which is $$$n logn$$$.

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

      There is a trick to even get it down to O(n).

          out = []
          for k in range(1, n + 1):
              teams = [t for t in teams if len(members[t]) >= k]
              score = 0
              for t in teams:
                  score += prefix_sum[t][k * (len(members[t]) // k)]
              out.append(score)
      

      This part will run in O(n) time, not O(n log n). This is because a team with $$$m$$$ members will be filtered out of teams after $$$m$$$ iterations. And since the sum of the sizes of all teams are $$$n$$$, the code runs in O(n) time.

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

        I did like that in my ugly code, its good to know that it is O(n), i thought it would be something like N*sqrt(N).

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

        Nice trick. Wouldn't it be "cheaper" to kick them from the set, instead of generating new list all the time?

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

    This is probably the intended solution and it's $$$O(nlogn)$$$. It's not about the test cases, it is indeed $$$O(n)$$$ except sorting. Because, if done so, we will consider a university with size $$$s$$$ in only $$$s$$$ different $$$k$$$'s. Since the sum of all $$$s$$$'s is $$$n$$$, complexity is $$$O(nlogn+n)$$$, that is, $$$O(nlogn)$$$.

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

Please explain how to make problem C using Two points method, i made it using Prefix sums.

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

    I guess you'll need prefix sums anyway. From now on, assume that the universities are sorted in non-decreasing order by size. The thing with the "two pointers" must be that when you encounter a university with size smaller than current $$$k$$$, you have to move your "left pointer" (you shouldn't evaluate universities on the left of the left pointer because their size are smaller than $$$k$$$). As with the right pointer, it just doesn't exist.

    P.S. : It is my understanding of this tag.

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

How to solve D?

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

    Maintain a 2D DP array. Here, $$$dp[i][j]$$$ means the value we'll get in interval $$$[i,j]$$$ if we reverse the interval $$$[i,j]$$$. It is not hard to see that $$$dp[i][j] = dp[i+1][j-1] + a[i]*b[j] + a[j]*b[i]$$$ because when we reverse an interval $$$[i,j]$$$ , interval $$$[i+1,j-1]$$$ gets reversed and we swap $$$a[i]$$$ and $$$a[j]$$$. Now, maintain a prefix and a suffix array $$$pre$$$ and $$$suf$$$. Here, $$$pre[i]$$$ denotes the answer for prefix $$$[1,i]$$$ without any reversing and $$$suf[i]$$$ denotes the answer for suffix $$$[i,n]$$$ without any reversing. The answer is maximum of $$$pre[i-1] + dp[i][j] + suf[j+1]$$$ for all intervals $$$[i,j]$$$.

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

      thank yo so very much....I understood..you explained it really well

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

      I think there is typo it should be dp[i][j]=dp[i+1][j-1]+a[i]*b[j]+a[j]*b[i]

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

        Sorry, you're right. Fixed that.

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

Can someone explain why the first submission gets TLE while the second one gets accepted?

114581044 114630025

Only difference is how I sort a vector.

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

    In the first submission, you have used a lambda expression to sort the vector. The problem here is that you have 'captured' the variables using "=" which is slower. I replaced that with "&" and uncommented the "#define int ll" line. The code gets AC after this.

    114639136

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

    Capturing variable using = is by value which means you copy a new vector every time the sort function compares two numbers. Use & to capture by reference.

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

How to solve C ? I solved using factorization in O(nsqrt(n)) but it seems lot of people have solved in some different way.

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

    idk

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

    You can solve problem C using Prefix Sums . Divide all the students by their corresponding cities . For each city , if number of students in my current city is $$${m}$$$ and size of teams is $$${k}$$$ , then $$${m\%k}$$$ lowest skilled students will be not be in any team .$$${\newline}$$$ So for each city , sort the array of students ,calculate the prefix sums , and then iterate over the size of teams ($$${1}$$$ to $$${m}$$$ ) , take sum of skills of all students who can be teamed up ( $$${pref[m]-pref[m\%i]}$$$ ) and add to the final answer array .
    Hope it helped !
    Submission Link : https://codeforces.com/contest/1519/submission/114643205

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

      So, let say there are $$$n$$$ university and each university has only $$$1$$$ student then don't you think your solution will be $$$O(n^2)$$$? I was trying to do same but this case stuck in my mind

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

        The the number of students is $$${n}$$$ , the only thing I did is distribute those $$${n}$$$ students across the cities . There are two loops but the sum of total operations of the inner loop is still $$${\mathcal{O}(n)}$$$ (because I am iterating over the students and only n students exist across all the cities ) .

        In your example case , the inner loop will perform $$${\mathcal{O}(1)}$$$ operation for each outer loop iteration , summing upto $$${\mathcal{O}(n)}$$$ . (Also you'll need to account for sorting , which takes $$${\mathcal{O}(nlogn)}$$$ ).

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

Speedforces.

Many people solved ABCD.

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

Wow, the contest is very good!

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

Need Help in problem D: **** I have solved Problem D using Python. i wrote the same logic in two different ways 1st way got Accepted but the 2nd way got TLE. both are exactly same as other only I changed the calculation part of the code and I believe it should not affect the run time. please help me out.

TLE Submission : https://codeforces.com/contest/1519/submission/114646999 Accepted Submission : https://codeforces.com/contest/1519/submission/114647073

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

    I think this blog might be helpful.

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

      Hey, the community should need to take this blog seriously and make the required changes in PYPY. during the contest, I made logic and coded it but the submission got TLE. I taught my approach was not optimal and started to think of other ways to solve that problem. finally ended not solving it. after the contest realized My idea is the only optimal way to solve it and all the people with python submission got TLE, only a few people who already know the above trick got accepted in PYPY. The tester of the round should have tried python also and they would have figured the TLE problem or they have not tested with python. please Do the need full I believe solving problems and learning should need to be the main goal the programming language we use should not be a barrier to it.

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

weak test in C

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

Can anybody please tell me why i'm getting TLE in C? Like i used the same approach as many the people who got accepted did, till today morning my solution was accepted by now it's showing TLE
here is the link to my submission https://codeforces.com/contest/1519/submission/114596588

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

    I too had same problem. But, the thing here is, for each k you are checking each university even if k>sizeof(university[i]). This makes your solution time complexity O(N^2).

    Better approach is to go for each university and then add its answer to k( which is less than sizeof(university[i])). To do this we need only O(N) time complexity.

    Here are my solutions:

    This is similar to your approach but got TLE: https://codeforces.com/contest/1519/submission/114653177

    Here I modified it as stated above and got AC: https://codeforces.com/contest/1519/submission/114659364

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

      if it's becoming O(n^2) then how come it passed TC:7 because which is some what similar to TC:8(on which i'm getting the TLE)

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

        Let's define n as the max number of the students in one university and m as the number of universities. The last loop in your submission will run n*m times. It seems that there is only one university which is numbered 200000 in the 7th testcase. However, there may be 100000 different universities in your TLE testcases, where the first university has 100001 students and every other university only has one student.

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

        No. They are not same. There is some difference which we cant see as only few numbers are visible in testcase.

        For proof:

        Let n = 200000 Let distinct universities be 10000.

        1 <= k <= n

        Total Computations = k_values x distinct_universities = 200000 x 10000 = 2*10^9

        So, you will get TLE.

        In other scenerio:

        Let students in each university be (n/distinct_universities) = 20

        Total Computations = distinct_universities * no_of_students_in_that_uni = 200000

        So, this will get you AC.

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

OH C ! You broke my little heart

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

Can Someone figure out why I am getting random values instead of 0, for problem C MyCode(https://codeforces.com/contest/1519/submission/114659037)

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

    :(

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

    i can't sorry bro

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

    sum = sum + (v[j][((long long)(v[j].size() / i) * i — 1)]);

    When i > v[j].size() the second index becomes -1 so you read memory outside of the vector (v[j][-1])

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

when the ratings update cannot wait for more time??

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

In Problem E, why doesn't the following greedy solution work?

I first order lines by their angles with Ox and iterate them by counter-clockwise order. For each line, find two points that can reach the line, and always take points under the line first. Of course, I remove selected points after each step.

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

    I did the same but got stuck on test 7 because there's a test case that ruins this approach. Let's say a specific angle has 3 points and other have 4 points and another one with 1 point. You're gonna choose any 2 of the 3 but what if the 2 points you choose were in the other 4 points ? It won't be chosen there (at the 4 points's angle). So, you have to choose 2 points out of the 3 that won't interfere with the 4 points to get the maximum number of moves and it would just interfere with that 1 point because it won't be chosen anyway. Hope you understand my explanation.

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

Time limit exceeded on test 8 :(

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

C was a pretty cool problem. Never seen anything like it, requires some thinking, yet not too difficult. Props!

Why not just pick n=2000 for D, so it can be solved in Python? Now I had to go back and rewrite my solution in C++ for no particular reason, just because the Python implementation barely times out. I actually thought it was a very nice problem other than that annoying detail.

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

    I assume n=2000 might have allowed some O(n^3) solutions to pass by virtue of vectorisation. That might be the reason setters kept n=5000.

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

Is it rated?

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

Problem C raises my doubt about how vector<vector<int> > works in different versions of cpp compilers. After calling push_back() for serveral times, sometimes the result is unexpected but sometimes it looks fine. It seems that this error is related to the version of the compiler. Could someone please explain why?

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

My solution 114601199 for the problem 1519C significantly coincides with solutions phungminhvu/114594685, ngtvu278/114601199. phungminhvu is my friend and he have helped me in this contest. I do not knowingly violate the rules so Can you forgive me this time ?

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

Editorials please...

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

MikeMirzayanov Please update the rating change, please...

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

I've got a nasty bug in the implementation of D which gives WA on Test 27. Can somebody help me figure it out ? 114670308

Test case 27
»
5 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Does anyone know why the rating change in the CF predictor is so different from the actual rating change?

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

hm? why so big delta between predictor and real rating changes?

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

Finally, after 14 months and 57 contests I have reached CM. Feels good :)

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

Why is the rating change so less than cf predictor?

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

    Ask the predictor creators. Its not an issue of cf

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

      why so confident? Actually almost always real rating changes are greater than predictor changes, in this case it's vice versa.

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

    Use Carrot, It is better and more accurate than CF-predictor.

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

How come CF-Predictor is showing +79 rating change but the actual rating change is only +48 for me while there are other accounts who have seen increase in their actual rating change :(

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

I think the positive delta is really low even after getting 2899 rank considering My previous ratings i should have got +120-130 but i only got +81. is it normal ?

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

    No.. of all the contests I have given this is the first time I have seen the actual rating change is less than the predicted rating change..

»