0
why my submission page is not loading? When I am opening the page it shows Your text to link here... |
0
What dose "dp" stand for? I thought it cannot be "dynamic programming" |
0
amazing round! |
0
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? |
+1
Wow clean and smooth implementation |
0
Excellent Contest,Thanks for Tourist Cooperation For this Wonderful contest And especially for the first 4 problems |
+1
Tgod!!!i love you.This is my first time to reach the top 600. |
0
See my comment Although it's not elegant, I think it's easy to understand. |
0
It's graph problem |
+1
Agreed. |
+2
Guess I'm too Indian to understand this. |
0
Thank you! |
+3
However personally I think this may just be a coincidence and could not prove anything. |
+2
the second testcase is |
0
damn, nice to see you on cf wilo |
0
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. |
0
i am also facing some problems, sometimes it works sometimes it gives error |
+19
Heh, Heh, Heh, aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa |
+3
well it's broken for me and i don't know why |
0
|
0
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$$$. |
0
my first div2. really good |
0
How to solve the "Letter Exchange"? |
0
In both the problems you only need to resolve the cycles of length 2 then cylces of length 3. |
0
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. |
0
So I'm really interested in how to solve 1B so fast. |
0
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. |
+6
I liked the contest, thank you tourist for the problems! |
0
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. |
+3
I have the same question. Maybe tourist also surf foreign websites? (wwwww |
0
I don't get it. |
0
but there is a huge score difference, for example 750 points between D and C so it's kinda justified |
0
omg tourist round!!! |
0
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? |
0
how it is similar, can you please elaborate sir |
0
Why i can't upsolve? |
0
omg tourist round |
+23
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...) |
0
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 |
0
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. |
0
Idea Resolve cycles of length 2 then resolve cycles of length 3 |
0
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. |
0
Here is a problem with same idea as today's Div1B/Div2D in case anyone is interested. |
+3
|
+1
I counted all combinations and greedily matched those that benefit both people |
0
Any hints / elegant approaches on solving div2-d? |
+2
One of the most unbalanced rounds (Div. 2) in a while. |
0
Div1E, not Div2E |
0
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 |
+5
My solution of D is a very ugly implementation |
0
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 Code
couldn't get ac because coded too slow... :( |
+11
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 |
0
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. |
0
Mistaken, ignore. |
0
why so worry about rating? |
0
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" |
+3
Yes that's it |
0
Though my problems were comparatively easier but still I was able to solve only 1 |
0
Can anyone explain to me how to solve problems E and F on Div2? Thank you so much. |
0
Oh, didn't FST. So my rating won't drop too much. |
0
Based on previous experience, will be after about 1 week. |
0
what is FST? |
0
How t solve 1D? |
0
Cool round!)) |
+3
we are on the same boat |
0
where editorial? |
+3
"If there are multiple solutions, print any", this sentence was missing at the beginning in 1B, that was bad. |
+24
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 |
+6
C, D and F are interesting, E is quite standard, and B is too hard for me. |
0
So when will system test begin? |
+3
My username is pretty much how i felt during the entire 3 hrs.Last tourist round for me. |
+1
Thanks :) |
0
cf carrot extension |
+1
Even after that you completed the contest withing 2 and half hours , really appreciating. |
0
What programm do you use to see performance? |
+17
My worst performance in a while T-T |
0
YES ~ tourist probably |
0
Same here, pretty much hardcoded everything only to get WA in the end for D |
0
And a typo: not -> now |
+5
1C It's easy to see that every time you have to move all the points such that all the places from $$$1..m$$$ are filled and $$$m$$$ is minimum. Let $$$f(x)$$$ be the number of $$$a_i$$$ such that $$$a_i <= x$$$. Let's call a point $$$a_i$$$ useless if $$$f(a_i) > a_i$$$ and $$$cnt(a_i) >= 2$$$ because in this case, you need not move the point at position $$$a_i$$$ to any other point and more than one point is sitting at position $$$a_i$$$. So, adding an element iteratively will create at most one useless point (if you remove all the useless points previously) and remove the current useless point if exists. Now the answer will be $$$sum(remaining points) - m*(m+1)/2$$$. You can implement this idea using lazyseg tree and find the useless point by binary searching on lazyseg tree. |
+9
Especially liked F |
0
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 |
0
Is this is a implementation problem? |
+5
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. |
+1
The submissions are not public yet. |
0
Which browser are you using? |
+2
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 :( |
0
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. |
0
Me too!!Got stuck and got 9 WAs :( |
+87
my suggestion after this,1782,1561: avoid vk cup rounds for boring implementation problems and random performance |
0
Which extension/website you use to get predictions? CF preictor extension is currently now working for me. |
0
Please give some hint how to solve problem 2D. |
+86
C was too hard for me ;) |
+10
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. |
+26
Why did you put a trivial 12D DP (= easy idea, looooong implementation) as Div1E? It's not funny. |
0
Wait till the System Testing gets over. |
+6
Really interesting div 1 contest, thanks! |
0
Does the problem 2D involves case work on bitmask? or this is graph problem? |
0
very hard problems |
+7
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. |
Name |
---|