sevlll777's blog

By sevlll777, history, 12 months ago, In English

I'm very very sorry to all Div2 participants for unclearness in statement of A, and not including notes in the statement of B, hope it didnt ruined a contest for you. Thank you all for participating, I hope you enjoyed non-empty subset of the problems! You can rate the problems of the round in the corresponding spoilers.

1894A - Secret Sport

Hint 1
Hint 2
Tutorial
Solution
Rate the problem

1894B - Two Out of Three

Hint 1
Hint 2
Tutorial
Solution
Rate the problem

1893A - Anonymous Informant

Hint 1
Hint 1.1
Hint 2
Tutorial
Solution
Rate the problem

1893B - Neutral Tonality

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Rate the problem

1893C - Freedom of Choice

Hint 1
Hint 1.1
Hint 1.2
Hint 2
Tutorial
Solution
Rate the problem

1893D - Colorful Constructive

Hints: Natural Way
Hints: Believers Way
Tutorial
Solution
Rate the problem

1893E - Cacti Symphony

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Tutorial
Solution
Rate the problem
  • Vote: I like it
  • +26
  • Vote: I do not like it

| Write comment?
»
12 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Nice contest and fast editorial, A was tricky

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why is this getting downvotes, someone please explain.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      Because questions were not that difficult. Like you would be able to solve d just by simple sorting

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        there actually is a builtin function in c++ to solve that problem, it's called merge. 231958618

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ohh... Thanks, I didn't know that

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

          I took this comment as a hint, and implemented the merge logic manually... And I got AC!

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really nice div 2 contest and fast editorial. Thanks a lot!!!

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C and D div 2 was nice

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    too easy at this place.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +60 Vote: I do not like it

      Well,may be it's different for different people.As a div1 contestant,div1A and div1B (div2C and div2D) were really not easy for me that I spent nearly 45 minutes to solve them,but what shocked me was that div1C and div1D were very easy to come up with for me...

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

Could anyone help me figure out why my code can pass 1B? I can't prove my solution is right qwq. my 1B submission

»
12 months ago, # |
  Vote: I like it +73 Vote: I do not like it

Div1D way too EZ

»
12 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Problem A is true observation, I even didn't know how I got AC by that code lmao

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'd like to know how sevlll777 created the sample input. I think it's more difficult than solving the problem.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      It seems that just make random strings with $$$\text{the number of }\mathtt{A} \ne \text{the number of }\mathtt{B}$$$ is ok. In this case you can choose $$$X=\max(cnt_A, cnt_B),Y=1$$$.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      validator is like: bruteforce all $$$X$$$ and $$$Y$$$

»
12 months ago, # |
  Vote: I like it +117 Vote: I do not like it

The performances of participants who solved $$$3$$$ tasks range from CM to IGM (in Div. 1). I believe that the coordination is really incredible :)

»
12 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Man, the first problem is the same problem that errichto said in the interview with the Joma Tech (available on youtube) right??

»
12 months ago, # |
  Vote: I like it +90 Vote: I do not like it

div1 B>C>A>D

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What a fast editorial)

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

A was too bad, B and C were nice.

»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

A solution doesn't take into account inputs of type "AB" or "ABAB" right? Which should be reported as "?" since there is no clear winner. Except if we consider the string fed to us is always correct?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Except if we consider the string fed to us is always correct?

    From the statement (in bold):

    "It is guaranteed that the given sequence of plays corresponds to at least one valid game scenario, for some values of $$$X$$$ and $$$Y$$$."

»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Intuitive understanding of the correctness of the full greedy algorithm for D :

When filling a shelf, we select the $$$d$$$ most present colors and take one of each, and repeat until the shelf is full (taking the $$$d$$$ colors in the right order as to keep the condition).

It breaks only if there are less than $$$d$$$ different colors left. Hence, if we have to choose between two colors, we want to use the most present one, as to avoid being left with only one of them in the future. And if we have to choose between all of them we want the most present one.

This gives a simple solution that can be implemented with a priority queue (see my submission https://codeforces.me/contest/1893/submission/231786809)

And congratulations to the author for the amazing problems ! I really enjoyed the round !

»
12 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Ty @Errichto for explaining Problem A 4 years ago

https://www.youtube.com/watch?v=F4rykKLcduI

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly remembered this clip when I saw this problem, thought I'd give it a shot and voila! AC

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

In Div2-A If the input was "AB" should not the output be '?' since there is no winner?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    The string "AB" is not a valid game scenario and since the input is guaranteed to be a valid one...

»
12 months ago, # |
  Vote: I like it +36 Vote: I do not like it

wtf where's the proof of greedy in D? like 80+% of AC's used that greedy

»
12 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Didn't solve D1C because 1e17+1 is not (ll)1e17+1...... and in test case 3 where sum(r[i])==1e17, my solution took it as sum(r[i])>=(ll)1e17+1

»
12 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Div2 ABCD are so trivial in implementation that I just hesitated to submit them, was sure that missed something in problem description, and overcomplicated D to the point where it's finally got wrong. I'd prefer more emphasis on implementation than deciphering descriptions.

»
12 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Can anyone please help me to find out what's wrong in this code? (https://codeforces.me/contest/1894/submission/231802454) I got AC just by changing the condition in while loop. AC submission: (https://codeforces.me/contest/1894/submission/231828401) But what's the difference between this two?

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2 A :

testcase : 4 , aabb

how can answer be B?

For what x and y is answer going to be B

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I noticed the solution for problem A quickly. And waited 15 minutes rereading the statement then submitted a more complicated solution. That was a bad statement. Otherwise the other problems were nice.

»
12 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Div-2 C was good ... i was able to make major part of the logic but wasn't confident enough to implement

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

(Div2-A) That makes sense. But there won't be any "?" output (either A or B). Also X,Y are considered redundant. All in all, it was weirdo :/

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To add some more weirdness to it, a problem statement as short as 1 page with 1 line of code solution caused 2 announcements during tournament.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In question B , there is also another way to insert the elements of b in the array a . In array a , we can look for the starting point of the lis of array a such that the point is to the left as possible if there are more starting indices of same length lis . Let the element at the starting position is elem.Then we can insert all the elements greater than the elem to the start of the array in decreasing fashion and all elements less or equal to the elem after elem in decreasing fashion . The problem is how to find this elem(starting position with above requirements in given time constraints) . Can we find this out (basically we have to find the leftmost index of lis of array)?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great idea, but it needs to be fixed. Consider this case: A:2 2 3 4 B:1 if you insert 1 after the first 2,the result will not be best. About your question, simple dp runs in O(n^2) and there exists a binary search trick to make it O(nlogn) .

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

      Yeah i see , the idea requires handling rhis case also . In this case we can insert after the 2nd 2 .The n2 approach will give me the starting point of the lis but it is not within time constraint.The nlogn thing afaik it gives me the length of lis bit not the elements. Can we modify it to find if not all but the 1st element

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

        Consider this case,A[7 8 9 4 5 6], B[3],the leftmost element is 7,but you need to insert 3 after 4, not after 7. Also, the nlogn solution gives you same result in each step as n^2 solution, not only the final lis length. You can find this point by comparing these two solutions in each step.

»
12 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Even though people dislike A problem thanks for the fast and high quality tutorial, with hints and the possibility to rate each problem.

»
12 months ago, # |
  Vote: I like it +338 Vote: I do not like it

I'm writing this text because I was deeply affected by some comments about the contest and some personal messages received on cf. And I feel an urgent need to explain how the contest was created, why these particular problems were chosen, what was the idea behind the problemset. And to show that I care about each problem, and about the contest as a whole.

I will focus on the Div1 part of the round, because it was Div1 that was the main goal, it was Div1 that had most of the effort and thought put into it.

The main things I wanted to show to people in this contest were the author's solutions to problems B, D, E and their proofs (for B, D), and the solution process (for E). (I'll talk about A and C later, but, spoiler, these problems were not chosen "from what was available", and there is a strict motivation behind both of them, but more on that later). Seriously, I recommend everyone to read the editorial of problems B, D, E and understand the authors' solutions and their proofs. I find them very beautiful, and these are the ideas I wanted to convey in this contest for the general audience, it was the basis for the creation of the contest. More details about these tasks:

B: I'm still amazed by the fact that you can insert any numbers into any array in such a way that the LIS doesn't change, in my opinion it's just marvelous. The statement itself sounds like this is a well known problem, but surprisingly it is not. The first version of the problem had $$$m = 1$$$, that is, you had to insert one number, and in this version the problem does not reach its full potential, not all the beauty is seen in such a formulation. And the surprising thing is that such a simple and familiar algorithm leads to the solution: merge two arrays with two pointers. And I find the proof of this very beautiful. The author's solution is unironically: input + 2 lines + output. Seriously, isn't that fascinating?

D: I really like the author's solution and his proof, that such a simple and trivial necessary condition suddenly turns out to be sufficient, and it's not difficult to prove, it's a very simple construction. And now the problem, which at first sight is impossible to combine for $$$m$$$ different arrays suddenly splits and becomes so simple, familiar and understandable~-- just split into arrays of different numbers for given lengths, and further solution is just a matter of technique. Seriously, isn't that fascinating?

E: Kind of the opposite of problem D. I really like that the solution consists of a few tiny ideas and observations. And at some point, after some number of observations, it is suddenly revealed that the problem breaks up into 2 independent and standard-sounding problems. What I like about this problem is that the statement has some stupid formulation and some incomprehensible constraints taken from the sky, but in the end the solution turns out to be very natural. And in the flow of solving the problem, everything falls into place, strange constraints are revealed, and their meaning becomes clear. And the moment when the problem breaks up into 2 independent, familiar and understandable tasks is the peak, the catharsis of this problem. Again, I really like the resulting structure of the solution, starting from some random conditions we step by step approach closer and closer to something understandable, it does not happen at once, first one observation, then the second, third, etc., and at some point the problem falls under the rush, and disintegrates into two simple and so familiar combinatorial problems. Seriously, isn't that fascinating?

As it happens, one story happened to all B and D and E: the moment they transformed from ideas in my head to actual competetive programming problems, art and magic chastically collapsed, due to alternative solutions. About alternative solutions:

B: there are VERY many alternative solutions to this problem. VERY. There is, also quite beautiful, an alternative solution based on a deep understanding of the algorithm for finding the LIS for O(n log n) using DP with binary search. But there are many others. And this is something I can't control. I can't force all participants to come up with a 2-line solution, and even if I could, it would be bad, "you can't force someone to enjoy the art", you know. That's why I, as an author, put up with a lot of alternative solutions, in order to bring my idea of an author's solution to the general audience.

D: there is one alternative solution here. And yes, it is horrible and disgusting. Stupid stupid stupid greed. I was not originally aware of this solution. This solution was found by the testers. In fact, in this problem I had many ideas and options how to change the statement to break the greed. For example, a version where you don't have to recover the answer, but there are q queries "add a cube of color X, s[i] += 1". But that makes the task ugly. It spoils the picture by spilling some black paint on it. The purest diamond would have a dark spot. I don't like that. Absolutely not. When choosing between two evils, I'll always choose the alternative solution. But I won't spoil the task, I won't spill paint on my beautiful solution. And that's where I'm probably wrong about making a contest for a wide audience. Maybe I should have compromised, and "messed up" the author's solution to cut the alternative solution. Perhaps.

E: there is also one alternative solution here. Nightmare dp on cacti with 100500 parameters and recalculation with matrices. This sort of thing is usually dealt with by choosing constraints, and yes, this is why problem E is the only one with n = 5e5. But it was all useless, since it was not possible to cut off this solution completely. I tried to spoil the life of those who wrote this solution as much as possible, but so that those who wrote the author's solution would get the AC as freely as possible. Here also the duration of the contest set at 120 minutes played a role. In this problem I also considered the option of adding queries, a-la "+X vertices appeared on edge E". Perhaps I was wrong, and I should have compromised by adding ugly queries. Perhaps.

Now I will tell you about tasks A and C. Formally, these tasks are "fillers", but I still put my soul into them, and now I will explain it.

A: The first task of the contest. The apitizer task. A task that should not be too difficult, but not too trivial. It should contain a minimal idea, which is nice to find by yourself. A task that should entice you into the contest, and set you up for a further two hours of brainstorming. That's my philosophy for the perfect div1A. And I'm confident that this task A almost fully satisfies that philosophy. But there is a small problem. The main idea of the task is rather "hidden in the statement", lying out in the open, rather than requiring some great idea. The problem requires observation in the truest sense of the word. And yes, this problem was not perfect, but I still consider it more than worthy for a contest opener.

C: The task that got the most hate after the contest. This task contains some cute and funny ideas, which lead to the fact that a rather dumb bruteforce turns out to be very fast. I find the idea part of the task cute, but certainly not at Div1C level, more like Div1A level. The big challenge here is really a neat implementation of the solution, fast and bug-free. And yes, that's why the task made it to the contest. Its purpose was to mix the full-of-idea tasks B and D with some implementation, and to bring variety into the contest. That's why from my point of view it was a perfect-fit, adding to the contest a test of another part of a competetive programmer's skill: fast and accurate implementation. That was the idea. And it failed miserably, and it seems, because of alternative solutions for B and D. Or maybe not, and I just overestimated the interest of the idea part of this problem, and in fact it is Div2A level. I don't know. I don't know...

I doubt anyone will actually read this text. I would never post something like this publicly, but I really want to show that I really cared about the contest at worst. And at best, to explain my philosophy of problemsetting. Sorry if the text turned out to be messy and crumpled. And thank you.

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it +68 Vote: I do not like it

    First of all, thanks for preparing the contest! I liked thinking about B and D. Still, and it seems like you agree, the contest does have it's flaws. I'd like to share a couple of thoughts I had during testing and after reading you comment, maybe someone will find them useful)

    A: What I didn't like about this problem is how contrived the statement felt. Too many things had to be satisfied to make it work. Maybe most of the competitors felt the same way.

    C: Again, the statement feels pretty contrived. The solution is almost hidden behind the statement, so after parsing it, only implementation is left. I felt mostly ok with that, but it seems like quite a lot of people disagree. Personally, I wouldn't be ok with putting this in my contest without trying to come up with something better, but well, that's just my opinion).

    B and D (and maybe E?): I think that even if a problem's intended solution is very interesting, for a contest, you have to consider what participants are more likely to stumble upon. If with a high enough probability that turns out to be some undesirable solutions (from your point of view), and you can't cut them off in a pleasant way, maybe you should reconsider using the problem in the contest, at least in it's current form.

    That being said, trying to estimate what participants will come up with is sometimes very hard) Though in most cases, I feel like the miscalculations are due to either the author and coordinator being not up to date with the community as a whole or the tester pool being not representative of it (sometimes both). Fortunately, it's possible to reduce mistakes from these sources, though I feel like not enough effort is put into doing that (I've been guilty of this a couple of times myself, but hopefully, I've been learning from my mistakes...).

    Side note: problems are sometimes surprisingly resilient to giving up their core idea even after pretty significant changes, though I feel like that mostly happens when you have a simple statement)

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      Thanks for the comment! Just in case, I want to ensure you, that I didn't ignore your feedback during testing, btw, TLs were increased because of your suggestion. You were not the only tester who not liked A and C, but there also were testers who liked both of them, and afterall I decided to trust my inner feeling and leave both problems in their places.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +78 Vote: I do not like it

    Obviously, spoiling beautiful problems for cut some muddy solutions is a bad idea. I think everyone could learn something from this competition. For example, that sometimes you can believe in some kind of unprovable greedy (D). For me, an important lesson was that before you rush to write code, you should think a little more, and not shove two different subtasks into one dp (E).

    Anyway, thanks for the contest! People are designed in such a way that they would rather blame the author than try to find their mistakes and learn SomethingNew) I will be waiting for new contests from you!

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I did find problem B fun to think about. The observation that LIS stays constant felt a bit obvious when you're given this much freedom of where to insert the new element, but still finding the right strategy is very much not obvious.

    Personally, D is also fine as is, because the greedy solution to D is magical to me, it's surprising that such a simple solution works for what is a problem with a lot of moving parts. I don't hate the greedy solution as much as most people, but I do hate whoever submitted it without proving it. Shame on you.

    But in general I'm not opposed to adding more details to a problem to "force" an observation if it's a beautiful one, that is done quite often in e.g. problems where you're asked to count number of some configuration (to force you to find observations that make it easier to count).

    Now, the part where I think you're mistaken, is that C would be bad regardless of the rest of the round. The statement is very hard to understand for what seems to be no good reason -- why introduce 998244353 variables when you could have written something like "You're given n arrays $$$a_1, a_2, ..., a_n$$$ and you must select at least $$$l_i$$$ and at most $$$r_i$$$ elements from array $$$a_i$$$"? And then, after you spend a lot of time to understand the statement, you spend no time solving it because, as you admitted yourself, there is only one extremely simple idea and it's at most a div1A in terms of difficulty and should never be 1C.

    This could have been a fun round with some adjustments, remove C because it's fun for no one and add something else to actually bridge the difficulty gap in the middle. Still B and D had some cool ideas and I have faith that you can make a better received round in the future. Just maybe ask for a better coordinator.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the well problems and the preparation of the contest.

    Actually I was annoyed by the implementation of 1B and 1C (I write very sophisticated code for 1B, around 160 lines) and had no time to read 1D. 1B is my fault, but I think it better to remove 1C.

    However when I read the statement today I immediately came up with a same solution with the author(divide a shelf to several $$$len=k$$$ parts and a $$$s\bmod k$$$ part) and when I read the ultra greedy solution, I found both beautiful. But whichever solution one chooses, the difficulty is only 1B/1C while not 1D.

    So a good solution is removing 1C, placing 1D at 1C, and adding a more 1D and 1F.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the comment! By the way, 1D was indeed in 1C spot at the start of the testing. But many testers had difficulties with this problem, thats why it ended up in 1D spot.

»
12 months ago, # |
  Vote: I like it +16 Vote: I do not like it

this contest too bad !!

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

In Div 2-A 6th example test case —

13 AAAABABBABBAB

here if x=1,y=13 then A is winning more, but not in the last slot, and if x=13,y=1 then A is winning as A won more matches in the slot. then how B is the winner here? can anyone explain, please!!

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

    x=3,y=2 is a legal explanation.

    And actually,the problem says that if one wins y sets,the game will be ended at once. So when the last play ends,the game will be ended.So the winner of the whole play must be the winner of the last play.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • but a set of size 3 (as x=3 ) is not possible cuz the matches played are 13, so x could either be 1 or 13, or it won't make a valid combination of sets, it has to be in multiple of 13.
      • »
        »
        »
        »
        12 months ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        There's one thing that one set contains at least x plays,but not only x plays.Maybe you have some misunderstanding of it.

        For example,if we set x=3,y=2,the first set is AAA,it stops as A wins 3 times. The second set is ABABB,obviously,it contains 5 plays but not x=3 plays,that's because it stops when B wins 3 times while A wins 2 times at the same time. The third set is ABBAB,the same as the second set.

        So B wins y=2 sets,then B wins.

»
12 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I am curious how the author came up with Div2A, and how you (noone including the coordinator) couldn't find a duplicate problem. It took me less than 5 minutes to find a duplicate from IPSC 2005.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sadly I failed to debug Div2 E

»
12 months ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

Just look at this code: https://codeforces.me/contest/1894/submission/231756011

It has Undefined Behavior (Heap-Buffer-Overflow on $$$used$$$) already in example, but passed all tests.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint 3 in the solution of Div1 E really confused me. I think it should be InDegree instead of OutDegree.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone can explain why the time cost of tutorial to div2E can be $$$O(\Sigma n_i)$$$, from the code, i think it is $$$O(\Sigma n_i)*O(\Sigma r_i-\Sigma l_i)$$$,at most $$$10^{10}$$$

  for (int len = suml; len <= sumr; len++) {
    for (auto &[i, pos] : indexes[len]) {
  }
}
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No because sum of the indexes length is at most n

»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Damn I hate that I missed the round. Heard that Div1-C,D were really fun.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest sevlll777, I am a little unclear on why exactly a cycle is created after n reversals [Anonymous Informant], could you please explain in an intuitive way?

  • »
    »
    12 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Okay I got it after a few minutes of thinking. Here's what I think in case anyone needs it. There are at most n unique shifted arrays for any possible initial array. The next array that we get after a reversal is one of those n unique shifted arrays, and for one array, what comes after a reversal is fixed. Hence the moment one of the array repeats, the whole chain has to repeat. After n reversals, one of the array HAS to repeat (as mentioned before, there are only n unique such arrays possible, for it to not repeat there has to be more than n unique, shifted arrays for an initial array),due to which, the whole chain will repeat too. In many cases, the chain of reversals may start repeating before n.

    After n reversals we cannot disprove the anonymous informant anymore.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why my solution for div1 A is getting WA though it's similar to the solution mentioned in the editorial? submission

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What an irony to me. I could remember win loss statistics of all 1 <= n <= 20 games. Yet I didn't listen to the announcement revealing the winner in problem A.

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

Hello! 
I received a notification from Codeforces stating that my solution for the problem Problem link was flagged for similarities with other submissions, resulting in my disqualification from the contest. I believe this is a wrong accusation , considering the problem's simplicity, which naturally leads to resemblances in solutions.

Upon reviewing other submissions, I identified some differences in my code, such as my use of ordered map whereas all the other submissions have use of unordered_map . My coding style, indentation spacing and input/output formatting, remains consistent with my previous submissions in all my past contest submissions which is also quite different from other submissions. After grinding competitive programming for almost a year now it would be stupid for me to resort to copying solutions at this stage.

I kindly request MikeMirzayanov a reconsideration of my submissions to get this contest rated for me.

Here is my solution — link



Here are some other solutions which were mentioned in the message :

Submission 1

Submission 2

Submission 3

Submission 4

Submission 5

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

I wrote code for A that outputs the last char and then started overthinking why a div. 2 prob would be so easy and added more checks lmao.

This was a fun prob

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

You can adapt calculation method for LIS to solve D:

Calculation method for LIS in $$$\mathcal{O}(n\log n)$$$: https://cp-algorithms.com/sequences/longest_increasing_subsequence.html

In the method $$$d$$$ is calculated by starting with empty array, incrementally adding the next element of $$$a$$$ and updating $$$d$$$ after each addition. In this problem we can decide if we want to add either the next element of $$$a$$$ or some element of $$$b$$$.

If we add an element that exists inside $$$d$$$, $$$d$$$ does not update (think about it) and thus this element has no effect on LIS. Therefore if at the current step an element of $$$b$$$ appears in $$$d$$$, you should add that element from $$$b$$$.

Otherwise, you are able to choose whether to add next element from $$$a$$$ or some element from $$$b$$$. Due to behavior of LIS its best to add the large elements early and save small elements for later. Thus you should add the largest between: the next element of $$$a$$$, and the largest element of $$$b$$$.

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

sevlll777 in editorial of div2c/div1a, However, we can notice that if we manage to undo the operation n times without breaking anything, we have entered a cycle. Therefore, if we successfully undo the operation n times, the answer is definitely "Yes".

can you please justify this. How if we manage to do for n without breaking ,then we can definitely do for k.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

first one still doesn't making sense to me..why don't we take x = max(aCount , bCount) and y = always 1 then we can conclude that A is winner if aCount > bCount , otherwise B and else '?'.. like what is stopping me to do this??

»
9 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

It's a nice realization in C, Iterating the sets that contain $$$s$$$ for all $$$s$$$ is in total simply $$$\sum n$$$ (its like a rearrangement of the matrix given by the multisets) though at first it seems much slower