Theo830's blog

By Theo830, 4 weeks 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. zxcgod

  3. tuihuademing6

  4. OguriCap

  5. PATOLOVE

Div1 + 2:

  1. SSRS_

  2. tourist

  3. kefaa2

  4. hitonanode

  5. A-SOUL_Diana

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

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

Hoping for a good contest :)

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

nvm, added in the blog.

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

    Usual150 min

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

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

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

    Ahh Thank you so much M0riarty.

  • »
    »
    3 weeks 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.

»
3 weeks 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.

»
3 weeks 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 :)

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

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

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

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

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

        As a blog reader, I thought let's continue the comment series

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

As a tester, enjoy!

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

I don't know Theo830 in actuality, but I understand he is a really hardworking person!

»
3 weeks 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

  • »
    »
    3 weeks 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.

»
3 weeks 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 ?

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

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

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

Will probably get of of grey.

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

Hey please help me out with this problem.

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

    ab + bc + ca = ((a + b + c)^2 — (a^2 + b^2 + c^2))/2;

    2 segment trees.

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

      I didn't know segment tree yet...I will study and do it....I was applying fenwick tree but getting tle.. thanks a lott...

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

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

»
3 weeks 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!

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

" with short and clear statements. " Thanks :)

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

Why is it such a strange time

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

+1

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

Hello everyone! Good luck to everyone on the contest!)

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

Hoping for a good contest.

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

I don't like subtask.

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

let's play

»
3 weeks 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.

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

Hoping to enjoy an interesting contest!!!!

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

I hope this round will be my last round in grey (:

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

18:05 in blog is just Moscow time right?

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

WoHOOOO, contest after a long time!

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it
lighthearted meme
  • »
    »
    3 weeks 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". :)

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

    Why are all of your memes light-hearted?

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

Hope to score, even a little

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

What do you mean by first Cypriot round ?

  • »
    »
    3 weeks 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.

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

Good luck too all

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

Long queue! I hope it gets resolved asap.

»
3 weeks 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!!!

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

Moving on from Green tonight...

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

Wish today I will get break up with GREY

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

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

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

    May be it will be postponed

  • »
    »
    3 weeks 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.

»
3 weeks 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 =(

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

    That's because of your bad profile picture.

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

I AM NOT ABLE TO SUBMIT IT SAYS AM NOT REGISTERED

  • »
    »
    3 weeks 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!

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

speedforces. D was nice though.

»
3 weeks 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.

»
3 weeks 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 ^_^

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

How to solve C?

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

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

        N can be divisible by both 2 and 3 :)

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

        Here is my solution. https://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!

      • »
        »
        »
        »
        3 weeks 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

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

    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks 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".

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

    • »
      »
      »
      3 weeks 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!

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

      Choose better testers next time. :(

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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.

»
3 weeks 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

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

    there is an imposter among us!!!! P.S. It happens and has been fairly explained by comments above

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

Problem D is same as INOI 2021 Among Us

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

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

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

      • »
        »
        »
        »
        3 weeks 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.

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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 :)

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

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

E2 was beautiful.

  • »
    »
    3 weeks 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.

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

Was E1 dp or just a math formula ?

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

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

»
3 weeks 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)

  • »
    »
    3 weeks 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.

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

      This could be true...

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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.

»
3 weeks 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.

»
3 weeks 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

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

    could u link this CSES problem?

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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).

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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?

        • »
          »
          »
          »
          »
          2 weeks 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 :)

          • »
            »
            »
            »
            »
            »
            2 weeks 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.

          • »
            »
            »
            »
            »
            »
            2 weeks 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?

»
3 weeks 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...

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

Is D a graph problem?

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

    Yes and union find set is used to solve D

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

      Can you please explain how to approach it?

      • »
        »
        »
        »
        3 weeks 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

    • »
      »
      »
      3 weeks 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.

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

Can someone explain E1?

  • »
    »
    3 weeks 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).

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

      Got bricked after not being able to solve B, thanks for the explanation!

»
3 weeks 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.

  • »
    »
    3 weeks 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$$$

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

    E1 is rated 1000 C is rated 1500

    E1 was supposed to be < C

»
3 weeks 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.

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

How to solve C ?

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

    Its too easy :) But I was thinking about B... Didn't notice C. When I started to code it became too late :)

    Just think of this ; If s[n-1] ==c then obviously it is possible to replace all the remaining character with c with one go.... As N (length of string) won't divide any index then the answer will be 1 in this case ( if all the characters are already the given character then answer will be 0 ) But if s[n-1]!=c then check from n/2 to n if there is any i for which s[i]==c then the minimum steps required will be 1. And that index should be the value of x. Just take a pen and paper and think of it.

    But if you don't get any index i for which s[i]==c ranging from n/2 to n then obviously minimum steps required will be 2 and values of x will be n-1 and n

»
3 weeks 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

  • »
    »
    3 weeks 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!

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

Math riddles that i failed miserably.

»
3 weeks 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:.

»
3 weeks 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 .

  • »
    »
    3 weeks 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.

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

    u must convert k to a bit mask firstly for example k = 4 , so k = 1 0 0

    and loop on every index, if the bit number i is a set, add pow(n , i) to the result

»
3 weeks 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

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

The problems were good.

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

Good contest !

»
3 weeks 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 :)

»
3 weeks 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://codeforces.com/contest/1594/submission/131209103

Thanks in advance.

  • »
    »
    3 weeks 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}

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

    7 a abbbbab you can choose x = 6

  • »
    »
    3 weeks 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 )

  • »
    »
    3 weeks 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

»
3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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".

»
3 weeks 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://codeforces.com/contest/1594/submission/131200149

»
3 weeks 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!

  • »
    »
    3 weeks 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

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

    Please try to do this every time unless really not feasible... coz it helps us in ways.

  • »
    »
    3 weeks 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.

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

    -1

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

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

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

    This is actually true about long long xD

»
3 weeks 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.

»
3 weeks 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.

»
3 weeks 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?

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

Can somebody help me with C ! I thinking like this if I check the last character is equal to the given character or not , if it is than we will choose n as x since n won't divide any number from 1 to n-1, and if last character or the string is not same x than there would 2 operations n and any prime number less n ? I don't know why this approach is not working? Any help is sincerely appreciated since I'm a newbie and if I sound dumb please pardon me ! :(

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

    In some cases it is possible to convert the string using only one operation even if the last character of the string is not x. For Example:

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

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

»
3 weeks 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://codeforces.com/contest/1594/submission/131212208
PS. Thank you for the contest.

»
3 weeks 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

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

    Are you saying he's not related to Boris Yeltsin?

»
3 weeks 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 :)

»
2 weeks 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://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!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I just realized that "Yeltsa Kcir" is Rick Astley backwards....

I have been unknowingly Rick Rolled, screw me

»
25 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be nice to have only positive rating changes in codeforces for all level coders, so people doesn't bother to stop coding if they are so much rating phobic.