When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

By BledDest, history, 6 years 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 awoo Piklyaev, Vladimir vovuh 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

| Write comment?
»
6 years 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?

  • »
    »
    6 years 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...!

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

      Wubba lubba dub dub

      • »
        »
        »
        »
        6 years 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.

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Are there going to be pretests?

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

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

  • »
    »
    6 years 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.

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

      And what about hacks? Will they change rating?

      • »
        »
        »
        »
        6 years 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.

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

»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

24 hour open hacking phase ?

»
6 years 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).

  • »
    »
    6 years 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?

    • »
      »
      »
      6 years 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.

      • »
        »
        »
        »
        6 years 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 :)

        • »
          »
          »
          »
          »
          6 years 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

  • »
    »
    6 years 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)

    • »
      »
      »
      6 years 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

    • »
      »
      »
      6 years 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.

      • »
        »
        »
        »
        6 years 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

»
6 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Is there going to be more rated Educational rounds?

»
6 years 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!

»
6 years 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???

»
6 years ago, # |
  Vote: I like it -26 Vote: I do not like it

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

»
6 years 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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Make next educational contests rated

»
6 years 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?

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

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

»
6 years 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

»
6 years ago, # |
  Vote: I like it +55 Vote: I do not like it

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

»
6 years 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.

  • »
    »
    6 years 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.

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

OMG! That's good!

»
6 years 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

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is it "Rated"?

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

Will all Educational Codeforces Rounds be rated?

»
6 years 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

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

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it
»
6 years 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.

»
6 years 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.

»
6 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Is it rated?

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
6 years 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.

»
6 years 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

»
6 years 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?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

best thing to an educational round :D

»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Again 30 pages queue :\

»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Experiment Failed. ( Long Queues )

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

    I think long queues are not cause of round type.

»
6 years 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 ;)

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

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

    • »
      »
      »
      6 years 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.

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

Is it rated?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In queue for more than 15 minutes!

»
6 years 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.

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

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

»
6 years 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.

  • »
    »
    6 years 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.

  • »
    »
    6 years 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.

  • »
    »
    6 years 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

»
6 years 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.

»
6 years 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?

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is it Rated?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

  • »
    »
    6 years 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)))

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Anyone who failed a pretest got screwed with penalty time.

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

    So don't fail the pretests

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

      Good idea. I'll remember to keep this in mind for next time.

»
6 years 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?

  • »
    »
    6 years 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.

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

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

    • »
      »
      »
      6 years 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

  • »
    »
    6 years 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

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

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

»
6 years 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?

  • »
    »
    6 years 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

    • »
      »
      »
      6 years 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."

»
6 years 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

»
6 years 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?

  • »
    »
    6 years 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!

  • »
    »
    6 years 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

    • »
      »
      »
      6 years 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

      • »
        »
        »
        »
        6 years 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

  • »
    »
    6 years 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.

»
6 years 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

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

    Try LONG LONG INT

  • »
    »
    6 years 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

    • »
      »
      »
      6 years 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 :(

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

        go throught dfs and connected componenets...it'll help

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ???

  • »
    »
    6 years 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)).

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

      Thanks a lot :)

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

      __"we need to make sure that day[j] > 0 n days that a[j] = 0" shouldn't it be "day[j]>=0"?

»
6 years 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(((

  • »
    »
    6 years 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.

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

      Oh my god, I roundly got the idea. But can you write the details please :)

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

        initial players 1,2. spectator:3.

        the result has to be between players.so the result has to be 1/2. if result=1, spectator=2, player=3. swap between loser and spectator.

        if result=2, spectator=1, player=3

        now players: 1,3 spectator: 2 ....it goes on till the end

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

          Ok, but when we will reach the end? I can't get it(

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

            end is the end of input elements. array size

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

              Oh yeah, I'm that stupid... But... I'm sorry again, what is the array size....

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

                "The first line contains one integer n (1 ≤ n ≤ 100) — the number of games Alex, Bob and Carl played."-- This n is the no of array elements or size

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

                  Ohh.. I know, I'm so stupid. But how to swap players. That's a problem.

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

                  Go to toilet then have a dinner, again go to toilet and players will be swapped.

  • »
    »
    6 years 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.

    • »
      »
      »
      6 years 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 ^_^:)))

»
6 years 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

  • »
    »
    6 years 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.

    • »
      »
      »
      6 years 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.

      • »
        »
        »
        »
        6 years 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.

    • »
      »
      »
      6 years 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.

»
6 years 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?

»
6 years 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?

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

    Yes, because people's solutions can still be wrong.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces give or take points in this contest?

  • »
    »
    6 years 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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks a lot for problem F's time limit

»
6 years 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

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

How to solve problem F??

  • »
    »
    6 years 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.

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

      thanks man

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

      Can you please elaborate your solution ?

    • »
      »
      »
      6 years 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?

      • »
        »
        »
        »
        6 years 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.

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

          Thank you so much.

          • »
            »
            »
            »
            »
            »
            6 years 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!

            • »
              »
              »
              »
              »
              »
              »
              6 years 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)

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years 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.

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

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

»
6 years ago, # |
  Vote: I like it +126 Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve E ?

»
6 years 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?

»
6 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Round should be unrated. Very long queue

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A?

  • »
    »
    6 years 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

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Really nice problems!

»
6 years 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

  • »
    »
    6 years 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.

»
6 years 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

  • »
    »
    6 years 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.

    • »
      »
      »
      6 years 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.

  • »
    »
    6 years 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
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain, how to solve F in detail ?

»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    6 years 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 :)

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

ratings?

»
6 years 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.

  • »
    »
    6 years 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.

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

    It looks like it's system testing now.

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

      It's being done at a mind-blowing speed as well..

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When we can see the mew rate?

  • »
    »
    6 years 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.

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

sorry i mean new rate

»
6 years 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.

»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

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

really nigga :| its still testing

»
6 years 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

  • »
    »
    6 years 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

    • »
      »
      »
      6 years 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

  • »
    »
    6 years 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.

»
6 years 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.

  • »
    »
    6 years 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.

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

When can i see my new rating?

»
6 years 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

»
6 years 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?

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

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

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

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

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

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

      • »
        »
        »
        »
        6 years 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 always_4ever_5_25__21_SS there are some other issues where rating change doesn't make sense.

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

          my friend had + 108 but ended up with +124

          • »
            »
            »
            »
            »
            »
            6 years 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 :)

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

      I had +68, ended up with -2

  • »
    »
    6 years 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

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

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

»
6 years 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???

»
6 years 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 .

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

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

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

    CF predictor +35 Rating -35 Became Specialist

»
6 years 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.

»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Is there anything wrong with rating changes? BledDest MikeMirzayanov

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

    Yes The Rating seems to be super mega unfair ?????

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

    Prediction might be correct :/

»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Isn't this weird!

  • »
    »
    6 years 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...

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

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

Why?

»
6 years 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???

»
6 years 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)

  • »
    »
    6 years 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.

  • »
    »
    6 years 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.

    • »
      »
      »
      6 years 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...

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

      It's just a number bro

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

Round should be unrated because the problems were very easy

»
6 years 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.

»
6 years 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.

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

It's fixed, the ratings. Thank You.

»
6 years 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.

»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Good Contest

»
6 years 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.

»
6 years 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????

  • »
    »
    6 years 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.

»
6 years 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?