300iq's blog

Codeforces Round #500 (based on EJOI)
By 300iq, history, 6 years ago, translation, In English

Hello everybody!

On July 28 and 30 will take place tours of EJOI — individual programming competition for juniors, held under the rules of the International Olympiad in Informatics.

EJOI consists of the most interesting and hard problems that are proposed by a wide community of authors, and that is why we decided to give you an opportunity to crack the complete problemset of the contest. During the second tour of Olympiad, we are going to conduct a rated Codeforces round based on problems of both days of our Olympiad.

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of EJOI (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

The round will happen at Jul/30/2018 11:15 (Moscow time) and will last for 2.5 hours. There will be 6 problems in each division.

The tasks of the round were invented and prepared by tourist, PavelKunyavskiy, niyaznigmatul, 300iq, GlebsHP, pashka, qoo2p5, VArtem, demon1999, Flyrise, ifsmirnov, isaf27, yeputons, cdkrot.

Also thanks for testing never_giveup, vintage_Vlad_Makeev, izban, GoToCoding, Egor, doreshnikov, Sert, disa, wrg0ababd, craborac, budalnik.

And, of course, thanks to MikeMirzayanov for great systems Codeforces and Polygon.

Good luck everybody!

UPD: Congratulations to winners!

D1:

1) Um_nik

2) LHiC

3) dacin21

4) ksun48

5) Swistakk

D2:

1) UnproductiveGuy

2) WaldarDoppen

3) IHaveHir

4) cly_none

5) Shadi.Gh

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

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

Please translate to English

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

    On July 28th and 30th, EJOI tours will take place — a personal programming competition for juniors, taking place according to the rules of the international schoolchildren's competition in informatics.

    EJOI is made up of the most interesting and complex tasks that were proposed by a large team of our authors, therefore, not wanting to deprive you of the opportunity to break your head over the problems of the full problem of the network together with the contest participants, we are going to run a rating round of Codeforces, based on the tasks of both rounds of the Olympiad.

    In this regard, we ask all members of the community who are going to participate in the competition, show respect for themselves and other participants of the competition and not try to cheat in any way, in particular, clarifying the tasks of the participants in the competition in Innopolis. If you learned any of the tasks of EJOI (by participating in it personally, from someone from the participants or in some other way), please do not write a round. We ask the participants of the Olympiad to refrain from public discussion of the tasks. Any violation of the rules above will be an excuse for disqualification.

    The round will be held on Monday, July 30, 2018 at 11:05 and will last 2.5 hours. In each division, six tasks will be proposed.

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

    Sorry, it is translated now.

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

When you click on EJOI, it writes no such blog entry.

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

23 coders are here.

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

Wish there will be no internal errors, because... well... 500...

#iykwim #okthisisabadjoke #imout

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

isaf27 is among the names of this round while peltorator is among the names of the last round :D

upd:my fault,isaf27 is also among the names of the last round

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

Congratulations everyone on the 5th century of contests here on Codeforces :) :D

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

    5th Century of Codeforces round, not Codeforces Contest. :)

    As educational rounds are also Codeforces Contest but not Codeforces round. :)

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

Let's hope for a nice 500th anniversary!!

Happy 500th round, Codeforces!!!

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

Be scared, be very scared.

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

very excited to join a contest prepared by all of these legend.

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

A not bad time for Asian users :) ?

Hey, maybe the contests based on OI have more unusual time which is not in evening or night? :P (Like Moscow Open Olympiad (Round #469))

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

    HAHA!You are so funny.

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

      I can see by your cf icon you too have refined taste.

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

    Yeah,it is so tiring to take part in contests at midnight,especially when you need to go to school tomorrow

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

    but tomorrow's div 3 will start at night again ...

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

For those in US wondering how the hell to wake up at 4 AM, let me give you some advice:

Just stay up

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

    3 AM here in Colombia :)

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

      Well, did you follow this advice? Somehow I actually managed not to sleep, hope I can solve more than one problem :D

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

        haha, no, I went early to bed. Im not sure if not to sleep is a good idea haha

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

Is it emmm, no no nothing.

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

Should I skip my school to participate?

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

    If u can, why not?

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

    Well, I just did this in Round #469 which has the same beginning time ┑(￣ _ ￣)┍

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

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

    Херня какая-то

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

      Yes, I made some mistakes, sorry. Next meme gonna be better ;) ________________________________________________________

      Our greatest glory is not in never falling, but in rising every time we fall.

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

        Don't worry, here at codeforce we like to say "practice makes perfect", whether it is segment tree or shitpost.

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

another round with tourist's problems ... ಠ_ಠ

God bless me ...

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

Have now made my schedule free for Codeforces #500! <3

The best feeling ever (Despite it being at 1:30 pm here, on a Monday!)

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

I honestly expect quite a lot of people seeing EJOI Day 1's tasks from contestants, which messes with the standings by having an unfair advantage. Expecting everyone in an online competition to play fair isn't enough.

Either make this contest unrated, or change Day1's tasks with original ones.

Leaving such an obvious method for cheating unchecked certainly shouldn't happen for Round #500, which instead should be celebrated as a milestone in fair competitive programming.

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

    I think that the main purpose of the contest is to solve interesting tasks, not to earn ratings. We will try to do everything to fight with cheaters, but I don't think that cheaters can ruin the contest. Just enjoy the tasks!

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

    The onsite contestants were asked to don't disclose the problems.

    Anyway, there are ways to cheat in codeforces rounds even without onsite competition present. So we hope, that most people on codeforces just simply don't cheat.

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

    I really like the tone of this comment, "Do this, do that, it should be". Should we also buy you a Ferrari and a nice house?

    I think this team of experienced contest authors together with Mike can figure something out, don't you think?

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

300iq dude you gotta chill out. You've been included in lots of rounds recently.

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

I wonder if this contest would be too difficult for Div 2 contestants.... That's because actual EJOI is for pro junior coders..

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

    I think that first 2 or 3 problems won't be from the EJOI, because A, B and sometimes C are very easy and I think there aren't that easy problems on EJOI. Please correct me if I am wrong.

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

feeling good to see tourist in problem setters...i think this contest is going to be more interesting than other contest........

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

upvotes for tourist.

UPD1: Now downvote for starboy_jb.

UPD2: don't do anything with this comment.

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

14 writers just for a single contest!

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

I will miss this contest because I have to take part in HDU 2018 Multi-University Training Contest 3contest is here...

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

?detaR tI sI

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

Happy round #500

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

What controls registration time? We can register in Educational round but not in #501 yet.

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

So many writers? Pfft. I hope this won't be disappointing. Stupid writers always disappointing. I wish you all minus rating changes. F*** y'all

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

I hate 10 minutes delay :(

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

10 min delay :'(

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

What's the score distribution?

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

As a result of 10 minutes delay, I will miss my supper.

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

    same here, I just want to participate to contest until end of my lunch time, which means 55 minute of the contest. Now they decreased it to 45 minutes by delaying it :(

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

After getting a %l64d error, I wasn't able to submit my code on problem A, it always said that I've submitted exactly the same code before, even if I changed things in it. I also wasn't able to ask questions on the problem.

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

    It may be caused because I registered in the 10 minutes delay time.

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

When you solve A,B,C then leave cuz you don't have anything to do. :')

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

I guess I'm back to div2 again...
How to solve B?

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

    Represent each row and column as a node, and connect a row and column if cell (x,y) exists. Answer is number of connected components minus one.

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

    Make a bipartite graph (the left side of the graph is for ri and the right side is for ci, edge (ri, ci) exists if we have element (ri, ci)), then count the number of connected component.

    This solution works because if you will be able to make element (ri, ci) if you can reach node ci from node ri.

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

    DSU on rows and columns. When you're given a cell, you merge the x and y coordinates. The answer is the number of components in total — 1.

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

      szawinis Why are you doing merge(x,n+y)? A detailed explanation of your approach would be really helpful..

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

        Well, that's just a way of separating the x and y coordinates while keeping them in the same dsu array. Since the first n vertices are taken up by the x coordinates, we can just append all the y coordinates by doing n+y.

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

For div1A you can prove it is always optimal to make all the x's a contiguous subarray when the ai is sorted right

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

    Yeah, so sliding window will work.

    Note that when you're doing a proof you may get stuck at one point while trying to induce a contradiction, but you should also pay attention to whether the y's form a contiguous subarray as well.

    If you assume that neither the x's nor the y's make a contiguous subarray, you should be able to easily induce a contradiction of the minimality.

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

    Yes, because you can make the x's contiguous without affecting difference between the highest and lowest y (can even decrease it), resulting in difference between the highest and lowest x being decreased (or not changed at least).

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

How many cases are there for Div1D?

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

Div 1:

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

I tried C with a DP approach but got WA on test 8: 40959527.

Can anyone point out my mistake?

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

    Please, explain what is d[i][j][0] and d[i][j][1] in your solution (we are not telepaths)

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

      Alright. Should have some clarifications.

      In this, I declared dp[i][j] as the minimum time used to build j houses, using hills with 0-based-index not higher than i.

      dp[i][j][0] is the minimum time to build j houses without building a house at the i-th hill, while dp[i][j][1] is the minimum time to build j houses, including one at that hill.

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

        You need to update dp[i][j][1] with minimum of dp[ [0,i-2] ][j-1][1]

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

        I haven't found the mistake yet, but I met difficulty when I was trying to solve it in your way which uses dp[i][j][0] and dp[i][j][1]. So I tried to use dp[i][j][0] ,dp[i][j][1] and dp[i][j][2]. dp[i][j][0] is the minimum time to build j houses without building a house at the i-th hill or i-1-th hill. dp[i][j][1] is the minimum time to build j houses, including one at that hill. dp[i][j][2] is the minimum time to build j houses, including one at i-1-th hill.

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

          Could you please explain the transitions in your solution?

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

            I omitted a dimension of the array, maybe this cause my solution hard to understand. f[i][j][0]=min(f[i-1][j][0],f[i-1][j][2])is obivious. f[i][j][1]=min(f[i-1][j-1][0]+max(0,a[i-1]-a[i]+1),f[i-1][j-1][2]+max(0,min(a[i-1],a[i-2]-1)-a[i]+1)) Transition from f[i-1][j-1][0] means that you only have to lower the height of i-1-th hill from its origin height, which costs max(0,a[i-1]-a[i]+1) hours. Transition from f[i-1][j-1][2] means that you have to lower the height of i-1-th hill from the height which had been lowered when calculating f[i-1][j-1][2] and is already min(a[i-1],a[i-2]-1), so this costs max(0,min(a[i-1],a[i-2]-1)-a[i]+1) hours. f[i][j][2]=f[i-1][j][1]+max(0,a[i]-a[i-1]+1), because there is no other choice. I finally realised my poor English when I was trying to explain my solution... Hope you can understand it.

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

        The first bug I see: while counting d[1][1][1] you don't consider a case when the first (0-th) hill is lowered. Can you please determine if d[i][j][1] means that you must take the i-th hill or that you can take the i-th hill?

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

          Looks like I do have trouble clarifying stuffs... My apologies.

          dp[i][j][1] means i-th hill must be taken.

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

            I think the bug is this: when you take the-th hill you have to lower the next hill. But then you forget about it and don't put it in consideration when you take the d[i-2] value.

            You have to consider the first i hills in isolation. For example see my solution (but here 0 means that we don't count the i-th hill, and 1 means that we can count or not count it).

            Solution

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

    Finally, mistake found — a stupid one I must say.

    i64 dp[5001][2500][2]; (It should be 2501 for the second dimension).

    Like, I've neglected Carrays for a very long time (only using it today since nested vectors didn't suit in 1s TL), and then this happened...

    Still thanks for all the support! rembocoder Tutis ouuan

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

      I always use dp[5010][2510][2] in this case.

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

        Heck, I should spend sometimes revising Carrays again, just to have the flow in my head. Such issues are straight intolerable :D

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

I can finally see my rating change before going to sleep as a Chinese!

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

    And how beautiful when it is going to be a great rise.

    Have been monitoring your progress, and I can only say congrats! ;)

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

    Codeforces's progress proves the revolution successful and makes itself better!^_^

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

    Maybe I won't be able to? The rating change hasn't been shown yet.

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

      Now I can see the rating change.

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

Which problems were from EJOI. The ones from Div.1?

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

Wow, had E coded for last 8 minutes but wifi went out I guess, and iPhone took too long to recharge so not submission :'(

EDIT: :'(

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

    Cheer up T_T..

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

    It seems that you would have won this round if this didn't happen. So sorry.

    But still, congratulations on becoming nutella :)

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

    Ehm, I spent some 20min going in wrong directions on E, then wasted a lot of time on D. About an hour after the contest, I decided to revisit E and figured out I can take Euler cycles in about a minute... and the rest is straightforward.

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

My Modest Solutions

A-Piles with stones
http://coolforces.blogspot.com/2018/07/1013a-codeforces-piles-with-stones-solution.html

B-And
http://coolforces.blogspot.com/2018/07/1013B-codeforces-And-solution.html

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

Why cannot solve AB-Strings by greedy T_T...

Was I missed something?

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

    How was your greedy, exactly?

    Also, please keep in mind that the commands with string are linear in time complexity, in case you implemented them directly on your solution.

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

    Yeah, I also did not understand why does not it work to just break an "ab" in one string and a "ba" in another. Though I just saw the number of OKs and the number of WAs and decided not to think further =/

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

    For a test like:

    ababa
b

    It's better to make the number of cuts in the two strings more equal. For example, we balance them on the very first move:

    ab|aba  -->  aba         ab|a  -->  aa           |aa   -->  aaa
|b           abb  ;      a|bb       abbb  ;      a|bbb      bbb
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Oh.. I think this was it! Thanks!!

      so the first time pre-processing was that I was missing

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

      You have 6 total letters in the input data and 8 in the output, seems like you've meant:

      ab|aba  -->  ab|a  -->  |aa    -->  aaa
|b           a|bb       a|bbb  -->  bbb
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks, fixed!

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

          Uhm, are you sure? If you consider it correct, I don't understand the format you've chosen for it.

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

            Argh... sorry! Another try above. Yeah, now yours and mine look equal.

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

              Okay, seems alright now, thanks for the test

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

Everyone solved D as DFS!!! I never thought of it

Can someone explain it to me??

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

    Let's present a table as bipartite graph. N vertices for rows and M for columns. Then an element means an edge in this graph. If we have a path of three edges, we can connect the ends of this path with an edge. This means that if we have a longer path a_1, a_2, a_3, ..., a_k, we can at first connect a_1 and a_4, so the path becomes shorter, and so afterwards we can connect a_1 and a_k. So if two vertices are connected, then we can draw an edge between them already. Thus we only need to buy edges to make all the graph connected, so the answer is the number of components — 1.

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

that moment when you spend 1 Hour try solve D then you realize that you misunderstand problem because you are shit in English

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

How to solve Div2 C? tried a lot but could not get it :(

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

    I approached it with greedy solution — minimize one dimension of the desired rectangle as much as possible.

    To achieve that, we will sort 2 * n coordinates, and choose n consecutive coordinates in the new sorted array to be coordinates of the same dimension (either x or y, doesn't really matter). Technically, we'll keep a sliding window and try all possible n-length consecutive subarrays.

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

I solved Div. 2 B in 16 min. but then accidently resent it after one hour and a half. Both of them are correct Which solution will be rated?

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

18 and 43 tests in B kills all submissions

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

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

For the problem D in Div.1, Both ko_osaga (submission) and Konijntje (submission) got accepted. But for the input below, ko_osaga and Konijntje's outputs are different.

<< INPUT >>

b
aabaaaaaabaabbbbaaaaabbbbaaba

<< ko_osaga's output >>

6
1 16
2 1
2 7
13 6
7 15
17 8

<< Konijntje's output >>

7
0 10
9 18
17 3
2 15
11 0
0 6
2 0
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    hmm, I think it should be 6 for this case.

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

    you should join codeforces team

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

    My answer also has 6 actions.

    When a solution considers a number of cases, there can be quite a few of them (mine, for example, has a total of 18 calls to the main solution function, just to be sure). So, if one of X such cases is solved incorrectly, informally, it is X times harder to catch it with tests. So it is understandable if something like that slipped through.

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

      I made an identical TC in contest to test my code. It's a basic one, and if I was a tester I won't tolerate it. (But still I appreciate all setters effort!)

      FYI, smaller countercases :

      a
bababab

      Answer is 4.

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

    Nice.

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

a sudden difficulty rise between div1 C and D .

Means we need code faster again

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

Guys there was some cheating going on today. Guys like n00bie knew the questions beforehand and hence achieved a good rank. What a disgrace!

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

    I guess I'll just repeat Jatin.

    Get a life.

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

Can anybody tell me how to solve div1D?

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

    Consider all substrings ab and ba: the switch positions where the two consecutive letters are not equal. Note that each cut can remove at most one switch position. Now, if we cut ...a|b... in one string and ...b|a... in the other, and swap the prefixes, we remove two switch positions simultaneously. However, one swap can remove no more than two of them, one from s and one from t.

    What's left to do when, for example, s has no switch positions and t has X > 0 of them? We can remove one switch position from t with one swap. But we can do better: cut the string t so that approximately half of these positions go into s. Then we can again remove two switch positions per swap, which is twice as fast.

    In fact, we can start by counting the number of switch positions in s and in t (let them be X > Y), and if they are not equal, make the first cut so that (X - Y) / 2 of them go from s into t, making their count approximately equal. After that, proceed with the greedy solution which removes one switch position from s and one from t in each swap.

    What's left is to consider which string will turn into aaa...a and which into bbb...b, and formalizing the "approximately equal" above. We can just solve for a few  ± 1 cases and take the minimum to be sure.

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

    Don't. Solve E instead.

    Seriously, if it looks simple and there are few correct submissions, maybe the next problem will be more doable — or if it isn't, at least it won't give you a headache.

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

      I found E pretty easy for 2500 pointer, but D was even easier, but just tedious with implementation. For me doing E was better decision than D, but you can't simply discard such problem a priori, it wasn't that bad.

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

        I agree that D was easier than E idea-wise, but if the implementation is tedious enough that there are only 20 correct submissions (while 180 people attempted) in a 2.5 hour contest, and if the first correct submission came after 80 minutes... that implementation is pretty brutal. I think if D and E were swapped, there would be more correct submissions on that D than on that E.

        I'm not talking about discarding it a priori, but about recognising that it's not worth spending a lot of time on — either from experience, from looking at the statistics or trying it and seeing that there are a lot of cases and it's easy to miss some (so easy it happened to the authors, even).

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

editorial?

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

Rating should be updated now But it has been 3 hours since ending and rating haven't been updated even

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

    Seems like it's not that easy this time. Like they also rolled back the rating changes for round 499.

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

a sudden disappear of round499 rating record?

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

whats wrong with cf 499 round??

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

Is there any problem with previous round ( Round # 499 ) rating !

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

Editorial?

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

For people who came up with D in contest, how did you come up with solution to a problem like this? Did you see similar problems or did you figure it out from writing out the pairs/graphs by hand? I understand solution, but coming up with it seems like total magic to me.

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

    Well, yes, associating rectangular grid with bipartite graph is a known thing.

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

      congratulations man. Only your hatters will downvote this comment.

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

    It makes sense that we need to have all (x,y) values in the same connected component, if all cells that we make for free are (x,y) where x is from set R and y is from set C and R is set of all x's and C is set of al y's in that component.

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

A

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

Suddenly noticed that both the Announcement and the Editorial aren't linked to any contest...

And the result is no contest materials link in the contest Dashboard or problemset

UPD: Fixed.

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

The comment is hidden because of too negative feedback, click here to view it

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

Where can I find the tests to the output-only problem from EJOI?

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

when are u going to upload editorial??

→ Reply