Блог пользователя Theo830

Автор Theo830, 3 года назад, По-английски

Γεια σου (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

  • Проголосовать: нравится
  • +586
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Hoping for a good contest :)

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +26 Проголосовать: не нравится

nvm, added in the blog.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

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

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

»
3 года назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

As a tester, enjoy!

»
3 года назад, # |
  Проголосовать: нравится +273 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Will probably get of of grey.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Why is it such a strange time

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hoping for a good contest.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I don't like subtask.

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

18:05 in blog is just Moscow time right?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

WoHOOOO, contest after a long time!

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
lighthearted meme
»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

What do you mean by first Cypriot round ?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Moving on from Green tonight...

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I AM NOT ABLE TO SUBMIT IT SAYS AM NOT REGISTERED

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

speedforces. D was nice though.

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve C?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        N can be divisible by both 2 and 3 :)

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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!

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        8 a aaaaabab

        You say the result is 2 3 but its actually 7

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      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 года назад, # ^ |
      Проголосовать: нравится +35 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится -40 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +38 Проголосовать: не нравится

        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 года назад, # ^ |
          Проголосовать: нравится +41 Проголосовать: не нравится

        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 года назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -14 Проголосовать: не нравится

      Choose better testers next time. :(

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

Problem D is same as INOI 2021 Among Us

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

E2 was beautiful.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Was E1 dp or just a math formula ?

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      This could be true...

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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 года назад, # |
Rev. 2   Проголосовать: нравится -88 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    could u link this CSES problem?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится -15 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

          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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
          Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

          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 :)

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +9 Проголосовать: не нравится

            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 года назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Is D a graph problem?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes and union find set is used to solve D

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please explain how to approach it?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Can someone explain E1?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve C ?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +52 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Math riddles that i failed miserably.

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good contest !

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    7 a abbbbab you can choose x = 6

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    one counterexample is:

    7 a

    aabbbab

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

Thank You :)

»
3 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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!