Educational Codeforces Round 49 [Rated for Div. 2]
By awoo, history, 6 years ago, translation, In English

On Aug/18/2018 17:35 (Moscow time) Educational Codeforces Round 49 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

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

The problems were invented and prepared by Vladimir vovuh Petrov, Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Mike MikeMirzayanov Mirzyanov and me.

Good luck to all participants!

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

Hi Codeforces!

Our Hello Barcelona Programming Bootcamp will be kicking off next month from Sept 26 — Oct 4, and we’d love to see you there!

The boot camp will once again feature the all-time greats Mike MikeMirzayanov Mirzayanov, Andrey andrewzta Stankevich, Michael Endagorion Tikhomirov, Gleb GlebsHP Evstropov, Artem VArtem Vasilyev, Ivan ifsmirnov Smirnov and other world renowned Russian coaches to train the participants.

You will be competing and learning side by side with some of the greatest teams in the world, while learning from the best coaches the ICPC has to offer.

Be sure to register before September 1st so everyone has time to get visas if needed, and of course for the Early Bird Discount of 5% or the Loyalty Discount* of 20% off registration for the boot camp!

*The loyalty discount is offered to universities and individual participants that took part in Hello Barcelona Bootcamps and Moscow Workshops ICPC.

Learn more about Barcelona ICPC Bootcamp

You can ask any questions by email: hello@harbour.space

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Um_nik 7 179
2 isaf27 7 343
3 BlackPuppy 7 357
4 eddy1021 6 157
5 ppc_qjd 6 176

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 200:-25
2 eR6 87:-58
3 Winniechen 35:-13
4 jhonber 29:-1
5 Kaban-5 19
697 successful hacks and 674 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A arknave 0:02
B eddy1021 0:06
C bekzhan97 0:12
D teja349 0:12
E step_by_step 0:10
F lee_sin 0:24
G uwi 0:39

UPD: The editorial is posted

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

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

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

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

What will be the penalty, 20 or 10 ..??

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

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

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

=A=

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

Why those great bootcamps don't have public videos for participants not being able to manage to there ?

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

    then why should some people go there on their own expense,they would also wait for videos/tutorials to get public.

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

      true !

      But both are not the same thing, getting videos are least you can hope!

      peace

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

Have anyone noticed that after Codeforces Round #503 and #504, although rating recalculated in users' profiles, RATING page and Top rated page didn't change?

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

    Yeah, but the colour changed, so now the Top rated page has 9 nutellas and one red (who's in the 9th place)!

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

The internet of machine room is out of service, sadly I have to use my wifi to play codeforces....

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

Assalamu alaykum MikeMirzayanov!
When will you update Rating?

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

Assuming ACM ICPC rules, the problemset won't be sorted by increasing difficulty, right?

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

Hey, what will happen with Round 505? It starts tomorrow when hacking phase is still going on

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

halyavin is going to take part in the round! Stay determined!

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

How to solve F?

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

    My idea was doing binary search. And for checking matching, we can use Hall's theorem.Here hall's theorem converts to checking each component has more exam days than students.

    It gave TLE on 46th. So now I think the above procedure can be done with a dsu and a sort. Hopefully it should pass

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

      Nice application of Hall's theorem.

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

      Yeah DSU works

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

      I managed to get it accepted this way (binary search + application of Hall's theorem) although several attempts were required.

      Adding rank heuristic and getting rid of rand() calls in my implementation of DSU is what finally worked.

      Code: 41803434.

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

      I just binary search and matching. In the contest, I got WA on 17th because of the mistake of binary search :'( (41788874 ), just fix it and got AC. (Matching in O(n^2)) 41796159. Sorry for my bad English

      • Edit: TLE main test.
      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Perhaps a 2-SAT solution exists?

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

      Yes, I did 2-SAT with binary search: 41787621 (MLE Test 45).

      We have two variables Vai and Vbi for each exam, with Vai positive if we want to take exam i on day ai.

      Of course, if the binary search value we are evaluating is smaller than bi (resp. ai) then Vbi (Vai) has to be false.

      Then we just need to enforce "at most one exam a day", which I did by taking a prefix and suffix OR of the variables correp. to exams on a given day. Please ask for more details if the code / my description is unclear.

      Note that this uses 6N variables (3 for each day each exam is on).

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

        Hi! It took me quite a long time to understand the prefix/suffix OR idea. I reimplemented your solution using Tarjan algorithm for SCC, and got TLE on test 45. I generated random test of the same size, and it takes ~16 seconds. So I don't think it is possible get this solution accepted, the constant factor is just to big - the memory allocation for the graphs are the culprit I guess. Thanks for the idea though. (https://mirror.codeforces.com/contest/1027/submission/42493816)

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

          Stopped creating a new graph in each binary search check, just set the variables which are out of range to false, got down to 7 seconds. Can't think of any other reasonable change. I would really like to get it accepted :(

          https://mirror.codeforces.com/contest/1027/submission/42496525

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

            I tried to reduce your binary search iterations via coordinate compression and now we have 42497321 — MLE Test 46.

            To make testing easier (instead of local testing on random large instance), you can make mashup with only this problem, and change TL and ML to whatever you like.

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

So What's test 9 problem C?

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

    No idea, to be honest. Just 25000 testcases of size 40 with random sticks.

    I can provide you with generator and command line arguments if you need it.

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

      Nah,I'll just cry in corner,Thanks anyway for the contest and nice problems

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

        Forgot to sort the array :(

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

      I have a feeling the time limit constraints are too strict. My java solution (equivalent of an acc C++ soln doesn't seem to pass..) Are the problems just meant to be solved in C++?

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

        Two problems with your solution (that I also faced during contest):

        First is your frequency arrays. You're recreating your freq array for every test case. If the number of test cases is 25,000 recreating that array so many times is very time consuming. You should instead reuse the frequency array and only clear an element the first time you access it during a test case.

        The second problem is your output. You're using System.out which is much slower than using a PrintWriter. But that'll still get TLE. Instead, you should append all of your output to a StringBuilder and print once after doing all test cases.

        I agree it's kind of annoying but sometimes you need to do annoying things to make things pass in Java.

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

          Thanks for your help! I'll try the suggestions

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

One of the weirdest contests I ever seen !!! Solved C and D and couldn't solve A nor B !!!

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

whats test 5 in C ?

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

    166666 testcases with lists of size 6: 3 pairs of equal lengths. I can provide you with generator and command line arguments if you need it.

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

    Minimum difference might not give optimal answer.

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

In C is it not optimal that we always choose the two sides which have minimum difference and for those differences (of length and breadth) which are equal check for them explicitly whose given ratio (p*p/s) is smaller ?

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

    not just the ratio.. you need to minimize x/y + y/x

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

      Yeah but this would be minimum when x is closest to y (obtained by differentiating) and for those whose difference b/w x and y is same we compare which of ratio (x/y+y/x) is smaller. Did i miss something ? I guess i increased conditions and computation but still could not figure out why WA. Though your code make sense. Thanks !!

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

        if you fix one of x or y.. then you can say that the other one has to be closer.. but that does not mean that the closest pair will be the answer

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

          only adjacent ones need to be checked. we need to minimize (a/b) + (b/a) where a and b are the 2 sides. define x = (a/b), then we need to minimize x + 1/x which is done when x = 1. So checking only closest elements is sufficient

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

            Actually what he said was that finding two closest (with min difference) does not give required answer.

            For eg 18/2 is 9 and 500/100 is 5, smaller than 9 despite of having difference as 400 which is greater than that of former one.

            Sorting in this case worked because for a given element if we want to check smallest possible ratio then we want just smaller one because all others will give a higher ratio (mistake i did by differentiating by keeping one variable fixed) because in this case we are talking with respect to particular element a[i].

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

      Could you explain how does one get from

      p * p / area

      to x/y y/x ???

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

        p*p = 4*(x^2 + 2xy + y^2) area = xy divide them, 4*(x/y + 1 + y/x) so you have to minimize x/y + y/x.

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

    I was thinking about 1 1 2 2 15 15 20 20...

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

    f(x, y) = (2*x + 2*y)^2/(x*y) f(1, 2) = 18, f(100, 109) = 16.03

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

    this site plot functions with 2 variables, it can give you a visual vision for the function varaitions, hence you can find it's minumum.

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

Didn't solve C... I'm feeling like a fool...

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

What's test case 23 in D and test case 9 in C ? :/

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

How to solve E?

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

    An observation is that when the color of the first row and the color of the first column is determined, then the color of the whole matrix is determined, and the maximum area of the rectangle of the same color equals to the maximum number of consecutive grids of the same color in the first row multiplies the maximum number of consecutive grids of the same color in the first column. Thus you can do a dynamic programming computing for each k, how many arrays of length n such that the maximum number of consecutive grids of the same color equals to k, and then easily find out the answer.

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

      When u get the observation but don't attempt it more after seeing the modulo (fft).

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

        You don't need FFT, it's a very simple dynamic programming problem.

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

      I have a question, can you help me? qwq If the first element of two arrays is different, how do we merge the two arrays? For example: n = 2, and k = 2(k is the maximum number of consecutive grids of the same color in array) we can get: "00" "11" but I can't understand how to generate the matrix?

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

I faced an issue in this contest ! Read about it here(https://mirror.codeforces.com/blog/entry/61298) and present your views !

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

Is F binary search on day and apply halls theorem for checking the validity in the binary search ?

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

    no~~

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

      Why not? It works although one has to be careful about implementation — I got several TLEs before getting it accepted.

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

    You can try mentos theorem.

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

      What is mentos theorem. Couldn't get anything through google search. It will be helpful if you can provide any links.

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

damn...

This submission was made 20 seconds before the end. I started about 20 minutes late into the contest and I wrote the code for G in a real hurry so I didn't even know the code was going to pass a lot of tests.

I hoped for a miracle but guess that's not happening today :(

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

What's test case 23 in D?

I was considering it as graph and finding the sum of minimum costs in cycles in different connected components, but got WA on test case 23.

Edit : It was a minor bug in implementation

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

    Your solution fails on

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

      Isn't the answer 1 in this case (the rat will come in the first room sooner or later so placing the trap on first room would work) or I'm missing something ? (My code is outputting 1 but it also got WA in test case 23)

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

      My answer is 1.

      And I think that's correct :|

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

    you need to calculate minimum of costs which are part of a cycle.. not its branch

    1->2->3->4->2.. here you have to consider 2,3,4 and not 1 bcoz 1 is not a part of the cycle

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

      I am doing the same... I am first isolating a cycle and considering the minimum cost of elemenents in the cycle...

      Also I'm taking use of the fact that there will be exactly one cycle in a connected component(considering it as undirected graph).. isn't it right?

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

        yeah but see the test case in which you got wa.. there might be something wrong in your implementation

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

    Just realised now that I can see that test case :|

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

How do you solve D? I realized the problem was much harder when it wasn't a tree.

UPD: Nvm you just dfs from two roots

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

    Find minimum Ci in every cycles and add these minimum to answer.And note that cycle can be with one node(self loop).

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

41776119 It gave WA on test 5 in C. I tried to minimize l/b + b/l. Although I later ACed it by hardcoding the functions for area and perimeter, I still couldn't figure out my bug in the first approach. Any idea what's wrong? Thanks in advance.

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

    Not completely sure, but the problem seems to be the line

    maxx = (ll/bb + bb/ll);

    maxx is an integer, and ll/bb+bb/ll is a float/double.

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

      Damn, that was the bug. Spent an hour trying to debug it. Anyways, thanks a lot :)

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

        actually i checked it on my computer and the problem is with this line: int maxx = LLONG_MAX

        xcode is smart enough to warn about wrong conversion: Implicit conversion from 'long long' to 'int' changes value from 9223372036854775807 to -1

        ideone example

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

          Actually I have used #define int long long, so I didn't face that problem.

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

i was getting wrong answer in problem b in java because i was using Math.ceil() function. can anyone help me why this is happening ? failed submission http://mirror.codeforces.com/contest/1027/submission/41770896 Accepted submission http://mirror.codeforces.com/contest/1027/submission/41791415

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

    Same, I used ceil function in c++ while in contest and it gave me wrong answer.
    Contest Submission- http://mirror.codeforces.com/contest/1027/submission/41788167

    Just removed ceil and used if else instead and it got accepted. http://mirror.codeforces.com/contest/1027/submission/41800586

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

      using / on 2 ints will give answer in int. i.e ceil(5/2) means 5/2 is 2 so ceil(2) gives 2. If you want to use you can use 1.0*x/y this will give correct ans but still may have precision issues of very large values. so it's best to use custom ceil function.

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

        My variables in ceil function were double not ints. Double variables shoudn't cause any problem I guess.

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

          nn^2 can be very large so it causes precision issue try using long double that should work.

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

          In any case it's not adviced to use double unless you can't do it with int.

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

            Yes, long double worked. Thanks for the help! Should've tried using long double while in contest.

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

I was constantly getting logged out of my account during contest.Don't know what it was because of my slowed down wifi today or something else.It ruined my contest today

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

What is the complexity of memset in C++..? I read it is O(Size of Array to be initialized) but in Problem C, I used memset for an array of size 10000 in all the testcases and it passed all the pretests..How?

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

    The memset function is highly optimized by those professional engineer, it's very fast.

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

    There are some hardware acceleration inside menset(), for example, it can be done parallelly. Also you can set 8 bytes at a time if you are on a 64 bits machine

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

A solution for problem C:

  1. Since it needs to form a rectangle, we only pick those sticks which have a equal-length pair.
  2. Sort these sticks, check every adjacent stick pair to find which one has the smallest P^2/S.

This works because the smallest value must appear in the adjacent pair, here is a proof:

1.Let these two stick pairs have length a and b, minimizing P^2/S is equal to minimizing a/b + b/a.

2.Suppose b = a + d, d >= 0. a/b + b/2 = a/(a + d) + (a + d)/a, get derivative for d, it's positive in our concerned area, that means the minimum value must appear in the adjacent pair.

I didn't notice the rectangle constraint in the first glance, found it unsolvable. :(

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

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

    You could have time travelled into the past (smaller rank) if you spent less time looking at the standings xD

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

      Dear Mister,

      You can notice that I solved C at the last minute.

      So don't go around and assume that I spent it looking at the standings. ^-^

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

How to solve F?

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

I wonder why my solution for problem C runs 1840ms but others solution runs 421ms???

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

    Because in every test cases you are clearing cnt array which is O(T * sizeof(cnt)).

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

    You're resetting cnt every test case even when n=4. 250000 testcases with n=4 and your solution should give tle.

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

    It is not because of memset.

    Firstly, the complexity of the other's solution is not O(T nlog(n)) but it is something like O(106log(106)), and your complexity is not O(Tn) but it is O(T 104), and here is the problem, because when T = 250000 and n = 4 for each testcase, then you will iterate, for each testcase, 104 times while you could iterate over 4 elements atmost (n = 4).

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

      I solved it in O(T*nlgn) but still the solution was hacked by the test case that you mentioned and the verdict of the hack was TLE . I can't figure out the reason as I am only doing O(nlgn) operations in each test case . My submission

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

        I have just finished testing your submission and the problem was with big I/O data. So, you just need to convert cin/cout in your code to scanf/printf.

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

          Thanks a lot! I was really unable to find my mistake.

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

            Welcome :)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it +3 Vote: I do not like it 
              ios_base::sync_with_stdio(false)

              Will adding this line solve the problem or I have to use printf and scanf ??

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

                On my computer, scanf/printf were faster 3 times than ios_base::sync_with_stdio(false) (the last one took almost 2111 ms but the first took 766 ms almost), but yes it will solve the problem on Codeforces.

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

The time limit set in the today's contest was very stringent for python guys. I was getting a TLE for O(1) solution, whereas when I used fast I/O after the contest, my code passed all the test cases by just 1 millisecond and later on it was hacked by someone and the verdict was TLE. It would be great if you could increase the time limit by one-two second, for people coding in python. Since, everyone knows python is 5 times slower than c++. As increasing the TL by one second, won't allow any O(n) or above solution to run. So, if possible do it for both B and C.

Also, I wished to raise it as a general concern as well. Every time I code in python there is some TL issues. Why don't you guys provide a X5 multiplier for python similar to other coding sites? As it would encourage the use of python in CP. If the problems are specifically designed for c++, just tell it before the contest starts.

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

    Python gets other advantages such as many inbuilt functions big integers etc. So it's a trade off.

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

      I completely agree with you, but don't you think that there should be at least an AC in every programming language allowed, which passes the given time limit by a comfortable margin?

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

    Why would you necessarily want to encourage the use of Python in CP? Lots of contests don't allow the use of Python (ICPC, GCJ, etc.) or it's completely infeasible to solve some of the problems in Python (FHC), so I don't see why CodeForces should encourage the use of Python in any way.

    EDIT: Made a mistake, ICPC and GCJ allow Python. However, for ICPC, solutions are only provided for C++ and Java, so it is not guaranteed that one can solve a question in Python. Same is probably true for GCJ now that it is judged on their servers rather than running input on our own machines.

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

      Python is now allowed in all the contests like ICPC, GCJ and FHC. I didn't mean that I specifically want everyone to code in Python. If it seems so through my words, I am sorry. But what I meant is, if someone gets TLE on a perfect logic, then his interest goes low, even though he might be good at CP.

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

Can anyone explain why i was getting TLE in C when dealing with double and got AC when dealt with integers AC ....TLE

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

How to solve problem D ?

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

    In a circular path of the mouse, we should place trap in the room with minimum cost. This same trap will work for those rooms also from which you can enter this cycle. Summing over all such rooms( corresponding to each cycle ) will give the answer.

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

      what to do in this case ?

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

        So you have the cycle 1-2-3-1 in this. Pick the room with minimum cost in this cycle (say room x). Also you can reach to this cycle from 4. This covers all the nodes. Answer will be cost of x.

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

    Hint: When a loop is found, we can travel around the loop again to get the minimum cost.

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

Could anyone provide a hint for G? Also, I know F is about Hall's theorem, but how to implement it?

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

    Hint for G — you can calculate answer for each divisor of m independently.

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

    Formula for G: Let ordp(x) be the smallest positive integer k s.t. xk ≡ 1 modulo p. Then answer is

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

Hey can someone help me understand what is wrong with my solution? I am checking each adjacent numbers that are >=2 using a map and i am getting wrong answer on a list on the last test https://mirror.codeforces.com/contest/1027/submission/41804552

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

    float hasn't got the necessary accuracy. Change it to double/long double. See this test:

    1
6
9998 9998 9999 9999 10000 10000
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yea this was the problem. I got AC now thank you very much!

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

        Also don't use float unless absolute necessary. instead of a/b<c/d you can use a*d<c*b.

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

In problem C, is it mentioned somewhere that we have to minimize the length of sides as well after minimizing p^2/S. I am asking this because I submitted a solution where printing a larger side for the case when all sides are equal is giving wrong answer while if we take the smallest side Accepted is given.

Links to submissions:

Wrong Submission

Accepted Submission

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

    If you look test 3 of your WA submission, you will see that you are printing numbers that doesn't belong to the input array (the judge says "wrong answer Given lengths aren't present in the input list for list 5").

    You can check that minimizing is not necessary in this submission. I used your code but I didn't update the answer if I already found one, and it got AC.

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

      I too initially thought that the sides might not be present but when I checked (Look at this submission) I found the sides are in fact present in the list.

      PS: My previous submission said that the give side is not present in list 5. So I tried to print yes when whenever I found that side to check it.

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

        Yeah, that's weird, but minimizing the lengths is not really necessary (I updated my previous comment with a submission link). I really don't know what's going on :P

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

          Yeah that's the point. It is clearly mentioned in the question that you cant print any of the possible values. But they are accepting only the least one.

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

            The submission I posted in my comment prints 5314 5314 5314 5314 for that input list, yours prints 2 2 2 2, and the judge says both of them are ok, so not only the smallest side is considered as correct. Maybe there is some kind of bug for some values. I'm sorry that I can't help you with that!

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

When does system testing start?

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

    it hasn't started even now.. Will the submissions won't be check at system tests(pretest + hacks) this time?

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

When will the rating be updated ?

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

When will the ratings change?

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

Can someone please provide the 5th list of test case 3 in C. I am unable to spot the error in my code.

Error : wrong answer Given lengths aren't present in the input list for list 5

Code : My Solution

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

    You don't need the break in your loop. You don't finish reading the current list before proceeding to the next one.

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

      Thanks a lot !! :)

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

      I made the same mistake using the break in order to avoid TLE,it is the first time I meet this type of input which one testcase includes n tests.

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

        This is the common pattern on codechef!!

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

Why system test doesn't start right after open hacking phase? Contestants always need to waiting long time for system test and it's really boring and annoying...

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

    you can calculate by yourself,according to the standings and your points

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

      before system test, standings are not real standing. I know how to calculate rating change, but that's not the point. we can know real contest result only after the system test. I want to know the real result, not the expected rating change.

      and I really can't understand the reason why system test couldn't start automatically. I want to know the reason why we must need to waiting long time for starting system test.

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

What happened with the system test? The next contest will begin in 8 hours but the system test of this contest disappears.

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

When will the system test start?

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

The system tests are started!

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

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

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

when the ratings begin change?

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

How long will take it to calcuate the rating changes?

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

Why the rating changing still can't be seen??

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

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

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

I have solved C bt cant come up with a solution for B.. plz help!!

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

Rating has improved.I am happy.

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

The contest has helped me a lot !!!! thank you very much :)))

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

In Problem 1027F Session in BSU, Some people AC this problem by using Hungary Algorithm I can make the data to Hack Hungary Algorithm's solution (eg:41789514) How can I give my data to Codeforces? I only don't hope these people are mislead by Hungary Algorithm Sorry.I am not good in English,Can you get my meaning?

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

I am getting RTE on test case 45 in D Anyone help Submission link : https://mirror.codeforces.com/contest/1027/submission/48291955 Using normal dfs to detect cycles

→ Reply