Codeforces Round 908 (Div. 1, Div. 2)

13 месяцев назад, # |

3-second-forces

→ Ответить

alex007__

13 месяцев назад, # ^ |

why are you not giving contest

→ Ответить

13 месяцев назад, # ^ |

because I've failed in the selection test for our national olympiad for high school students, so my goal for cp is basically over, I just came here to read the problems for fun

→ Ответить

alex007__

13 месяцев назад, # ^ |

Dont Worry ,, Dont Leave CP ,Something Big will be ready for you in future.

→ Ответить

13 месяцев назад, # ^ |

yeah I'll come back when I enter university, now maths and physics for my university entrance test is my main focus

→ Ответить

13 месяцев назад, # ^ |

thank you.

→ Ответить

rope_and_snake

13 месяцев назад, # |

D and E are too tough for me. Hopefully my current points are sufficient to become dark blue after the round.

→ Ответить

flying

13 месяцев назад, # |

+48

Worst contest I've ever seen!

What is the point? Details and implementation?

Please be aware of your problem's quality before you bring it out!

You are wasting 20000+ people's time and feeling!

→ Ответить

13 месяцев назад, # ^ |

← Rev. 2 →

+12

I suppose you refer to Div1C problem, yes it's problem mainly about fast and correct implementation, but it's surrounded with B and D which involve almost zero implementation, so what's the problem of having one problem where you need to be actually careful about impl?

→ Ответить

vuhuydiet

13 месяцев назад, # |

← Rev. 2 →

+13

Div2D was too easy to be D!

→ Ответить

lecxe

13 месяцев назад, # ^ |

Can you please tell how to solve it?

→ Ответить

vuhuydiet

13 месяцев назад, # ^ |

← Rev. 4 →

-11

First, sort b. Iterate through a from begin to end, and if we meet any a[i] that is <= b.back(), just insert b.back() before a[i]. Then, if after iterating the array a, b is not empty, just insert the remaining element to c. This ensures that the LIS of a will only be increased by at most 1

→ Ответить

omsincoconut

13 месяцев назад, # ^ |

Sort b. greedily insert b from large to small before the first a[i] that is less than or equal to the current b you're inserting

submission

→ Ответить

13 месяцев назад, # ^ |

+47

I spent more time thinking on it than on three others problem I've solved combined :)

→ Ответить

650iq

13 месяцев назад, # |

What was that A ^-^

→ Ответить

yuokkotsu

13 месяцев назад, # |

← Rev. 3 →

I love this contest, because it is very tasty!

→ Ответить

Loganwick

13 месяцев назад, # ^ |

lol who is tasty?

→ Ответить

yuokkotsu

13 месяцев назад, # ^ |

I knew english bad( sorry

→ Ответить

surajiyer

13 месяцев назад, # |

How to solve C?

→ Ответить

asdasdqwer

13 месяцев назад, # ^ |

You realize that if a fixed point gets selected, it basically goes to the last position of the array. That means that if you want to reverse the moves, you have to start at the last position, to then look which element becomes the last element after the next iteration etc. You can turn this into a functional graph, on which you do binary lifting with k steps. One case that you have to look at is if a_i > n, then there is no edge from this node going out.

→ Ответить

Trippie

13 месяцев назад, # ^ |

you don't need binary lifting

→ Ответить

asdasdqwer

13 месяцев назад, # ^ |

Yeah, I just realized that

→ Ответить

13 месяцев назад, # |

+10

1A is interesting, 1BCD is implementing race.

→ Ответить

adityagamer

13 месяцев назад, # |

+33

Errichto leaked the solution of problem A: https://www.youtube.com/watch?v=F4rykKLcduI&t=374s The question was similar though

→ Ответить

SecondThread

12 месяцев назад, # ^ |

This may be the most spoiled solution in all of history. I read it today and had to double check the date of the contest thinking there was no way a question like this would get through testers if 1.2 million people have seen it before.

→ Ответить

Folka

13 месяцев назад, # |

Best Interesting contest Ever, I love it. But the worst thing that from problem A to D in Div.2 was leaked in youtube and this thing waste others effort So be good and don't copy answers " You are just deceiving yourself :)"

→ Ответить

ExplodingFreeze

13 месяцев назад, # |

-7

What is Div1 lol, B > C > D in terms of difficulty. Most of my time on Div1D was trying to prove why the obvious approach wouldn't work since it feels way too easy for its spot in the contest.

→ Ответить

_Lactosi

13 месяцев назад, # |

I think the contest was great. Maybe its true that D was too easy but I am happy for my first A-D in a Div2 round

→ Ответить

_apurv_

13 месяцев назад, # |

Wow, this was a very weird contest for me. I don't know why but I stumbled so hard on the first problem itself.

→ Ответить

kurony

13 месяцев назад, # |

Where did the [3,2,3,4,3] array come from in the first test case example on https://codeforces.me/contest/1894/problem/C ?

→ Ответить

13 месяцев назад, # |

Very nice problems! I also seem to remember I liked some div2 contest from you. Well done!

→ Ответить

13 месяцев назад, # ^ |

+11

Thanks a lot! glad to hear it

→ Ответить

UP84

12 месяцев назад, # ^ |

Screencast Um_nik ?

→ Ответить

yy_chen

13 месяцев назад, # |

+15

I feel that div1D is too easy, and it can be easily implemented using a greedy simulation approach.

→ Ответить

__shaun_0124

13 месяцев назад, # |

+58

Div. 1C seems too straightforward for a Div.1C, you can basically figure out 80% of the solution right after reading it.

→ Ответить

E869120

13 месяцев назад, # |

← Rev. 6 →

Some people says that problem Div1B/Div2D is implementation heavy, but here is my solution:

Sort array $$$[b_1, b_2, \cdots, b_m]$$$.
Now we can assume $$$b_1 \geq b_2 \geq \cdots \geq b_m$$$.
For $$$i = 1, 2, \cdots, n$$$, do the following thing (initially $$$\text{cur} = 1$$$):

While $$$b_{\text{cur}} \geq \max(s_i, s_{i+1}, \cdots, s_n)$$$ is satisfied, append $$$b_{\text{cur}}$$$ to answer and add $$$\text{cur}$$$ by 1.
Append $$$a_i$$$ to answer.

Lastly, append $$$b_{\text{cur}+1}, b_{\text{cur}+2}, \cdots, b_m$$$ to answer.

For example, if arrays are $$$a = [7, 4, 5, 1, 2]$$$ and $$$b = [3, 9, 8, 0, 6]$$$, the answer is as follows:

First, sort the array $$$b$$$. The array will be $$$[9, 8, 6, 3, 0]$$$.
Then, add all elements in $$$b$$$ which is greater than $$$\max(a_1, a_2, a_3, a_4, a_5)=7$$$. The current answer is $$$[9, 8]$$$.
Then, append $$$a_1$$$ to answer. The current answer is $$$[9, 8, 7]$$$.
Then, add all elements in $$$b$$$ which is greater than $$$\max(a_2, a_3, a_4, a_5)=5$$$. The current answer is $$$[9, 8, 7, 6]$$$.
Then, append $$$a_2$$$ to answer. The current answer is $$$[9, 8, 7, 6, 4]$$$.
Then, add all elements in $$$b$$$ which is greater than $$$\max(a_3, a_4, a_5)=5$$$. Nothing will be added.
Then, append $$$a_3$$$ to answer. The current answer is $$$[9, 8, 7, 6, 4, 5]$$$.
Then, add all elements in $$$b$$$ which is greater than $$$\max(a_4, a_5)=2$$$. The current answer is $$$[9, 8, 7, 6, 4, 5, 3]$$$.
Then, append $$$a_4$$$ to answer. The current answer is $$$[9, 8, 7, 6, 4, 5, 3, 1]$$$.
Then, add all elements in $$$b$$$ which is greater than $$$\max(a_5)=2$$$. Nothing will be added.
Then, append $$$a_5$$$ to answer. The current answer is $$$[9, 8, 7, 6, 4, 5, 3, 1, 2]$$$.
Lastly, append all remaining elements. The final answer is $$$[9, 8, 7, 6, 4, 5, 3, 1, 2, 0]$$$.

→ Ответить

13 месяцев назад, # ^ |

+15

Full solution apart from declaring these objects — very implementation heavy xddd

→ Ответить

tfg

13 месяцев назад, # ^ |

I just guessed my solution, thank you for a nice way to prove it.

→ Ответить

adityagamer

13 месяцев назад, # |

← Rev. 2 →

What's the solution to problem E?

My approach was to check for a fixed len was to check number of elements of value len we are forced to take for every multiset. These values will change only in multisets in which element len is present, so I am recalculating in that only and I am handling overflow by using int128. And I am checking for len E [minimum len, min(min len+m+1, maximum len)] Is the WA on test 2 related to int128?

→ Ответить

13 месяцев назад, # |

-13

This was a decent one. Thanks a lot for the problemset. Hope i can reach CM...

→ Ответить

13 месяцев назад, # ^ |

Fingers crossed... I have +133 by predictor, but i need +134...

→ Ответить

surajiyer

13 месяцев назад, # ^ |

Congratulations!

→ Ответить

13 месяцев назад, # ^ |

Thanks a lot, man)

→ Ответить

13 месяцев назад, # ^ |

+12

congrats with CM!

→ Ответить

13 месяцев назад, # ^ |

+10

Thanks! All because of your round. I really like your problems, keep it up! <3

→ Ответить

Keshi

13 месяцев назад, # |

+96

Who let him cook?!

→ Ответить

sdyakonov

13 месяцев назад, # ^ |

+13

74TrAkToR )))

→ Ответить

RDDCCD

13 месяцев назад, # |

+52

implementation round and speedforces. Not a good idea to put all these tasks in one round.

→ Ответить

13 месяцев назад, # |

-12

I was bamboozled by D, worth a ton of points, but easier than B and C xd

→ Ответить

sstrong

13 месяцев назад, # |

+25

It turns out that I've submitted two exactly the same solutions to problem Div.1 B 231765593 and 231765621 due to internet connection errors on the cf side and they counted as a resubmitted solution, so the corresponding penalty (-50) applied. Is it possible to cancel one of these submissions so that the penalty would not be charged (because under normal conditions codeforces would not allow submitting exactly the same code twice)? sevlll777

→ Ответить

13 месяцев назад, # ^ |

One of the submissions have been ignored, should be ok now

→ Ответить

sstrong

13 месяцев назад, # ^ |

Thanks!

→ Ответить

KM_Parvez

13 месяцев назад, # ^ |

Same here. I submitted solution 231748393, but I couldn't find it in the status queue or my submissions page. I refreshed the page again and again, waited for a few minutes, but my submission list was still empty. Then I submitted 231749171 again. Suddenly, both submissions appeared in the submission list. The server issues had a significant negative impact on my overall experience with this contest, and I must admit I didn't enjoy it at all.

→ Ответить

holy_crap

13 месяцев назад, # |

-10

Really nice contest and interesting problems. Thanks a lot!!!

→ Ответить

MASTERB4APRIL

13 месяцев назад, # |

Problem A must be 3500

→ Ответить

13 месяцев назад, # |

+368

I would not say that this is the worst contest I've ever seen in my life. Cause apparently, there are also many, many, 74TrAkToR rounds before.

→ Ответить

ryzen9

13 месяцев назад, # |

← Rev. 2 →

-9

sevlll777: I hope you will like the problemset and ideas hidden in the problems! It's guaranteed that statements are understandable, short, and, of course, ✨ stylish ✨.

Div2A: What is the point of put "It is guaranteed that the given sequence of plays corresponds to at least one valid game scenario, for some values of X and Y" and "? — if it is impossible to determine the winner of the game" together in statement? It's not short enough?

→ Ответить

13 месяцев назад, # ^ |

+21

what? it's key part of the statement

→ Ответить

ryzen9

13 месяцев назад, # ^ |

-10

This is November, not April. This is normal round, not April Fool round! Why do you make statement like that? Someone will keep thinking about which test cases will be output "?" and waste much time and someone will just try to guess the solution and don't know why it works :)

→ Ответить

13 месяцев назад, # ^ |

I think you have some fundamental issues with understanding problem statement, or I completely not understand you.

→ Ответить

physics0523

13 месяцев назад, # |

← Rev. 2 →

I feel almost A(21min) = B(34min=55-21) = C(27min=82-55) = D(22min=104-82).

A: Interesting, but little bit heavy implementation for D1A. (my approach is SCC+BFS)
B: One idea task, but it's not easy like AGC-A. Great!
C: Small data structure, but it's almost logic test.
D: PROOF BY AC (I think it's around 1500pt to just get AC)

And one another thing, it seems no one got FST in Div1. Congrats!!

→ Ответить

13 месяцев назад, # ^ |

+86

You might want to look at some other implementations of A...

→ Ответить

Lynkcat

13 месяцев назад, # ^ |

+23

Problem A actually only needs to be considered backwards.

→ Ответить

early-morning-dreams

13 месяцев назад, # ^ |

-12

lmao

→ Ответить

kozliklekarsky

12 месяцев назад, # ^ |

← Rev. 2 →

Unfortunately, I have a good friend who got FST on D1A :(( (and is div. 1)

→ Ответить

ram.bhakt

13 месяцев назад, # |

-19

great contest!!!

→ Ответить

13 месяцев назад, # |

-20

Kinda feels like people who say that the problems are obvious implementations mean that there is an easy-to-believe greedy... For example, it would be very nice to see an easy solution* (and by that I obviously mean that you can rigorously prove it, otherwise it is a heuristic, not a solution) for the problem (div1) D. And B. And C.

→ Ответить

13 месяцев назад, # ^ |

+71

The problems itself are all fun imo, but it's questionable that making a contest full of this type of problems is good or not.

Contests serve more than just a list of problems, splitting those into several contests, adding different types of problems can both make the contests better and those problems be more enjoyed by participants

→ Ответить

13 месяцев назад, # ^ |

-13

Which problems are supposed to be similar in this contest according to you? And what other kinds of problems you think would improve this contest?

→ Ответить

13 месяцев назад, # ^ |

← Rev. 2 →

Something like "spending time on draft and find a set of super cool observations, then implement in <=5 minutes without any detail"

→ Ответить

13 месяцев назад, # ^ |

I think C and E are both of that kind... Well, E is not 5 minutes, but not far.

→ Ответить

13 месяцев назад, # ^ |

-8

I will try 1E tomorrow... Maybe you are right, it's my skill issue.

→ Ответить

Dominater069

13 месяцев назад, # ^ |

← Rev. 2 →

C is? What is the cool observation in C? The 1e9 variables made to make the problem look difficulty? Did you mean B? Also, unless youre top 10, its more like ~15mins implementing C

→ Ответить

12 месяцев назад, # ^ |

Looks like I'm in the minority here, but for me C was an interesting problem and I didn't get it right away. My first thought was about knapsack-like DP, because we need to achieve a particular size of the resulting set. And the fact that you can take everything but then greedily remove items to get to the correct size was a nice observation. Then to finish it off you need to realise that you can do it only for the sets with this number present, which makes the complexity proportional to the input size. For me that's an interesting sequence of steps.

→ Ответить

13 месяцев назад, # ^ |

← Rev. 2 →

+12

Just like others have said, the implementing difficulty between two correct approaches can be huge, thus resulting in the B solution one thought of could be a lot harder that the D he found out. If you can always think of the easier solution then it's fine, but for middle-level contestants the experience can be frustrating

and the bad experience is based on the fact that there's a relatively high possibility one can find himself not solving in the right order, which can't happen if there's only one(or two?) problems of this type in one problem

upd: the type i'm talking about, is that 'the implementing difficulty between two correct approaches can be huge', and some other features i will explain in the reply

→ Ответить

13 месяцев назад, # ^ |

First of all, I don't think that your comment answers any of my questions. I don't see how your answer is even connected to the topic discussed, which was "making a contest full of this type of problems". What is the type?

Second, do you think that all possible solutions to B should be easier to implement than all possible solutions to D?

→ Ответить

13 месяцев назад, # ^ |

if the D requires a lot of thinking then it's fine to have a harder-to-implement B, but you should notice that the problems in this contest also have one thing in common, is that you can get a solution right after you finish reading the statement, the only thing deciding the implement difficulty of your solution is if you noticed some 'observation' at the first glance. I'm assuming here that in a short, rapid-paced contest like CodeForces you won't continue thinking of another solution if you actually have got one and it's not uninplementable like a 10K code.

→ Ответить

13 месяцев назад, # ^ |

You must be very good, because the only problem from this contest that I solved right after finishing reading was A.

→ Ответить

13 месяцев назад, # ^ |

Fine but it's really clear, that a lot of contestants get to the harder-to-implement solution before the easier one

→ Ответить

13 месяцев назад, # ^ |

+18

I don't see an issue with that.

→ Ответить

13 месяцев назад, # ^ |

+23

Or actually maybe there can be a problem pool stuff like to collect problems rejected because breaking balance of a single contest and reuse them together later. Making it way easier to improve a round's quality, and maybe also making it possible for harder rounds to happen more often

→ Ответить

13 месяцев назад, # ^ |

+23

So what should I do when I found a heavy-implementing but provable solution?

For common rounds, I spent around 3 minutes for some easier implementation and it has worked for 90%+ times.

However in 74TrAkToR rounds I felt there is a huge gap between "a correct solution" and "a easy-to-code solution".

→ Ответить

13 месяцев назад, # ^ |

← Rev. 2 →

+41

I don't understand what is there to prove in C (since I just explicitly determine all possible results) and B (since it is obvious why it works once you get an idea). C is just straightforward from the construction and I guess there is no way to think of the algorithm for B without getting understanding equivalent to the proof of its correctness

For D, well — I didn't have a rigorous proof, but I had near certainty that what I've done is correct. I think this is a valuable skill to estimate what is the probability of your algorithm being right in the absence of a formal proof and I didn't have any doubt regarding that while implementing that.

I go through shelves in arbitrary order, fill each shelf from left to right and always put a cube of the color with the highest number of unused cubes out of these colors that I am allowed to put right now. Seems quite obvious that you wouldn't want to put any less frequent one, because why would you want to do it? At this point any two colors that I am able to use right now are completely symmetrical, no past affects them in any way, so my intuition tells me that this is >95% correct before attempting any proof.

But yeah, rigorous proof is not obvious I guess. Let's say that the most frequent allowed color is $$$A$$$ and has $$$x$$$ cubes in it, but we decided to use less frequent color $$$B$$$ with $$$y<x$$$ cubes in it. Let's create a sequence of occurences of A and B in the remainder of the current shelf (but include the B we've just put too) and all of the following ones in an arbitrary order. Look at the difference between number of As and Bs on all nonempty prefixes. The first number is -1, but it ends up being positive, so there is a moment where we go $$$-1 \to 0 \to 1$$$. This is a moment of two consecutive As such that the prefix ending on the first one has equal number of As and Bs. Let's flip that prefix. We get another viable configuration, where we put A instead of B in the first position, as desired.

Though that proof is just "for fun", it doesn't support my point or anything. But the fact that the past does not affect my choice in any way (as long as I restrict my current choice to allowed colors), so all allowed colors are symmetrical — is a very strong intuitive argument for why this is correct and I had no intention on wasting my time during the contest for the rigorous proof of that even though I am bit of a purist as well and sometimes get fever while listening to these "proofs by AC" as well

→ Ответить

BladeRunner

13 месяцев назад, # |

Would have been better if div2D/div1B problem had explicitly mentioned LIS contains strictly increasing elements :( Got solving the wrong problem the entire contest.

→ Ответить

Md_Masaud_Hasan

13 месяцев назад, # |

Div2 A should be better ;(

→ Ответить

Chiral

13 месяцев назад, # |

+19

If you think you're stupid:

231749854

→ Ответить

gin_spirit

13 месяцев назад, # ^ |

#include <bits/stdc++.h>
#include <initializer_list>
#include <scoped_allocator>
#include <system_error>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
//#include <gmpxx.h>
using namespace std;
typedef long long ll;
typedef long long int int64;
#define input(v) for(auto &i : v) cin >> i
#define line(x) getline(cin, x)
#define endl "\n"
#define exit exit(EXIT_SUCCESS);
#define revArray(x, n) reverse(x, x+n);
#define all(x)  x.begin(), x.end()
#define lowercase(s) transform(s.begin(), s.end(),s.begin(), ::tolower)

const long long MOD = 1e9+7;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    
    int t; cin >> t;
    while(t--) {
        int n; string s;
        cin >> n >> s;
        cout << s.back() << endl;
    }
    return (EXIT_SUCCESS);
}

→ Ответить

oursaco

13 месяцев назад, # |

round was a bit speedforces, but problems were nice!

→ Ответить

marat.snowbear

13 месяцев назад, # |

+38

I liked the problems, but statement of Div 1 C drives me crazy. Math-heavy explanation of simple things does not sound like fun. I don't mind the formal definition of things, though ideally they should follow the explanation you can relate to, not substitute it.

"Minimize anti-beauty" sounds like double negation in some sense, why inventing a word? If you follow the statement style it should've been called f(S). If you want to make it prettier, call it "ugliness of set" or "cost of set".

→ Ответить

13 месяцев назад, # ^ |

The idea was that beauty is something we naturally want to maximize, therefore anti-beauty is something we want to minimize :D but ugliness would've been better choice, you are correct, not good enough in english I guess

→ Ответить

Madhav_1608

13 месяцев назад, # |

third question was fabulous

→ Ответить

AT_80

13 месяцев назад, # |

← Rev. 3 →

Div 2A was inspired (perhaps a little too straightforward-ly) by this YouTube video (featuring Errichto)
Errichto's interview with Joma Tech

The question is mentioned by Kamil at 4:23, when he gives an example of competitive programming questions.
Seemed like a really fascinating solution to me even when I had first seen the video.
Side note: The hints in the Editorial mention tennis and volleyball, quite like how they were brought up in the above-mentioned video

→ Ответить

-is-this-cht-

13 месяцев назад, # |

A similar problem as problem A, with the same solution, was mentioned in this interview with Errichto

→ Ответить

PieArmy

13 месяцев назад, # |

yayy I became expert! Thanks for the contest.

→ Ответить

13 месяцев назад, # |

I'm not really sure about it, but I think that again I wasn't able to get AC because of worse constant factor ;_;

Got stuck on memory limit too. Especially (I think) the stuff about doing something like that:

void rec(int v) {
    if (v<=n) rec(v+1);
    if (condition) {
        //something that creates variables and releases them right after this block
    }
}

I've knew before that if it wouldn't be inside of an "if" statement then all the memory would be allocated right after entering the function and I guess that the existence of the "if" statement doesn't change much. Can somebody confirm?

I've discovered this fact painfully in other problem some time ago, where the condition was called only a few times, but because of this insta-allocation my solution was quadratic instead of something faster. Here it just made constant factor bigger (and memory complexity just like time is still linear), but ML also turned out to be too tight for me.

→ Ответить

tourist

13 месяцев назад, # ^ |

+133

I highly prefer generous time limits, especially when there is no unintended solution that the authors are trying to separate from the intended one, but they just arbitrarily decide to set the TL to be 2x or 3x of their implementation in C++.

To all other authors: please don't do that! Consider what solutions you are trying to allow, and what solutions you are trying to disallow. Consider other programming languages besides C++. Set the constraints accordingly. Time limit equal to the geometric mean of the slowest implementation of the intended solution and the fastest implementation of the unintended solution is a good starting point.

To sevlll777: thanks for setting all time limits to 3 seconds and keeping all constraints (except E) under $$$2 \cdot 10^5$$$. That's much better than setting $$$n \le 10^6$$$ and TL = 1 second for no reason.

However, to be fair about today's Div.1 E, an $$$O(n)$$$ solution is obviously possible if you just use DP and store all vertex/edge colors going out of the subtree in the DP state — the constant factor would be around $$$3^6$$$, though. So, in a sense, this problem is all about the constant factor.

→ Ответить

13 месяцев назад, # ^ |

Radewoosh's solution looks exactly like DP with matrix exp. So I would say this time TL was even too generous, considering that it is possible to get AC with it.

→ Ответить

13 месяцев назад, # ^ |

Well, still linear if it changes anything (actually $$$\mathcal{O}(n+\sqrt{d})$$$) with multiplying vector by matrix everywhere except for prepro. I don’t think that these matrices can be counted as “complexity”, as if numbers higher than 3 would be allowed then the model solution wouldn’t work anymore (as far as I understand it), so I think it’s still a constant factor.

→ Ответить

13 месяцев назад, # ^ |

Yeah, it's totally a constant factor. Your solution is absolutely linear, and mine is $$$\Theta(n \log C)$$$. I still think that you didn't solve the problem :)

→ Ответить

12 месяцев назад, # ^ |

+30

I see the point and it makes sense, so I was about to agree, but I thought more about it and I think that I won’t (at least without hearing anything more).

Let’s consider cases with 2 very different solutions to the same problem. How can they be different?

One has better time/space complexity — that’s an obvious one, we should somehow be able to distinguish them.

One has better time/space constant factor — that’s different than the one above, I don’t think that the solutions should be distinguished (if possible) — if this is the only difference between them then why should one be treated better while probably both can perform better depending on the implementation. Ofc I understand that sometimes we should stay sane with TLs to don’t let anything worse pass, but I don’t see what bad could’ve happened if E would have $$$n \leq 10^4$$$. Why I don't think that the solutions should be distinguished? I guess it's rather clear, but I'll address it in the final paragraph.

One is easier to implement — sounds nice, if you’re an author of course you are happier seeing nice and clean solutions etc., but from the view of the participant the other one is harder to come up with, so it’s a trade off for participants and again I wouldn’t say that one of them is more correct.

One of them is somehow smarter — I think this is the point in yesterday’s E. When you’re the author you also want to see that people have deeply understood your problem, that’s obvious, but what if they don’t? If this in the end goes to the previous point (about implementation time) then some participants should finish later and that’s it, but if you think that your solution really is the smarter one then… prove it, there are ways (AtCoder does it all the time). I could say that my solution is really “smarter”/“better” as it does not require thinking and it’s just coding (btw. I don’t think that ofc). As far as I understand if in yesterday’s E authors wanted to make use of the nice formulas, then why wasn’t it (for example) incremental problem (list of edges being added in order to the graph)? Model solution for each edge would store also the time that it appears and searching such final graph would give all the answers in not so much more complicated way. But the problem wasn't about it, the problem was static. I think that saying that I didn’t solve the problem because my solution wouldn’t extend here is like saying that you didn’t solve it because your solution wouldn’t extend for $$$n \leq 1000$$$ and $$$numbers \leq 7$$$ ($$$n$$$ is small so it wouldn’t take an hour to solve a testcase, it still would be linear).

So it comes up to the question “is it ok as an author to use the TL to set boundary for AC somewhere in the middle of the sequence/set/bunch of observations that you can make to make your solution simpler/nicer/faster up to constant factor (and each of these observations would improve one of these)?” I think in general it's considered kind of a dick move because you force the participants to squeeze their solutions in some (for example technical) ways and I also think like that. Of course, most of the times authors face some slower solutions (slower in terms of complexity) that they want to disallow and they can't set the timelimit as high as they want, but I think it wasn't the point yesterday as I don't think that with $$$n \leq 10^4$$$ something would change.

Summing up:

You didn't want to let me pass — why not incremental problem?
You wanted to let me pass — why TL and ML so small?

→ Ответить

12 месяцев назад, # ^ |

-13

as it does not require thinking and it’s just coding

That's it.

I am not being serious when I say "I still think that you didn't solve the problem :)".

From my standpoint it is obvious that you can do cactus DP with some constant-size matrix. Reasons why I consider it not to be a solution for this problem:
- The solution is obvious for div1E
- I would not approve such a problem
- The limitations are clearly turned out to the max to try to make this not fit in TL
- It is clear that the fact that there are only 3 colors is super important, and all the ways in which good coloring is constrained is also important

I understand that this is highly personal, and it seems that you care much more about winning than me. I don't participate in contests to write brainless algorithms, I participate in contests to solve problems. Author intent is important for me. And in this case I can see that author clearly knew about the existence of such a solution and tried to show that it was not intended. I listened.

You wrote a code that produces the correct answer without understanding why this problem is even set. I understood what the problem was about.

Your solution is valid and it is aligned with your understanding of competitive programming. It is not aligned with mine, and I think I have a right to this opinion. I do not agree with "Radewoosh didn't solve the problem", but I agree with "Um_nik thinks that Radewoosh's approach is not a legit solution to the problem".

About setting TLs and limitations: you have a maxim that complexity is the most important thing and having complexity not worse than intended automatically means that you solved the problem. I am more about the intent. If the author thinks that the model solution is better (in any sense chosen by the author: faster, more interesting, simpler etc.) and they can construct a problem proving that — they are good to go.

→ Ответить

12 месяцев назад, # ^ |

+18

Don’t get me wrong, I totally agree that the model solution is far nicer than the crazy dp and it makes me a little bit upset that a nice set of observations and a way to understand something is used in a way that allows omitting it.

I understand what you’re saying and I have to say that I’m kind of surprised about the differences in our understandings of the nature of CP. The stuff that you are talking about sounds to me exactly like things that differ CP and math competitions — understanding the problem fully/blah blah (blah blah isn’t meant to be offensive) vs coming up with correct and fast enough algorithm/coming up with creative ways to surpass standard ways and just pass all the tests (I mean for me that’s the difference). Maybe not even coming up with correct algorithm but implementing it, cause you don’t need to know anything about proofs. So it’s kind of right that I see the “nature of CP” in a different, more mechanical way (in practice it often varies, because of these creative ways).

→ Ответить

12 месяцев назад, # ^ |

I completely agree with your summation. I had to make the problem incremental, but I didn't do it because of my stupid prejudices. It was a big mistake from my side, and I will try to not repeat in the future.

→ Ответить

12 месяцев назад, # ^ |

+20

I actually don’t think that it’s a big mistake, but rather that it could’ve been done in a better way in my opinion/I would do it differently. By “my opinion” I mean assuming that “complexity not worse than model should get AC”, so I have some (my own) understanding of, huh, conventions (?). I figured out that if people kind of read what I post, then it’s ok to write some actual thoughts which might be useful for someone, that’s why the message was so long, not to offend you or anyone in any way. Every problemsetter went through a lot of smaller or bigger fuckups (definitely including me) so I guess it’s nice to share insights.

→ Ответить

13 месяцев назад, # ^ |

Oh my god, am I the only one with a normal solution without cactus DP?!

→ Ответить

13 месяцев назад, # ^ |

← Rev. 2 →

Well, maybe you can argue that your solution is "clever"/"tricky", but the word "normal" belongs to cactus DP imho :p. It's easy (to think of) and natural and does not need to take advantage of the quirks of the statement which was very carefully adjusted so that these arbitrary facts somehow work out into a solution, while the dp solution does not care and can be adjusted and generalized however you want.

I remember that a year ago Polish ICPC contest featured a problem where a standard solution with $$$O(n log n)$$$ time and memory could have been applied. But they added a weird constraint that the graph contains a 1-2-3-...-n-1 cycle and that the values on edges are up to 50000 (the general solution does not care about these at all), so that they can then solve the problem in some acrobatic adhoc way giving $$$O(n \sqrt{D})$$$ (D was a range of values) time and the only advantage of it was that it got $$$O(n)$$$ instead of $$$O(n log n)$$$ memory and they set the memory limit specifically low. I was ... not amused

→ Ответить

schmosby

13 месяцев назад, # |

so ✨ stylish ✨

→ Ответить

Powerful_Orkhan

13 месяцев назад, # ^ |

Yesss bro

→ Ответить

AboNageh

13 месяцев назад, # |

← Rev. 2 →

Deleted

→ Ответить

liympanda

13 месяцев назад, # |

-8

The overall difficulty distribution for the Div 1 is more like a Div 2 contest.

Normally Div 1 contest has several 3000+ problems. But we only have 1 this time.

Actually E is hard, Which makes the gap between D and E huge.

→ Ответить

13 месяцев назад, # ^ |

← Rev. 2 →

+44

Just clarifying: there was a problem F in Div1 during almost all of testing phase. But we decided to cut it a week before contest, to make contest more fitting in 2 hours round. Tho D turned out to be easier than expected, and point about gap is very fair. And Div1 usually have 2+ hard problems when it's duration is at least 2:30.

→ Ответить

Iratis

13 месяцев назад, # |

-18

I think the problem D should appear in MO but not OI.

→ Ответить

mike_frank11

13 месяцев назад, # |

i want to know why all numbers is same ,ans is -1 i do not understand

→ Ответить

Valenz

13 месяцев назад, # ^ |

Because you don't have enough pair of numbers to fulfill 2 requirements.

→ Ответить

Powerful_Orkhan

13 месяцев назад, # |

Nice problems ... Thanks !

→ Ответить

Your_Hands_Clean

13 месяцев назад, # |

Thanks for this round. But the statement of task A wasn't short.

→ Ответить

cleanser

12 месяцев назад, # |

Took me almost 2 hrs to solve C during the contest, but after the contest, solved D in around 15 minutes. :(

→ Ответить

12 месяцев назад, # |

LOL, the problem A in Div2 xDD I've heard it so many times, it's a running joke among my friends lol

→ Ответить

Farsh_LE

12 месяцев назад, # |

A is the hardest problem in DIV2 LOL

→ Ответить

ryzen9

12 месяцев назад, # |

-12

Statement in Div2 A problem belike

→ Ответить

kozliklekarsky

12 месяцев назад, # ^ |

-10

Get a life

→ Ответить

VatsLakshya

12 месяцев назад, # |

@sevlll777 in question A of this contest .Suppose we have a case where AAAB (or let's say)AABB

then for which x and y will B win these cases?

→ Ответить

ibrahimwq

12 месяцев назад, # ^ |

← Rev. 2 →

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

but sequences which you give are invalid

→ Ответить

VatsLakshya

12 месяцев назад, # ^ |

oh yes i forgot about that line .

thanks for your help.

→ Ответить

12 месяцев назад, # |

← Rev. 2 →

Update : Deleted

→ Ответить

12 месяцев назад, # ^ |

← Rev. 2 →

Upd : Deleted

→ Ответить

12 месяцев назад, # ^ |

← Rev. 3 →

Upd : Deleted

→ Ответить