why my submission page is not loading? When I am opening the page it shows Your text to link here...

What dose "dp" stand for? I thought it cannot be "dynamic programming"

amazing round!

For This, I guess my logic is same but there is actually no need to harcode stuff, though It is something very tedious. Here is my code 192350442

Ps: On a seperate note who is she on your cf dp?

Wow clean and smooth implementation

Excellent Contest,Thanks for Tourist Cooperation For this Wonderful contest And especially for the first 4 problems

Tgod!!!i love you.This is my first time to reach the top 600.

See my comment Although it's not elegant, I think it's easy to understand.

It's graph problem

Agreed.

Guess I'm too Indian to understand this.

Thank you!

However personally I think this may just be a coincidence and could not prove anything.

the second testcase is 4 1 5 4 1 1 and rearranging it we get 1 1 4 5 1 4.

damn, nice to see you on cf wilo

1B's implementation is too horrible. I think there is no need to output the sequence of exchanges, it does no good but making this problem a lot more difficult to implement.

i am also facing some problems, sometimes it works sometimes it gives error

Heh, Heh, Heh, aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

well it's broken for me and i don't know why

The implementation may not be ugly if you organize your code well. Maybe you can refer to this code by jiangly. The code is neat and it only took him 10 minutes.

1D can be solved in dynamic programming and polynomial tricks in $$$O(n\times 2^n)$$$ time, but I've heard there exists other solutions which do not require polynomial or the modulo $$$998244353$$$.

my first div2. really good

How to solve the "Letter Exchange"?

In both the problems you only need to resolve the cycles of length 2 then cylces of length 3.

For cycle of length 2: If suppose $$$ith$$$ person needs $$$w$$$ and it has an extra $$$i$$$ and if the $$$jth$$$ person needs an $$$i$$$ and it has extra $$$w$$$, we can perform the swap and both will be satisfied in 1 operation. We can do this for all possible combinations of letters.

For cycle of length 3: If suppose $$$ith$$$ person needs $$$w$$$ and it has an extra $$$i$$$ and if the $$$jth$$$ person needs an $$$i$$$ and it has extra $$$n$$$, and if the $$$kth$$$ person needs $$$n$$$ and it has an extra $$$w$$$, we can first perform the swap between $$$ith$$$ and $$$jth$$$ person so now $$$ith$$$ person needs $$$n$$$ and it has an extra $$$i$$$, then we can perform the swap between $$$ith$$$ and $$$kth$$$ person. So all three will be satisfied in 2 operations.We can also do this for all possible combinations of letters.

So I'm really interested in how to solve 1B so fast.

well I spent about 1.5 hours on 1B and when I saw 1D I thought I should solve that problem in the first place instead of 1B. My solution to 1B is horrible and I rewrote my code twice, once because of my algorithm is incorrect and the other because I got sick of the rubbish code I had written.

I liked the contest, thank you tourist for the problems!

In DIV2 C, the only observation is that we should perform the query of 2 as the last move, right?

**Proof : ** Let's suppose we make a "chain" of 1, 2, 3, .., x and we have some element remaining y(y > x + 1) then after the operation 2 we'll be left with only y — x and if we'll need y — x type 1 operations now but if had we made it x + 1 earlier then y — x — 1 type 1 operations would've been needed

lemme know if something seems wrong.

I have the same question. Maybe tourist also surf foreign websites? (wwwww

I don't get it.

but there is a huge score difference, for example 750 points between D and C so it's kinda justified

omg tourist round!!!

If I understand correctly, all the people are nodes and an edge is connected between someone who needs and has excess of the same letter? In this case why can't the size of the cycle be more than 3?

how it is similar, can you please elaborate sir

Why i can't upsolve?

omg tourist round

Is div1-A's sample2 made by tourist himself?? I'm astounded him using Japanese internet meme how did he know that??(I know that it's well-known in Chinese...)

Problem D writing a perfect code, to getting RE on test 19

Reason: I wrote an assert statement to debug the TLE cause in the local machine Locking the problem and realizing I can't change this

My AC code

I don't know if there exists some elegant solution (I've seen some simple-ish ideas by people but not full solutions), but I personally had to write (and copy-paste) over 200 lines of code (I believe there has to be something simpler) to cover all cases.

I tried using bit-masking (coding needs and excesses as bits, 64 possible states in total, the first 3 bits for needs of w, i, and n and the other 3 for excesses). The observation I made was that there can be only 2 kinds of moves, i-j and i-j-k.
My implementation however got the better of me considering there were 9 unique cases in total, the code could have easily exceeded 600 lines if I had continued, lol.
Could you share your approach?

Here is a problem with same idea as today's Div1B/Div2D in case anyone is interested.

Problem

In brief solutions for all div2 (except B) problems and Div1 A-D

I counted all combinations and greedily matched those that benefit both people
After that greedily matches those that benefit only one of them

Any hints / elegant approaches on solving div2-d?

One of the most unbalanced rounds (Div. 2) in a while.

Div1E, not Div2E

Can you tell your approach? I thought this was similar to the question where we had to distribute equal number of ones among all rows, but just with 'w','i' and 'n'. But I had no idea how to implement it, if it even is correct in first place

My solution of D is a very ugly implementation

You do a dp of size $$$n \times 2^n$$$, where $$$dp[i][j] = $$$ number of ways that the number $$$j$$$ leads (is the highest value) a group of size $$$2^i$$$, and will lose all matches after this. Solve this dp top down.

Here's a snippet of the solution

dp[n][(1<<n)-1] = 1;

	for(int i = n-1; i >= 0; i--){
		ll cumulative = 0;
		for(int j = (1<<n)-1; j >= 0; j--){
			dp[i][j] = (cumulative*2) % MOD;
			cumulative += ((dp[i+1][j] % MOD) * (binom_choose(j-(1<<i), (1<<i)-1) * fact[1<<i])%MOD)%MOD;
			cumulative %= MOD;
			// cout << i << " " << j << " " << ndp[i][j] << ln;
		}
	}

couldn't get ac because coded too slow... :(

Was div2D ugly implementation?? There was a huge gap no of solves for b and d. I have no idea how to even start approaching D

I've simulated this approach for some example cases. Maybe we should add an adge pointing from a "extra" char to a "lack" char, for example, "www"-->(w->i),(w->n), "iiw"-->(i->n), where (char1->char2) is an edge pointing from char1 to char2.

Then we would get a directed graph with nodes {w,i,n}, each node has equal in-degree and out-degree. We can regard a exchange as cancelling 2 edges with same nodes and different direction, like (w->i),(i->w) --> nothing; or merge a path of 2 edges into 1 edge, like (w->i),(i->n) --> (w->n). We need to store the index of people in edges. To achieve the minimun number of operations, we need to use as more the first operation as possible. Therefore, first we cancel every pair of (w->i),(i->w) until one of them runs out, similar for (i->n),(n->i) and (n->w),(w->n). Then if there're edges remained, by the property of in-degrees and out-degrees, they must form some cycles like (w->i),(i->n),(n->w), or reversely, (w->n),(n->i),(i->w), we need to do 2 operations for each cycle.

Mistaken, ignore.

why so worry about rating?

is this approach correct for B? align the first cake with the first dispenser, such that a1-w=b1-h, then for the rest of n-1 cakes check if you can move them to the left by less or equal to (a1+w)-(b1+h) so that they are aligned with their dispensers, if ever needed to move the cake to the right the answer is "no" otherwise "yes"

Yes that's it

Though my problems were comparatively easier but still I was able to solve only 1

Can anyone explain to me how to solve problems E and F on Div2? Thank you so much.

Oh, didn't FST. So my rating won't drop too much.

Based on previous experience, will be after about 1 week.

what is FST?

How t solve 1D?

Cool round!))

we are on the same boat

where editorial?

"If there are multiple solutions, print any", this sentence was missing at the beginning in 1B, that was bad.

If problem setter is tourist, We expect better Contest, but I can say, this is the worst contest, I have ever given. Respect to tourist but Worst Contest ever seen... Mainly Problem D

C, D and F are interesting, E is quite standard, and B is too hard for me.

So when will system test begin?

My username is pretty much how i felt during the entire 3 hrs.Last tourist round for me.

Thanks :)

cf carrot extension

Even after that you completed the contest withing 2 and half hours , really appreciating.

What programm do you use to see performance?

YES ~ tourist probably

Same here, pretty much hardcoded everything only to get WA in the end for D

And a typo: not -> now

you don't really need to find x, but just need to get hold of a range ie. l,r such that l<=x<=r and then if l>r then output no otherwise yes

Is this is a implementation problem?

I used a super ugly implementaion with upto 30 lines hardcoded data.

I don't want to solve problems like this again.

It seems that here's a pretty good solution with graph theory:

build a three-node graph. when it's 'wwi', link w to i, when it's 'www', link w to i and w to n. and so on.

Finnally match edges with same endpoints but different directions firstly. then cycles with length 3 remain.

The submissions are not public yet.

Which browser are you using?

I just wrote the ugliest code of my life for problem D (B for div1): 192346636 Didn't really like this problem, and C was too easy, it should have been B. Other that these, I enjoyed the contest, although I would have loved to have time for E :(

why I am not able to submit solutions, it says contest is over even though 80 mins are left? Is it so that you have to participate in initial rounds so as to participate in the Final Round? It does display System Check is Pending.

Me too!!Got stuck and got 9 WAs :(

my suggestion after this,1782,1561: avoid vk cup rounds for boring implementation problems and random performance

Which extension/website you use to get predictions? CF preictor extension is currently now working for me.

Please give some hint how to solve problem 2D.

C was too hard for me ;)

Was Div1C a seg tree + binary search (based on the idea that after some time some numbers are fixed)? I could not come up with easier solution.

Why did you put a trivial 12D DP (= easy idea, looooong implementation) as Div1E? It's not funny.

Wait till the System Testing gets over.

Really interesting div 1 contest, thanks!

Does the problem 2D involves case work on bitmask? or this is graph problem?

very hard problems

If my solution failed for a HIDDEN PRETEST, (like Pretest 2), how much time after the contest can i see that testcase? Because the contest has ended, but I cant see the testcase which went wrong.