By BledDest, history, 3 weeks ago, translation, In English,

Hello Codeforces!

On November 23, 18:05 MSK Educational Codeforces Round 33 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.

As an experiment, the round will be rated for Div. 2. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were prepared by Mikhail PikMike Piklyaev, Vladimir 0n25 Petrov and me.

Good luck to all participants!

UPD: Editorial.

I also have a message from our partners, Harbour.Space University:

Be sure to join these courses to sharpen your programming and data analysis skills:

Combinatorics and graphs with Sergey Nikolenko, Researcher, Steklov Mathematical Institute at. St. Petersburg. He is a computer scientist with vast experience in machine learning and data analysis, algorithms design and analysis, theoretical computer science, and algebra.

Algorithms and Data Structures with Edith Elkind, Professor University of Oxford, Department of Computer Science. She researches game theory and the computation of social choices. She looks at the decisions involved in multi-agent systems such as auctions, elections and co-operative games.

Big Data Analysis: Mapreduce, Spark, BigTable/HBase, Distributed Data with Pavel Klemenkov and Alexey Dral. With HDFS, MapReduce, Spark, and NoSQL, students will master and sharpen their knowledge in basic technologies of the modern Big Data landscape.

Parallel and Distributed + High Performance Computing with Dalvan Griebler. The name says it all. Learn how to run your programs faster.

List of all courses:

27.11.17 — 15.12.17 — Image and Video Analysis with Archontis Giannakidis

27.11.17 — 15.12.17 — Linear Algebra with Archontis Giannakidis

08.01.18 — 26.01.18 — Text Mining & Translation with Sergey Nikolenko

08.01.18 — 26.01.18 — Combinatorics and graphs with Sergey Nikolenko

29.01.18 — 16.02.18 — Security analysis of networked objects with Yaroslav Rabovolyuk

19.02.18 — 09.03.18 — Security Operations Center and Cyber Threat Hunting with Sergey Soldatov and Teymur Kheirkhabarov

19.02.18 — 09.03.18 — Calculus with Dmitry Ivankov

12.03.18 — 30.03.18 — Malware Reverse Engineering with Vladislav Stolyarov, Victor Chebyshev and Boris Larin

09.04.18 — 27.04.18 — Incident Response & Digital Forensics with Konstantin Sapronov and Ayman Shaaban

09.04.18 — 27.04.18 — Linear algebra with David Zmiaikou

30.04.18 — 18.05.18 — Statistical Data Analysis with Evgeniy Riabenko

30.04.18 — 18.05.18 — Probability theory with Evgeniy Riabenko

21.05.18 — 08.06.18 — Parallel and Distributed + High Performance Computing with Dalvan Griebler

21.05.18 — 08.06.18 — Algorithms and Data Structures with Edith Elkind

11.06.18 — 29.06.18 — Big Data Analysis: Map Reduce, Spark, BigTable/HBase, Distributed Data with Pavel Klemenkov and Alexey Dral

Register for your spot

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

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

What are the exact rules of the rated contest? Since it's non-standard CodeForces round, you could have included more details about it.

Will hacks count into result? Will the ranking be like usual Educational rounds?

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

    I think it's first time, when educational round become rated. Hope problems will have short statements not as this announcement. Wish everybody luck and high rating...!

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

      Wubba lubba dub dub

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

        I hope the round will be unrated, because the query sometimes was more than 35 pages, and it was unreal to solve task without lost time.

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

    just like common div2 games,so take it easy and enjoy it.

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

    bazsi700.It's div2 contest...

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

Are there going to be pretests?

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

    I hope not, so that this contest would really feel different.

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

    No, the rules will be completely the same as on the previous Educational Rounds. After the contest we will build standings with Div. 2 participants only and update ratings according to taken places.

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

      And what about hacks? Will they change rating?

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

        I guess answer is NO, because if anyone who belongs to Div 2 and doesn't participate in contest, but have some successfully hack then what is happened? Also anyone can hack a lot of solution, then it arise a big problem in rating change.

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

        They won't. Your rating change depends on your language. For example I use C++, so C++ gives me more rating.

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

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

24 hour open hacking phase ?

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

About the rules of rating distribution:

After the hacking phase the participants from Div.2 will be sorted according to ICPC rules (by number of solved problems, and if the number of problems is equal, by penalty). Then the rating will be redistributed according to places in Div.2.

There will be pretests, and the number of them will be larger than in regular Codeforces Rounds, but we don't guarantee that if the solution passes pretests, it will pass system tests.

This might be inconvenient for some participants, but remember that this round is experimental, and we may make ERs unrated again after this round (or change the rating distribution system in ERs).

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

    Does the number of successful/unsuccessful hacks made during the hacking phase affect your rating like in normal Codeforces rounds?

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

      The number of hacks a person made won't affect his/her place in this round.

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

        Why won't affect ?
        If I will hack someone who solved 1 problem more than me, he will fall and I will in place upper :)

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

          What if he is in upper place after you hack, or lower place before you hack...:p

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

    A couple of proposals:
    You may divide all rating changes by 2 (do it "half-rated") due to specificity of edicational rounds.
    Add small score bonuses for successful hacks (hacking is useful for community, so it should be rewarded)

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

      Saw some guy giving the exact same suggestion some months ago and getting some umpty number of downvotes

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

      Anyone can hack a lot of solution. Then it will be a big problem, if there any bonus for successful hack.

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

        -1 penalty or -5 penalty with 1 successful hack will solved this problem

»
3 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

Is there going to be more rated Educational rounds?

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

I can't wait to see how rated educational will work. Good luck to everyone!

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

So as i understood it will be a cf round with educational problems which are really nice, with rating system like atcoder and cs academy, no hacks(because they don't count into the rating). What can be better in the world than this???

»
3 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

Is it rated? And if it is rated, can it became unrated?

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

I think that you should write into the description with really big letters that is rated because some don't see it very well.

»
3 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

So, CF is moving to ACM-ICPC style permanently? There will be no hack during contest in near future or soon? :)

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

Make next educational contests rated

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

So will system tests happen after the 24 hour hacking period so that hack cases can be added into the system tests?

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

    Actually, we add hacks into system tests in each ER.

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

You say: Educational rounds primarily pursue educational and training goals, rather than competitive ones. But edutcational is rated. Don't be so

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

Paradox :D Last official rated rounds — unrated. Next official unrated round — rated.

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

Will the rating change after the contest ends or it will change after 24-hour hacking phase? If it change after 24-hour hacking phase, will hacks affect to a participant's rating?

Hope this round will be the best rated Educational Round ever.

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

    Of course rating change after 24-hour hacking phase, because final system test occur after 24-hour hacking phase. Hack means a wrong solution, so rating must be affect with hack.

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

OMG! That's good!

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

What is the influence for penalty if I hack others? I have a suggestion. If I hack others successful, I got -10 min penalty, otherwise, I got 20 min penalty

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

Is it "Rated"?

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

    What are the exact rules of the rated contest? Since it's non-standard CodeForces round, you could have included more details about it. Will hacks count into result? Will the ranking be like usual Educational rounds?

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

      So as i understood it will be a cf round with educational problems which are really nice, with rating system like atcoder and cs academy, no hacks(because they don't count into the rating). What can be better in the world than this???

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

Will all Educational Codeforces Rounds be rated?

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

Rated educational contest: ACM with semi-freezing for the entire contest including yourself

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

Codeforces probably will be more and more interesting!Come on!

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

That's just a suggestion.

You can add another Rating Criteria say Educational Rating and make all the Educational Round rated based on the usual rating system or any other rating algorithm.

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

It'll feel more different if there would be no pretests and 1 day hacks.

»
3 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Is it rated?

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

    Any educated person can read this blog. Sorry to say, you can't!

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

      Any educated person wouldn't write answer to this comment. Sorry to say, you did(((

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

    NO, It isn't

»
3 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

I can not more agree with the dicision

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

finally there will be Edu. Round in my contest list :-)

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

Why this page is not included in "HARBOUR SPACE UNIVERSITY" page as Educational Codeforces Round 32 Announcement?


UPD: It was updated.

»
3 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

I'm a newbie =)) everry body who can help me how to study as well in IT

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

Good luck to everyone! We're all eager to know how this will work! Anyway, I want to mention that I'm okay with frequent changes of how the contests work, but I would like to maintain the situation of having one weekly contest that isn't rated(besides of other rated contests). What do you people think?

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

Is score will be Based on the time of submission??

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

    yes, penalty = sum_time + (amount of unsuccessful submits) * 20

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

    No, it will be based on your code. How long is it, it depends on size of your code.

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

best thing to an educational round :D

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

Again 30 pages queue :\

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

Experiment Failed. ( Long Queues )

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

    I think long queues are not cause of round type.

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

12 minutes to surpass the queue (and received a WA after that). Either Codeforces server is running into trouble again, or you guys haven't anticipated enough about the number of submissions in educational contests...

UPD: Things are getting a lot better now. Can't compensate the issues, but still cheers ;)

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

    It's not our problem. So what do you want?

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

      Actually, it is. The pressure of waiting for judgement for your "threshold" problems — that means the "just right" problems, hardest you can solve in a contest — is increasing dramatically due to long queues. Also, nobody enjoys an environment with bugs and issues. They should be reported so that the administrators/moderators or the contest setters could figure out and attempt to fix it.

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

Is it rated?

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

In queue for more than 15 minutes!

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

Codeforces improves significantly!! There are only 27 pages of queue now.

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

I think new diagnostics of solutions in c++ failed the crash-test...

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

Why is the answer for a 3rd test case in problem D is 2? No explanation given as well as this question is also not well framed.

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

    The answer is indeed 2. I am not sure whether I am allowed to give you an explanation in the middle of the contest.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Optimal:
                  1   2   3   4     5 
    Mornings      0  +5   0   0    +11
    Day Balance   0  0    0   10   10
    Evenings      -5  0   10  -11   0
    

    In check-days we have non-negative balance, balance always less or equal than d.Answer: 2 deposits.

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

    i was a bit confused too, but then i got that we can put some money to account before 0 operation comes in the evening

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

I think contest is going well.Queue is for having many test cases than regular contest :) Though sometimes it is bothering,but well enough comparing with bad pretest.

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

I hate D.Why you don't give an explanation to example when you know many people can't understand it clearly?

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

Is it Rated?

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

How to solve E?

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

    first preprocess all the lowest prime factors, factorials and their inverses up to 1e6+5. Then for each x find the powers of each prime in x. You can need to distribute each power in y buckets. (basic stars and bars problems) Also to accommodate negative integers see that you can have even number of negative numbers. So final answer will be:

    Calculate 2y - 1 by fast exponentiation. So time complexity: O(t * log(max(x, y)))

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

    Yes, I couldn't solve it too. How to solve it guys?!)

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

Anyone who failed a pretest got screwed with penalty time.

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

The submission 32583028 got TLE, but then 32586076 got AC while I only changed the compiler from "GNU C++17 Diagnostics" to C++11 (and lld to I64d). How to explain this phenomenon?

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

    With such two diagnostic launches, the performance of the program suffers tremendously (the program is executed 5-100 times slower and requires more memory), but often it's worth it.

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

      Thank you! I'd be more careful next time.

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

      Maybe add a warning beside the language name, something like (slower) or (only for debugging)? not everyone who has not seen the blog post will know about this

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

    You must not have seen the blog post. "GNU C++17 Diagnostics" runs much slower than the standard compiler as it checks for certain errors in your code. Check http://codeforces.com/blog/entry/55902

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

      I thought it was just adding additional checks into the code...

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

Will rating be calculated according to your standings without Div 1 participants (kind of like Div2 rounds with out of competition Div1 competitors) or like a combined round?

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

    I think it maybe a Div1+Div2 round and only to rate for Div2

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

      Okay, based on what Bleddest said, I think it'll be according to your standing among Div 2 competitors only. Correct me if I'm wrong.

      "After the hacking phase the participants from Div.2 will be sorted according to ICPC rules (by number of solved problems, and if the number of problems is equal, by penalty). Then the rating will be redistributed according to places in Div.2."

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

hi i cant find the bug in my code

can anyone help ? http://codeforces.com/contest/893/submission/32598508

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

For those who got WA on test 49 on D and later got AC, what logical error did you find?

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

    diff here 32594374 and here 32596916

    my idea was to use two limits mn - mx which the balance should be one of, I missed the case I meet a 0 and not update my mn to at least max(mn, 0) because if that value is below zero, some cases might add to mn which would fail my condition of failing which is mn > d it means you just can't achieve the goal!

    Hope this helps!

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

    While propagating the extra money that you are adding you need to keep in mind that you do not end up decreasing sum below 0.

    Go through this once.

    Let me know if you are unable to understand something

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

      What is wrong with my solution here. I understood your point, but I am always keeping my sum equal to d when sum>d and subtract the reduction from excess. So in my case, I can't decrease my sum below 0. 32597627

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

        well

        you need to check if your present sum < 0 Only then that is required... You need to find the minimum exchanges.

        I guess thats the only difference between our code

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

    I honestly don't know I got it in the last 3 minutes so after that I started changing small things in my code (I didn't even know if the changes were going to do something or not) and then submitting the code I sent like 5 submissions in 5 minutes I was like crazy.

    Anyway a few of my submissions got AC but I don't know if it's going to stick.

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

could someone help me with problem c I keep getting wrong answer on test 7 link to my solution: https://goo.gl/95gxqy

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

    Try LONG LONG INT

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

    you havent considered the smallest one

    I think you've missundestood the problem.

    you can go throught this ,

    hope it helps

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

      thank you for your help but I can't understand the code because I'm beginner :(

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

who can share some hacks to show where people made mistakes?

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

How to solve D ???

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

    There is no contest results yet. So contest is in progress. You shouldn't ask solutions of others, boy ya!

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

    Here is my submission: 32585910.

    First, I took the prefix sums of all a[i] in the array I called day. I also saved which days a[i]=0 in the array check so I know which days the balance needs to greater than 0. Notice that the balance on day j is day[j].

    Since the balance on day j is day[j], we need to make sure that day[j] >= 0 n days that a[j] = 0. If day[j] < 0, we want to deposit money that morning. Since we want to add money for the minimum number of days, we want to add as much money as possible when we are depositing money. If we add x money to day i, the amount of money on days i...N all increase by x. Therefore, The maximum amount of money we can add on the morning of day i is D-( max(day[j] for j = i...N) ). To calculate max(day[j] for j = i...N), create an array mb where mb[i] is max(day[j] for j = i...N). Loop backwards to create mb. Now, if on day i a[i]=0 and day[i] < 0, we can deposit D-mb[i] that morning. We now need to store that days i...N have D-mb[i] more money. Create a variable add which stores how much money has been added in the mornings.

    If at any point day[i]+add > D, print -1 because the account has more than D burles. If a[i] = 0 and day[i]+add < 0, deposit D-(add+mb[i]) but deposit at least 0-(day[i]+add), otherwise the account will have negative balance. So add += max(D-(add+mb[i]), 0-(day[i]+add)).

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

Can someone explain me problem A in more detail??? I can't figure out my solution(((

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

    start with 2 people (1 and 2), 3 is sitting out. then start a loop and check if 1 wins then swap 2 with 3, so now the players become 1 and 3. 32591094 will tell you the logic. it becomes obvious once you do it by hand.

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

    You just have to simulate the game, Alex and Bob start playing and Carl is spectating. So if Alex wins ( if the number is 1 ) you change Bob who lost with Carl , now Alex is playing with Carl if the number is 3 means that Carl wins, so you have to change the players again....

    Do this until you find some absurd ( the person who wins is the spectator ) or until the movements finish.

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

      Oh yeah, I got your idea. But I don't know how to implement it. Can you help me please ^_^:)))

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

for problem C, shouldn't DFS with connected components get me the correct answer? I am failing 5th test case. 32595477

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

    for starters, your array should have a size of at least 100001, because you're storing everything 1-based.

    In general, it's a good practice to add 5 elements more to your limit to avoid these problems.

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

      thanks. I am a fool. 32601419

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

      Why count him as starter? He has better potential than you. He tries to solve hard problems. NOT LIKE YOU. So you should get your tongue tied.

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

        Oh my god, he didn't call BeardAspirant a starter. It's just a way of speaking. It's similar to: "Firstly, your array should have a size of at least 100001 ...". And why the hate? Also, who are you to decide who has better potential? Stick to what concerns you.

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

      in general for competitive programming. Generally, you should be very sure about which indices are actually accessed.

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

i solved problem D using segment tree lp. what is the simplest way to solve D?

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

Must we wait till the end of hacking phase to know the rating change?

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

Codeforces give or take points in this contest?

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

    It depends on your rating. In your case (pupil), you won't get any points. For example, in my case (newbie), I will get exactly more than 2500 points.

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

thanks a lot for problem F's time limit

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

Pls, someone tell me, is it correct solution for D?

http://codeforces.com/contest/893/submission/32601001

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

    I think your solution is incorrect. But problem is not in your idea or in your code. Sorry to say, Your problem is in your name... Maksim... Maksim... Maksim.. I really feel sorry about you(

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

How to solve problem F??

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

    Build a merge sort tree on the <value, depth> of the tree in DFS order. When merging, remove elements so that value is non-decreasing and depth is non-increasing. Then each query becomes over this range, what is minimum value if depth is maximally (depth(x) + k). Solve this by having a fenwick tree or doing a binary search.

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

      thanks man

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

      Can you please elaborate your solution ?

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

      Can you explain the 'process' function in your code? Or, what are you trying to achieve using the fenwick tree?

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

        Yeah that code shouldn't work, and doesn't properly implement what I said above, but I guess it's hard to find tests that make it TLE. I'll write up a cleaner commented version and link it here later today.

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

          Thank you so much.

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

            Alright, here we are. This solution is

            , but runs in around 2.5 seconds (TL is 6 sec).

            First, run the DFS to get a list of nodes in DFS order. Then, build a segment tree on these nodes. For each segment, we keep a map from depth to the minimum value at that depth. Then to get the answer for a segment and a depth d, take the minimum value over all depths <= d on that segment. To do this quickly, use prefix minimums or a fenwick tree. The fenwick tree is overkill here, but would support updates quickly.

            Prefix Minimums: http://codeforces.com/contest/893/submission/32656954

            Fenwick Tree: http://codeforces.com/contest/893/submission/32656865

            Let me know if you have any more questions!

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

              I have used segment tree, instead of fenwick and prefix minimum. Although, I am getting accepted, can you tell me, why is it running so slow ? (3.4s)

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

                Segment trees just run slower than fenwick trees or prefix mins. They have a higher constant cost.

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

                  oh okay. Thanks man! You have been really helpful.

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

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

How to solve E ?

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

getting TLE in c++17 and clang++17 Diagnostics and accepted in c++14. How?

»
3 weeks ago, # |
  Vote: I like it -22 Vote: I do not like it

Round should be unrated. Very long queue

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

How to solve A?

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

    You can just simulate the game: have three boolean variables / array of 3 bools and then update them based on who wins.

    If the bool variable corresponding to the player who wins is false (e.g he could not have played in the first place), print -1 because such a win is impossible

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

    You can have 3 variables, these can be 2 on and 1 off, then you are reading and only ask if it is on or off, if it is off the answer is "NO", if it is on you change the three variables to its opposite, then you return to change only the variable read and repeat the process until finished. If you finish without problems the answer is "YES".

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

Really nice problems!

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

For problem C, I have seen that (in hacking phase) many contestants have used dsu using two arrays — cost, parent. But my code shows memory limit exceeded on test 4 with 10^5 sized array — 32587358

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

    You forgot to return a value in the second case of your par function. You are compressing a path but not returning it.

    Hope that fixes it.

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

I made the following observations on E. 1: the number of prime factors of x cant be more than 20. And there can be atmost 8. even when it is 8 it is > 1e6. So build a dp table for binomial co efficient. 2: In order to find the prime factors modify seive table to hold the largest prime factor dividing it. 3: Split x into prime factors. And count the number of walls. (Combination with repetition). and using binomial coefficient we can make C(y+w+1, y) choices ( here 1 is for the number '1'. since i can include it). But here i got stuck. since in these y factors different prime numbers can be different number of times in which i ve to use permutation with repetition (to arrange within them). But how to apply it here. And after that choose any 2, 4, 6,.. numbers in y numbers and again multiply them with the permutations (for choosing negative. ) here also i got stuck. Can someone plz help me

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

    Your logic is correct. For your last part, consider the binomial theorem expansion of (1+x)^n. Sum of all n choose k is 2^n.

    Now put x=-1. You will see that sum of all n choose odd k= sum of all n choose even k. Hence, the sum of n choose even k= 2^(n-1).

    Also, note that the sequence starts from 0 and not 2.

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

      Yes. it is correct for nC2 + nC4 + .. . But i can arrange within them. So it will be (n!/(rep1! * rep2!...)) * (nC2 + nC4 + ..). so how to calculate the (n! / rep!), rep1 = number of times prime factor 1 is repeating. rep2 is no of times factor 2 is repeating.... . for eg, suppose if i ve 2, 2, 3. then i can arrange them in 3!/2! = 3 ways(here n = 3, rep1 = 2, rep2 = 1) . so i ve to multiply that with the answer. here there is 2 times 2 hence i put 3!/2!. But when i choose y numbers, i dont know how mnay numbers repeat how many number of times. So how to solve that.

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

    There is a very simple idea in which you don't have to worry about repetitions -- Let's represent the given number x as it's product of prime factors. Observe that each prime factor is independent of other. So we can calculate the answer for each prime factor independently and multiply it with the final answer. The pseudo code will be something like this:

     res = 1
    for each primeFactor in x:
    c = number of times that primeFactor occurs in x.
    res *= numWays(c, y)
    res *= power(2, y - 1) //Now res is your final answer.

    Now the problem reduces to finding numWays(c, y) efficiently. Observe that we have c apples and we need to distribute them to y people such that a person might not get any apple. So the numWays is just ncr(c + y - 1, y - 1). So the final idea is:

     res = 1
    for each primeFactor in x:
    c = number of times that primeFactor occurs in x.
    res *= ncr(c + y - 1, y - 1)
    res *= power(2, y - 1) //Now res is your final answer.
    Hope it helps
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain, how to solve F in detail ?

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

Perfectly matched problems for DIV2. Thanks to authors & testers:)

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

    Problems were nice, but I think E is easy for Div2E, maybe it can be D of Div2 :)

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

ratings?

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

No system testing?? The standing page says its the final standings, i thought hack tests will be added before final standings.

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

    When the hack phase ended, they announced that the solutions will be rejudged on hacks soon.

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

    It looks like it's system testing now.

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

When we can see the mew rate?

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

    We have to wait for them to rejudge the solutions with the new tests and then they'll update the ratings.

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

sorry i mean new rate

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

I think if educational rounds will be rated in the future too, I think a feature should be added, the system testing percentage one like normal rounds.

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

System test is too slow................................................

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

really nigga :| its still testing

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

In Div 2 C (Rumors),I don't really understand why my first submission isn't working and second is working. I only changed how I set my data type (for example from long long, I switched to typedef long long ll). My first submission results in a wrong answer on test case 5. I am really curious what did I do wrong, so I can know for next time. I didn't change anything in algorithm.

My first submission:

http://codeforces.com/contest/893/submission/32631226

My second submission

http://codeforces.com/contest/893/submission/32631196

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

    Look you change the size of graph, in the first solution, if you add edge (99999, 100000), you have problems

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

      Ohhh, so I made a mistake by typing 100000 on a vector instead of 1e5+10

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

    vector <int> v[100000]; and long long niz[100000]={0}; your adjacency list size as well the cost array will not store the 1e5th node values, there is no spaces to it.

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

Hey mikemirzayanov do you need my laptop? I guess it will help the system for judging.

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

    hahah, this has to be the longest systest ever, and no progress indicator too.

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

When can i see my new rating?

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

System Testing is finally OVER !! How long will it take for rating changes to reflect? :D

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

If I had +65 rating in combined list, shouldn't I have more rating in only Div 2 list? Am I wrong?

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

    Same, I had +77 but ended up with +2??

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

      same here i got +89 but finally it increased by +27

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

        same here, +45 combined, -25 actual rating change

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

        +46 == -11 :/

        I think rating predictor might have been offset from div1 participant, but it should not be THIS drastic.

        Also, as described by Psycho12Killer there are some other issues where rating change doesn't make sense.

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

          my friend had + 108 but ended up with +124

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

            Yes, rating changes are going up/down/everywhere. Many are now providing examples of unfair/nonsensical rating changes. I really hope this issue is resolved.

            P.S Good for your friend :)

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

              yeah , but it's really weird because CF predictor never gives less than the original rating change :)

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

      I had +68, ended up with -2

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

    +80 but ended up with -8.

    Looks like those who got 4 or more AC had big increases in rating. Those with just 3 heavily suffered from rating loss, regardless of time penalty

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

    Same, CF-Predictor predicted +115 , got +33 only.

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

I didn't understand the rating change fact. Before this contest i had a rating of 1510 and i became 74 (in division 2) and my rating increased by 104. There is another person who became 304 and his rating increased by 98 (his previous rating was 1530). Is it because this is an educational round and things are handled differently???

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

CF Predictor show +74 Rating and Got +8 . don't know how they calculate it .

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

    cfpredictor count with div1(( It shows + 56, get +1

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

      so is there a problem? :|

      I am finding this odd.

      Will the ratings be updated again? :|

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

    CF predictor +35 Rating -35 Became Specialist

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

Div 2 only,

Rank 55, previous = 1811, increase = + 125, new = 1936,

Rank 77, previous = 1795, increase= = + 24, new = 1819.

Also,

Rank 7, previous = 1891, increase = +193, new = 2084,

Rank 10, previous = 1757, increase = + 141, new = 1898,

Looks very odd in my opinion, especially the second one.

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

Is there anything wrong with rating changes? BledDest MikeMirzayanov

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

Isn't this weird!

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

    Yup, that's wierd :p , i guess ratings will be recalculated...

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

Rank 612 — rating 1640 => -42 Rank 1771 — rating 1695 => -53

Why?

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

I was 1526 and finished 441st in the contest and my rating went down, IT WENT DOWN.. HOW AND WHY???

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

These ratings are unfair ! Moderators please look into it. Some ambiguous result below

BEFORE CONTEST: User 1: Initial rating 1342 User 2: Initial rating 1120 AFTER CONTEST: User 1:(Contest rank div2: 1636) Final rating 1368 (increase of just +26) User 2:(Contest rank div2: 1816) Final rating 1214 (increase of +94)

»
3 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

I don't think I will be joining rated educational rounds again , I will stick to regular rounds. Waiting for a day for rating change and systems tests + weird rating change (no thanks)

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

    You should also note this is experimental/first time they are doing such a contest, it is very possible they will fix this for this contest and future contests.

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

    Exactly ! If this is how experiments turn out, I will refrain from participating in "rated" educationals from now on. I was so positive and excited about new ratings...but now I am depressed as hell.

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

      I was excited about going back to Expert after a long time but no, 18 points decreased, fantastic...

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

      It's just a number bro

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

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

Round should be unrated because the problems were very easy

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

Just an assumption: Maybe while rating they considered only points i.e. number of questions solved. So all those who solved the same number of questions were ranked equally from rating point of view. I assume this seeing the anomaly in the comment section.

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

looks like the new rating is based on the number of problems you solved, not your standing on this contest. It is unfair to change the rating rule without announcement before the contest.

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

It's fixed, the ratings. Thank You.

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

I solved 3 and initially my rating was increased by +26, which itself was less, and now they have revised the ratings and now it is +3 only. Seriously? -_-

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

Very Good contest, I like it, very very good. Make more contests PLZ.

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

Good Contest

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

I noticed that the rating changes did not apply on the Rating page.

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

what the hell!!!!!!!!!!!!!

How you count the rating ???? which process it has changed????

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

    Dude your rating has increased by 101 points. Are you really that angry?

    I mean its all right to know how the rating changes work but you wayyy more angry than some of the other participants who've had their ratings decreased in spite of expecting an increase.

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

      Dude I know my rating has increased.

      But I Want to know how they count the ratings.... That's It.

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

My rating increased by 6 and now it shows -11..why?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • Hello codeforces i am new here can plzz somebody tell me about the ** hacking phase** round that started after the contest .. i dont know what i have to do in that round !!!