Theo830's blog

Codeforces Round #747 (Div. 2)
By Theo830, 3 years ago, In English

Γεια σου (Hello), Codeforces!

Dremix10 and I are glad to invite you to the first Cypriot round Codeforces Round #747 (Div. 2) which will take place on Oct/08/2021 18:05 (Moscow time). Note the unusual start time of the round. As usual, this round will be rated for participants with rating lower than 2100.

Problems were created and prepared by Dremix10 and me. We tried to make them interesting, with short and clear statements. We hope that you will enjoy them!

I would like to thank:

You will be given $$$6$$$ problems (and one subtask) and $$$2$$$ hours and $$$15$$$ minutes to solve them. Scoring distribution will be announced later.

Good luck and have fun!

UPD1:

Score Distribution: $$$500-1000-1500-1750-(1000-1500)-2750$$$

UPD2:

Editorial

UPD3:

Div2:

  1. A-SOUL_Diana

  2. End.

  3. tuihuademing6

  4. OguriCap

  5. PATOLOVE

Div1 + 2:

  1. SSRS_

  2. tourist

  3. 244mhq

  4. hitonanode

  5. A-SOUL_Diana

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

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

Hoping for a good contest :)

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

nvm, added in the blog.

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

    Usual — 150 min

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

    And also notice the unusual duration of this contest (usual time + 15min)

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

    Ahh Thank you so much YPK.

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

    If you'd just added this to your original comment everyone would know what you are talking about without going back through the revision history.

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

As a tester, I found problems are new and clear.

UPD: Problem D found copied. I take my words back.

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

As a tester, I hope you will enjoy the problems as much as I did :)

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

    As a Participant I'll tell my feedback after the contest!

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

      Till then, your feedback wouldn't be much useful, I think.

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

As a tester, enjoy!

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

Roses are red
Energy is produced by nuclear fusion
The contest is great
As a tester, I want contribution

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

    Well, let's hope all the problem statements are not quatrains like this one.

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

does one subtask means that one problem will be divided to easy and hard versions ?

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

I wish this round will be my last round in grey :)

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

Will probably get of of grey.

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

I will be impatiently waiting for the start of the round!

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

As a first feedback giver, I can say that Theo830 worked really hard to make an interesting and enjoyable round for you guys!

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

Why is it such a strange time

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

Hoping for a good contest.

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

I don't like subtask.

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

I hope it will be my last contest in grey ^_\, wish me luck.

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

18:05 in blog is just Moscow time right?

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

WoHOOOO, contest after a long time!

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

    I just want to add that "this round will be my last round in grey" is more ambitious than "I will become pupil after this round". :)

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

    Why are all of your memes light-hearted?

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

What do you mean by first Cypriot round ?

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

    Both setters are from Cyprus. And as they mentioned, this is the first ever fully Cypriot round.

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

Hope the long queue will be ended before the contest...
Best of luck to everyone!!!

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

Moving on from Green tonight...

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

system is testing so slow :( hope it won't cause unrated round

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

    May be it will be postponed

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

    No it's not? The system testing is excellent in terms of speed.

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

This is so weird. I couldn't be able to solve any problems of the past 3 contest =(

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

    That's because of your bad profile picture.

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

I AM NOT ABLE TO SUBMIT IT SAYS AM NOT REGISTERED

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

    You should register before the contest begins next time or 10 minutes after it starts, sadly you can't compete now but you can solve the problems after the contest ends!

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

Three lessons I've learned today:

  1. I am stupid who can't solve any problem with counting
  2. E2 is much harder than F
  3. tourist is god
→ Reply
»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

speedforces. D was nice though.

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

I solved A in 1hr 5 mins I don't know how can I miss that silly thing and ended up solving B,C and E1 so never give up till last.

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

for 1.45 h I couldn't solve any problem then in the last 30 min, I solved problem A and C so cool even if I lose points this is good problems I ever seen in div2 problems well done ^_^

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

How to solve C?

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

    If all the characters in the given string are c then the answer is 0. Else just use brute force whether the answer can be 1. If the answer cannot be 1 then the answer will be 2 as we can always select n and then n-1.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      1. If nothing to change then answer is 0.
      2. If only the last character is to be changed, the answer is 1 2 or 1 3 depending on wether n is odd or even.
      3. If some character/character**s** other than the last are to be changed, then the answer is 1 N.
      4. If both 2) and 3) then answer is 2 N 2 or 2 N 3 (if N is odd then 2 N 2, else 2 N 3).

      This failed on pretest 2. Can you explain whats wrong with this? Unable to view pretest 2 right now.

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

        N can be divisible by both 2 and 3 :)

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

        Here is my solution. https://mirror.codeforces.com/contest/1594/submission/131189048

        If you pick your any of the number in the latter half of array, all other elements can be replaced as 2*element index will be greater than n.

        You have to consider cases when the last 2 elements are not the correct ones but there exists some index in the later half of the array with the correct character. That index can be chosen to replace all the remaining elements in 1 operation instead of 2 operations.

        Take some examples and go through the solution. If you still can't figure it out, post your question. Cheers!

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

        8 a aaaaabab

        You say the result is 2 3 but its actually 7

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

Problem D: https://www.codechef.com/INOIPRAC/problems/AMONGUS2

sus (pun intended)

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

    And here I was, shocked, bamboozled, confused whether I am crazy, hallucinating, or just sleepy when I saw blue Indian kids solve D in like 5 mins or so. To whoever authored this problem, if it was a weird coincidence, then oh well, shit happens. Otherwise, fuck you.

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

      We would have never used a problem that we knew already existed and was created by someone else, we started creating this round 15 months ago and wanted to make it the best possible. A coincidence indeed, unfortunate for all of us and we are really sorry about it.

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

    We are really sorry for this, we were not aware that this problem already existed and the idea -we thought- was ours and came from scratch inpsired by the game "among us".

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

      Hello yes, to me seems like a notorious coincidence that both ur problem and the one where it matches were exact the same and also based on among us.

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

        We would never use a problem that we knew already existed, we gain nothing by doing that as we spent more than 15 months on this round and wanted to make it as best as possible. We are really sorry.

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

        Among us was a very popular game when I created that problem and the games of people that always say the truth or always lie are also really popular. You can definitely think whatever you want but do you really think that we copied the problem and said that it was ours? It is very sad to read comments like this. We tried our best to make a contest with short and clear statements and solutions that weren't very long. Again, we are really sorry for what happened (especially to the_hyp0cr1t3 the author of the original problem). If we will do another contest in the future we will be more careful about these things.

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

        Its not as unlikely as you might think, the INOI version was just a direct formalization of how an average emergency meeting goes in the game that the_hyp0cr1t3 came up with when a few of us were attempting to set problems after we had just played it.

        Its a very natural formulation and the min / max decision is a 50-50 choice anyway. The only other natural thing you can do with it is check if exactly $$$k$$$ imposters are possible and that's just boring addition of knapsack which also requires reducing constraints.

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

      No worries, it happens :) I enjoyed solving the problems and I think the contest is very good!

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

      Choose better testers next time. :(

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

        Testers are not to blame, they did their job as best as they could and their feedback was very helpful. We will make sure that nothing similar to what happened today will happen again in a round authored by us, we apologise.

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

          the suckers can suck, it was a great problem set that was amusing and fun to solve, to say the least.

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

Ironic how Problem D is an imposter. I had authored and created the same problem a while ago on codechef for INOI haha :3

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

Problem D is same as INOI 2021 Among Us

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

    What was the intended solution? I was trying DSU's. I had the idea, but couldn't come up with an implementation.

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

      Yes DSU works. The solution I submitted used DSU. Basically it's Online Bipartite except for the fact that "Online" is never used. So you can basically do it with simple DFS/BFS as well.

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

      I think a variation of bipartite color assignment could also work.

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

        This was the expected soln for the INOI version of the problem iirc, just try to colour the nodes, propogating the same colour for edges of type 1 and the opposite colour for edges of type 2.

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

      Let's say the edge weight of i,j is 1 if i says that j is an imposter or j says that i is an imposter, similarly 0 for non-imposter relationship. You can just color them. col[i] = 1 means i is imposter, else col[i] = 0. For every edge (i,j) col[i]^col[j] = edge weight. Now, this becomes similar to a bipartite graph problem with the maximum number of white nodes.

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

F is such a troll problem. Also why so tight TL in E2? I had to optimize constant to make it pass.. or maybe I have wrong solution :)

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

    I replaced unordere_map/unordered_set with map/set and reduced the running time from TLE to 124ms.. not sure if some of the test cases were deliberately designed to make c++ unordere_map/unordered_set fail.

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

      Yes,right.I meet the same situation.It took my almost an hour to consider why I got TLE during contest.

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

        I was a little disappointed actually. there is nothing wrong in our code or our algorithms. there is even nothing wrong in STL -- STL was implemented for solving practical problems in the industry, instead of for dealing with some nitpicking testing data deliberately placing obstacles.

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

E2 was beautiful.

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

    I really liked how authors were lenient on time and constraints as well.

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

Was E1 dp or just a math formula ?

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

D is a great problem .. :+) and Yahhhhhhhhhhhhhhhhhh specialist again :+)

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

Since contest is over, plot reveal! Problem D was most likely copied from INOI 2021 P2 (I say most likely since this might be the original problem from an unknown source and both of these could be copied)

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

    We did not copy the problem nor were we aware that it already existed. We are sorry for this, our only inpsiration was the game "Among us" and the rest were our ideas.

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

      This could be true...

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

        We gain nothing by using a known problem, that only hurts us. We are sorry for not knowing that a very similar problem already existed and we are just as disappointed as you are.

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

          No no, I actually believe you. Considering how "Among Us" works it is quite natural to see things this way.

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

Great and interesting problems today. Enjoyed giving the contest.Kudos to Theo830 and Dremix10 for the great round and all the testers as well.

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

D, a problem with 1750 points was a repeated problem

E1 was also the same as a CSES problem.

I knew neither. Thank you, I'll enjoy my -100 delta

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

    could u link this CSES problem?

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

    I rage quit when I saw my "friends" solve D in 5-7 mins, and I went on scratching my head on that problem for like an hour or so, without any solutions.

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

    I'm not sure about the CSES problem you're referring to. If it's https://cses.fi/problemset/task/1712, then I guess you missed the fact that $$$2^{60}$$$ can easily be stored in a long long, and you can do straightforward modular exponentation to that value. The main part was to find the formula (although short).

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

    So you can only solve problem you've known before? Sound like you got the delta you deserve.

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

      No, I prefer non-repeated problems(ad-hoc if possible), as with repeated problems rankings get kinda skewed, giving an unfair advantage.

      Edit: Also I know the more you solve the more you have this advantage, but I think we all can agree it sucks if a problem is straight-up repeated, intentionally or unintentionally

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

        Yeah, it was unfortunate that this situation happened. However, saying that you couldn't solve a problem because it was repeated just doesn't make any sense.

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

          Oh well I wasn't blaming that fact for bricking the problem, I just suck.

          I was blaming that fact for ruining my bad delta even further, which I think is reasonable.

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

      It is not an issue, that you can't solve the problem.

      The issue is when 1K other people knew this problem before and were able to submit it fast. People who didn't know the problem and solved it slow or didn't solve it at all are heavily affected.

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

        It is not an issue, that you can't solve the problem.

        It IS an issue when you couldn't solve a problem yet still managed to complain about its originality.

        I was specifically replying to that comment and I didn't find myself saying that reusing a problem was okay. So what are you trying to say here, again?

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

          Complaining about the originality of the problem is a legitimate issue, no matter being able to solve it or not. You were affected in both cases by the fact that others knew it beforehand.

          I am also not sure, what are you trying to say. This is obvious, that there were 2 groups of people — those who knew the problem and were submitting like crazy and those who were struggling. If you found yourself in the second one, you were heavily affected. There is already tons of cheating for the original tasks. If there was a repeated task of level D, you could expect a massive amount of submissions, especially when you are not breaking any rules by reusing the existing online code. You could copy and paste the solution and you can't even be banned for this.

          What is also funny, is you can see (in the comments) that some people wanted to brag about solving D. They copy-paste the existing code (without understanding the idea) and then just provide the URL to their accepted solution, explaining that details are too hard to describe in English, so just read the code :)

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

            Ok, I think I figured out what are you saying. You claim that by the fact that you didn't solve the problem, it means that you didn't know it (not necessarily true), so you shouldn't complain about its originality (because for you it was still the original problem).

            I think it is just trolling as he wasn't complaining about the quality of the tasks or the problem-solving experience. He complained about the personal outcome of the whole story.

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

            With respect, I think you're putting too much thoughts into this issue. Unfortunate things are sometimes bound to happen, we just have to deal with them and move on. It's an online contest after all, can you imagine how people reacted when it happened in an official competition like IOI?

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

I thought how the hell so many people solved D.
Looking at the comments, I'm getting why...

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

Is D a graph problem?

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

    Yes and union find set is used to solve D

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

      Can you please explain how to approach it?

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

        I tried but have found that it's quite hard to explain T_T. A hint is that if one says that someone is a crewmate, then they must be either crewmates or imposters.

        Thus you can use union find set to deal with the problem, at last coloring a bi-graph is needed.

        Elaborating the detail is far beyond me — my poor English but you can have a look at my code here

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

      Yeah but I mean D is quite easy for it's place. It is a free ~1750 points to anyone who has seen enough applications of DFS, BFS.

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

Can someone explain E1?

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

    It was simple combinatorics. You can color the root in any one of the 6 colors, all the subsequent nodes can be colored in any 4 of the remaining colors. So the answer is simply 6 * 4 ^ (number of nodes — 2).

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

tks bro :3, the problems are pretty good. But E1 < C :3. I tried to solve problem C but it was not AC. Maybe give me for idea to solve problem C.

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

    the minimum number of operations $$$m$$$ can be only 0, 1, or 2.

    the upper bound is 2 because we can always choose $$$x_1=n$$$ and $$$x_2=n-1$$$ to make all characters in $$$s$$$ equal to $$$c$$$. $$$n-1$$$ can't divide $$$n$$$ since the problem guarantees $$$n\geq 3$$$

    if originally each character in $$$s$$$ equals $$$c$$$, $$$m=0$$$

    if originally $$$s_n = c$$$, $$$m=1$$$ (choose $$$x_1=n$$$)

    if originally $$$s_n \neq c$$$, we find the last position $$$p\in [1, n]$$$ s.t. $$$s_p=c$$$, then if $$$p>\lfloor {\frac{n}{2}} \rfloor$$$, $$$m=1$$$ (choose $$$x_1=p$$$), else $$$m=2$$$

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

Was so close to becoming a Specialist but wasted much time on B and couldn't solve it, should have gone to E1. Nevertheless, I enjoyed the problems.

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

How to solve C ?

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

Hmm... Isn't problem D a very old and classic problem? IMO it's not very suitable to be used in formal contests (maybe it can be used in an educational round?)

Problem E2 and F are nice, thanks for the problems XD

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

    We were not aware of that and are really sorry about it.

    We will make sure that nothing similar happens again.

    Thank you for your kind words, we tried our best and are glad you liked them!

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

Math riddles that i failed miserably.

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

Problems A-E1 were more boring than usual, but E2 was nice. Sadly I finished E2 just after round was over :pensive:.

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

any one could help explain the method used to solve problem B ?, thanks in advance .

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

    Consider the number base n. Each good number is a number that has all digits equal to 0 or 1 in base n. Well, to find the kth of those, realize you can generate all numbers with only 0 or 1 value digits by just counting in base 2 and looking at binary representation, since binary is different masks of 0 and 1. This means you can just look at the number k in binary, and for each 1 in the binary corresponding to 2^x, you add to the result n^x.

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

A, B and C are quite creative problems!

but I think D is quite a classic problem

E1 is a simple combinatorics but I can't solve E2 and F T_T

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

Good contest !

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

Almost solved problem B but C looked easier than B to me. But I was too late to notice it. As soon as I coded C the contest already came to an end .... :) May be missed a chance for increasing rating :)

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

In c problem ,I was trying to find the nearest prime number<=n and then if the character at that position matches the given character c , then answer would be 1 , the number would be that prime number , else the answer would be 2 as one to change the character at the prime number position and the other for rest of characters in string. My this approaching is failing on same cases which I am not able to figure out, can anyone please help me by providing such case. code:-https://mirror.codeforces.com/contest/1594/submission/131209103

Thanks in advance.

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

    I was also doing the same but turns out that's not required and neither correct, u just need to check for i from (n/2 + 1) to n if there is any character equals to c then ans {i} otherwise m has to be atleast 2 and that can be done using {n,n-1}

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

    7 a abbbbab you can choose x = 6

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

    The optimal index is not necessarily prime.. Any index i such that for j in 1 to N, if j is divisible by i, then s[i] is equal to C will give an answer of 1. If such an index does not exist, simply use the last 2 indices, and ans will be 2. Can be brute forced ( NlogN )

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

    one counterexample is:

    7 a

    aabbbab

    in this case you should choose $$$x=6$$$, which is not a prime

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

This was a great contest!

The questions are quite unique with division-2 difficulty.

The solutions are also very diverse ඞ.

I also recorded a video during the contest that talks about solving problems A~E1 with explanations.

Please watch it if you are interested.

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

In the problem D, I have used the following approach, for every node I first I assume the node to be a imposter and then do a dfs and then count the number of imposters found in this scenario. Then I assume the node to be a crewmate and then do a dfs and count the number of imposters. I set the value of the visited nodes to be corresponding to the case in which maximum imposters were found( i.e. whether on assuming the node to be imposter or assuming it to be crewmate). Can someone tell me where am I going wrong. Submission: 131237230

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

    I am not sure, but from the judge, there is a wrong answer on the case:

    3 2
1 3 imposter
2 3 crewmate

    where you should print "2" instead of "1".

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

Thanks for the contest,

I think making n as 100000 would have been better for E1 considering it's position

My solution will work n = 100000 too

https://mirror.codeforces.com/contest/1594/submission/131200149

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

To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

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

    One of my solutions still shows pretest passed after system testing. On resubmitting the solution after system tests it is accepted. link is attached below

    Solution : My solution

    Link to blog : Blog entry

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

    Hi Mike, can you help me with this? my submission on problem B was considered plagiarism, but our submissions coincided just because the solution to pB is quite simple, and contains only one simple bit manipulation procedure.

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

I think author have some love with long long and % 1000000007 (::)

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

    This is actually true about long long xD

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

Can anyone tell what's wrong with my submission ? 131208294

I am simply making the crewmates into a single node and then use bfs to find if the graph is bipartite and the biggest bipartite possible. I can't see the full test case so I can't test. It seems that I am printing some extra -1 's.

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

MikeMirzayanov My submission for problem C passed the pretests but even after the system testing it's neither showing wrong answer nor accepted..instead it's still pretests passed...While submitting the exact same solution after the contest was over got accepted.Please look into the problem and update my rating accordingly.

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

Just a doubt
The answer for this test case in problem 'C' is not '6 5'. Why?
----TEST CASE------
1
6 v fxblgs
-------------------
After choosing x=6
s becomes vvvvvs
and choosing x=5
s becomes vvvvvv
but the answer is wrong.
But why?

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

alternative DSU based solution for problem D. https://mirror.codeforces.com/contest/1594/submission/131244090

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

My submission for D passed the pretests but got TLE on the system judge.
However, resubmitting the exact same code after the contest gets AC.
Is this normal or a glitch? code: https://mirror.codeforces.com/contest/1594/submission/131212208
PS. Thank you for the contest.

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

Is it just me or does anybody realise that problem B has a rick roll in it? (Yeltsa Kcir is Rick Astley reversed) XD

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

The Contest was entertaining. I enjoyed the whole 2hr 15 min.

Thank You :)

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

Regarding this message i got from codeforces- "Attention!

Your solution 131199954 for the problem 1594C significantly coincides with solutions CrocHold/131199954, contestiscontest/131199998, checker_1234/131200079, tourist___________1/131200332, tu-rex/131200598, testcase321/131200841, nas.2.op/131203694, susamogusbob/131204347. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."

The comment that i'm supposed to post here- The solution is ridiculously obvious to figure out, kindly undo and remove any related penalties levied on this account. Finding numbers that have only 1 multiple in the range is super obvious. The largest ones. that's all i have to say in my defense ...peace!

→ Reply