Всем привет!
В эти дни в Москве проходит вторая Международная олимпиада мегаполисов — международное соревнование для школьников из крупнейших городов и столиц мира, одной из дисциплин которого является информатика. Над турами по информатике имели удовольствие работать члены члены жюри, приглашённые из Санкт-Петербурга, Минска, Алма-Аты, а также Московская методическая комиссия, известная вам по Московской командной олимпиаде, Открытой олимпиаде школьников по программированию и Московской олимпиаде для 6-9 классов (раунды 327, 342, 345, 376, 401).
Мы очень признательны MikeMirzayanov за разработку системы Polygon, которая делает возможным и очень удобным одновременный перевод условий на большое количество языков, и, по давней дружбе с замечательной платформой Codeforces, мы проводим параллельный рейтинговый Div. 1 + Div. 2 раунд на задачах соревнования.
Раунд состоится 6 сентября в 15:55 по Москве и продлится два часа. В каждом дивизионе будет предложено по 5 задач, разбалловка будет объявлена позднее.
В составе жюри олимпиады: andrewzta, GlebsHP, Endagorion, meshanya, Chmel_Tolstiy, Zlobober, Елена Андреева и Бахыт Маткаримов. Задачи олимпиады разрабатывали timgaripov, mingaleg, halin.george, vintage_Vlad_Makeev, malcolm, LHiC под руководством вашего покорного слуги.
Выбрать задачи для раунда помогал координатор Codeforces KAN.
Всем удачи и высокого рейтинга!
PS Мы просим всех, кто участвует или знает задачи с основного соревнования, воздержаться от участия в раунде и публичного обсуждения задач, в противном случае вы можете быть дисквалифицированы.
Поздравляем победителей!
В div. 1 это:
В div. 2 это:
Опубликован разбор. Всем спасибо за участие!
Note that round ends 5 minutes before CSAcademy Round #47, so you can participate in both of them if you want.
==============
Обратите внимание, что раунд заканчивается за 5 минут до CSAcademy Round #47, и вы можете успеть поучаствовать в обоих раундах, если хотите.
I'm afraid that my laptop chagre is not enough for 4 hours of competition.
==============
Я боюсь, моему ноутбуку не хватит заряда на 4 часа соревнований.
We postponed the start of the CS Academy round by 15 minutes.
Why this round called extraordinary? :)
I believe this means that the round will be rated differently. Not sure on the specifics though.
Some crazy things like "there will be subtasks" comes to my mind :)
I'm sorry to disappoint you, but there won't be any subtasks. Also, if there was any difference in contest format, most probably round wouldn't have been rated.
http://mirror.codeforces.com/contest/391 (however one may argue this was not rated because it was affected by Codeforces Blackout xD)
while searching for solution of http://mirror.codeforces.com/contest/854/problem/E i found a blog which is using a data structure called chair tree . i don't know anything about this data structure and nothing is on internet can u help me to provide some link about this data structure from where i can learn blog -- https://blog.csdn.net/DaF_alex/article/details/77542114
Is it rated on earth?
+1
This word is a translation of "внеочередной" and is used in the literal sense of it — "out of regular order", "specially arranged" (as you can see it's published the day before it takes place), as opposed to the more common meaning, "unusually good".
This translation of the word is bad but I can't think of a better one.
Yeah, makes sense. Thanks!
A better way to write is "Rated, extraordinary Codeforces ...". Still not so good but at least people would not have any doubt about rating.
3 contests in 3 days fantastic :)
Is the round rated?
Can you read?
I hope there won't be a geometry problem :D
Would be interesting to see the dependency between rating and not loving geometry. I'm pretty sure that yellow+ people don't care, while all the greens hate it.
Graphical Illustration :)
Forgive my paint skills.
why you have to be mean to him ?
He wanted to see the dependency between rating and not loving geometry :(
Offtopic Codeforce is missing emojis :D
i don't mean you i mean him why he has to be mean to people with lower rating
Because he is Purple..? The Evolution Of Codeforces
Mathforces -> implementationforces -> geometryforces -> ColorForces
I would beg to differ. Geometry is rather hated all around the world by vast majority of people. The thing is, green struggle to check whether n points are collinear and reds struggle with computing area of sum of pacmans by integrating border of regions with holes with border consisting of different arcs and segments :P. However I like geometry. I think that maybe geo problems are not as appealing as others but I have just simply forced myself to like it because somebody in our team had to do this :P. And dealing with all stupid corner cases and precision issues is never exciting.
I really hates geometry, so I'll be a great counterexample for that sentence :)
I don't get it that how a particular type of problems should be or can be hated. I mean, there are so many topics there, and if one is not comfortable with some topics or faces difficulties in solving problems regarding those, he/she shouldn't dislike/hate it. Every topic has its own beauty. I personally like geometry even though I am not so good at it. And I suck at DP. Does that mean I'd say "Why so many DP problems?" or "This round sucks because 2 DP problems appeared!"??? No, I wouldn't say that. I know most people are not that comfortable with geometry problems. So what? That doesn't make it bad. And as Swistakk said, Red coders face trouble with really tough geometry problems and Blue/Green/Cyan/Grey coders face trouble with simple problems. So, it depends on one's skill. And it can also happen that a very good geometry(or any other particular topic) problem solver is Green while a red coder is not so good with that topic. It can happen sometimes, maybe rarely. But personally I think, everyone should have basic knowledge of every topic. One should know how to check if n points are collinear and other basic geometry stuffs, and one should also know the basics of every topic that may appear in a standard programming contest.
yeah, but a contest shouldn't be ALL math and geometry. What if you had a contest consisting of 6 DP problems? Wouldn't be very diverse or fun.
No, I hate geometry.
not really. Thanks to those geometry problems my color changed from green to light blue. I love geometry problems :)
Good luck and high ratings for everybody
I just find there is only 2016 International Olympiad of Metropolises, day 1 in CF Gym
Would you please put "2016 International Olympiad of Metropolises, day 2" to Gym
I just wanted to solve the tasks of the last year, so decided to add them to polygon to test. And then decided to add to the gym also for the others. But I got bored and didn't uploaded the second day :)
I found the tests on the official site, so you can find them and upload to polygon, if you want.
That's my last chance to become an expert till tomorrow.
Алма-Ата переименовали в Алматы в 1993 году.
Сказал Алмат :D
May the force be with all....
For every contest, score distribution is announced just before the contest starts. Just for my curiosity, I want to know, what's the reason behind this?
The start time of this contest is perfect. thank you ♂ sir
Hope problems are better than previous contest.
contests*
we need more CF rounds!!!
where can i find soloution for problems? i really need to cheat
you can find them after contest. there will be a lot of solutions)
Score distribution?
WTFFFFFFFFF? WHY DIV1D is very easy??? I hope it will not faill
Did you write dp[i][money on card] or what?
dp[i][j] means minimum answer for first i numbers with at the end you have 100*j bonus. (why 100*j? because j is divisible by 100 everytime)
So, you can calculate dp in O(n2) easily, but I guessed it is not optimal to have > 3100 bonus. I'm not sure that it will pass systest
I hope >2000 is not optimal, otherwise my solution is wrong :/
Hope there won't be problems where you assume things at EJOI.
I am not that good at such problems, always trying to prove things and then I spend a lot of time on some math (99% of cases I fail to prove). Just assume that as a fact but by the time I start coding the contest is over :(
How to solve Div 2 C? I tried to find a recurrence relation for 1 hour before giving up.
priority queue on cost.
DSU
Prepare a set S comprise of number from k+1 to k+n. Iterate over the flights in decrease order of their cost. For each flight, let's call the initial departure time i, find the first number in the set S that is greater or equal to i+k, erase that number from the set.
Sort the flights by their price in a descending order, then for each flight you have to do one of those things
1-the flight is already fine, no need to delay it(i > k) 2-the flight is bad, so you need to find the first j where j > k && j <= k also j must be minimum and set the flight to that time(you have to keep in mind that there is no other flight in the time j) and add the cost
I used intervals tree for find first free place, starting with min(i,k)
How to solve div2 D/div1 B ?
Prefix/suffix minimum sweep line
mind to explain?
You need to find the minimum possible cost to cover all flights for n people towards the Metropolis within a certain prefix, and similarly we do that for each suffix. Then, you just do a sliding window, and at each step of the iteration, you can find the answer in O(1) using the precomputed prefix and suffix values.
Can you suggest some good tutorial of this topic?
This isn't a geometry sweep line, it's just the standard technique that's usually finding interval intersections and stuff like that.
Sort all flights by their departure day. Now iterate over the last day that everyone must be in city 0 (from k to 1e6). We can see that the number flights we can use to go home will only decrease while the flights we can use to go to Metropolis increase. Now just keep minimum for every person (to go home and to go to Metropolis).
Ok thnx.
Is there nlogn scanline solution for div1C? I solved it with merge sort tree in O(6 * n * logn * logn), but I'm quite concerned about TL
Well I calculated number of points in all 9 directions of every rectangle, so my solution is 9 * NlogN, if you accept that as NlogN :D
Mine was 4*QlgN, I calculated the points that are up-left,up.right,down-left and down right for every query
Yes i did with scan line in the O(6*n*logn)
Yes. You can sweep from left to right and do all the queries when appropriate using a binary index tree to query the appropriate 8 regions.
How to solve C?
Is the there a hack test for DPpos, money, where money is current money in card?
Can you explain your dp solution?
Well DPpos, money is the answer till pos if we have money money (:D) in the card. I assume that if money > 3000 we will just pay for the next by card. And we have 2 cases for the dp: either we pay everything by cash, or we remove Y (from 1 to min(currentcost, money)) from the card.
Do you have any proof?
Nope, I stresstested it with a brute force (1000 random tests) and it was ok, but still I'm not sure so that's why I asked if someone has a counter sample.
UPDATE: it passed.
Too many data structure!
Too many greedy!
Greed is good
My current rating=2017, so this is good bye 2017 for me. Also goodbye div 1 :(
Binary search + segment tree (query min prefix) solve D1 D in any contrains for cost, bonus.
Can you explain how?
Time limit of Div.1 C is too tight, I kept getting TLE on pretest 4 with N log N complexity! It's not fair!
Well, i passed pretests with O(nlognlogn) solution, so there may be a problem in your implemention
I think there's nothing wrong with my implemention, maybe I have a large contant. That leads to 9 * N * log N.
I also have a constant O(6nlognlogn)
O(6 * N * log N * log N) passed? That's crazy. Well, perhaps I was wrong. I'll check my program later.
I have corrected my answer. It seems that my submission during the contest was right, but I picked the wrong data structure. The problem can be solved with binary search tree by making all queries offline, but I used persistent segment tree. That brought me a huge constant, I think I could pass within 3 seconds. Thanks for listening to my problem.
Good day to you,
well I managed to get AC with PST (in ~1.6) so it shall be no problem.
Your PST seemed to run even faster then mine.
Moreover if I changed the limits:
the TLE turned into WA (but hope I didn't broke anything by this)
Good Luck & Have Nice Day!
I'm sorry but I'm quite sure my PST method runs much slower than my BIT method (about twice slower), and my BIT method passed in 1.2s. That program might be my last submission during the contest, I had not finished debugging it, so it went WA. Check my previous submissions during the contest, I was saying about that. Thanks a lot for listening to me and wish you a nice day (Exactly evening here in China).
Oh yes, I didn't want to doubt about this statement (imho PST has very big "constant" even though the complexity is nice — due to memory).
I just wanted to propose that the mistake might have been somewhere else — anyway seems you have tried to increase constants too (with TLE) so I'm slightly confused :O :P [maybe other submission]
Well so enjoy your evening then ^_^
my reaction while pretests is running
same reaction when main tests and hacks are running as well.
Finding a typo in my code for problem D after the contest ended. However it still passed the pretests. Pretests for D are too weak. :(
A minute of silence for a contestant who made the following "genius" piece of code...
I can't believe that it took me nearly 1.5 hours to solve C (with I should be able to do in less than 15 minutes, given that I had the Persistent IT template). I'm so terrible at not creating bug T_T
I'd recommend using the -Wshadow compiler option because of this. It saved my life quite a few times.
I wish I knew about this sooner. Thanks for the suggestion.
Div2C solvable with segment tree?
Yes, but with priority_queue is easier.
I solved it with segment tree and my code is 120 lines long. I see other people submissions that are <=50 lines and I feel stupid :/
i used a greedy approach with a set
I used greedy with vector pair!! WA just cz of missing long long :(
Same code passed on adding long long after the contest :(
How to solve div2C ?
I used MergeSort + BinarySearch but couldn't finish the code before the contest .
I solved it using a set. First, insert all numbers from k + 1 to k + n into the set. Sort the given elements by the decreasing order of C, call them a[i].c, keeping their initial positions, call their initial positions id. Then iterate through the sorted array, and find lower_bound of the index, call it idx, and remove it from the set. Add ans = ans + (idx — a[i].id)* a[i].c.
Does anybody have solution to D, which is clearly correct? I wrote something and I've stresstested it, so I'm not in this group :P
I think so.
Let's do binary search on answer. It is clear that we will spend bonuses on last 1000s and last 2000s (it can be not a suffix, for example 2000 2000 ... 2000 (9 times) 1000 2000 1000, it is optimal to spend bonuses on two 1000 only). But if we omit two 1000s or take two 1000s after omitting 2000 (going from right to left) we can change it (two 1000 for one 2000, take the variant which is more on the right). So we have only O(1) possible variants, each of them can be checked in O(n) time.
You can show that there is an optimal solution that pays for the first k using cash, and the last n-k using rewards card, except for at most one exception which costs 1000.
how to slove div2 B....
More clearly...You can consider a chosen one's left and right are all available and actually good. So you can divide the grids to blocks which contains 3 grids each(Sorry for my bad description) And when k>floor(n/3) it can be count by n-k because all the empty grid are next to a chosen one.
Is div1C merge sort tree? I found bug in my solution but still not sure if it's the right way
It can be done offline using sweep line + Fenwick trees.
Mine is with simple wavelet tree. It runs fast enough.
Nice!
I think my code is right now. How can I submit my code after the contest? There is no button appearing.
You will have to wait until after system testing has finished. At that point you will be able to submit again.
Yes, i got AC with merge sort tree
I solved it offline using SQRT decomposition + Fenwick trees. Managed to squeeze it into TL.
Can be easily done by greedy + vector pair!! I got WA cz of missing to typecast answer to long long :(
I used persistent segment tree.
I wrote a '+' instead of a '-' in a 200-lines code on C and I found it 1 minute after contest ended :( FML
when i locked my solution and solution is hacked
Sympathize with you
Molo5ya
how to solve div2/C .
Record the boundary range with a next array
This is my solution and might be wrong
1-Sort the A[] in descending order of cost (store it as pair<cost,time of flight>)
2-Make a set and insert all possible values which is from (k + 1 -> k + n)
3-Now loop over the A[] and do this for each value
binary search on the lower bound for the (time of flight) then before removing it cost += (newTime of Flight — oldTime) * A[i].cost;
4-Remove the new time of flight from the set
The flight with huge cost, the place wont change or change minimally..
I used that approach . but the problem was with calculating the total cost it was always wrong .
priority_queue + save index which have the same cost
Greedily assign the most expensive flight to the earliest time you can.
How do you find this earliest time? My approach was to keep all indices from k+1 to k+n in a set. Then, when an index is assigned, remove it from the set. To find the earliest index, use set::lower_bound.
why is this similar approach giving TLE on test case 6? code
Your TLE lies in this line
lower_bound(st.begin(),st.end(),c[i].second);
should be
st.lower_bound(c[i].second)
code
That was the exact mistake I made. Use set's lower_bound, not the generic one.
I misread the statement of Div2.D that there will be flights between the cities. Then I went to an intricate solution using ternary search + visual vertexes + shortest path on a reconstructed graph and a transposed one. Failed to finish the implementation.
Maybe I should improve my reading. The previous round is ruined for I misdeemed that given points A,B,C can be exchanged.
I can't debug 1B out... Goodbye div1...
You are probably doing some loop till n instead of till m. Had the same retarded bug and got WA on the same test as you
I still can't find the problem, probably we coded wrong on some different places and WA'ed on the same pretest
Anyone with probably correct solution to Div1 E?
First, you can compute the Minkowski sum of the velocity vectors. This gives a convex polygon with 2k sides that describes achievable speeds. Then, to compute the answer for a exhibition i, center the polygon on the exhibition, scale it depending on the number of days ti, and count the number of factories inside it.
To compute the number of factories inside it, split the polygon into 2k triangles, and sum the results for each triangle. The hard part is then to compute the number of points inside a triangle.
Actually, there are only 2k different kinds of triangles if we ignore translation and scaling, and for a single kind of triangle, we can compute all values in O(n log n).
How do you compute in O(n log n) for a triangle?
We can assume that the triangle is (0, 0), (0, 1), (1, 0) by changing the base. We have points (xi, yi), and queries (ai, bi), (ai, bi + ti), (ai + ti, bi). With a single sweep along x + y, it is possible to compute values in O(n log^2 n). With a sweep along x + y, and a sweep along x, I think it is possible to reduce it to O(n log n) by computing #(x + y < ai + bi + ti) - #(x + y < ai + bi + ti, x < ai) - #(x + y < ai + bi + ti, y < bi) + #(x < ai, y < bi). (I will try to draw something to explain it).
It is correct, but kind of an overkill.
You may express the original polygon as a sum of 2k half-infinite trapezoids, some of which are added and some are substracted. A number of points in a trapezoid of fixed shape may be found in O(n log n).
Sorry, I don't see how you would decompose the polygon into the trapezoids. Could you explain?
Shoot a downwards ray from each vertex of the polygon. Each side of the polygon along with its two rays forms a half-infinite trapezoid
Okay. But in what way is this easier than a triangle, with one base of length zero?
Well with similar trapezoids you can transform them all into rectangles. Then counting the number of points inside a rectangle can be done with a single sweep + fenwick tree. I think doing this with triangles is a lot more complicated.
What kind of transformation makes it a rectangle?
Also, couldn't some of the regions become triangular when you draw the downward lines?
Sorry for the questions, just have never seen this technique before.
Perhaps calling it a trapezoid is confusing? The trapezoids have no bottom edge, as the downwards rays extend to -infinity. The idea is that for each side of the polygon, we want to sum all the points underneath it. Then to get the sum of points inside the polygon, we add up the points below the upper hull and subtract away the points below the lower hull.
All the trapezoids are two vertical lines and then a sloped line. Half-infinite trapezoids with the same slope can all be transformed into half-infinite rectangles with a change of basis. So if the side of the polygon is the vector (a, b), the transformation (x, y) -> (x, ay-bx) works (it makes the sloped side horizontal).
Oh, okay. I thought the "trapezoids" were real 2D trapezoids, which cannot be affine transformed into rectangles, but it all makes sense with infinite trapezoid. (I guess a triangle is a sum/difference of two or three trapezoids, then.)
Thanks for taking the time to explain.
Why doesn't system testing start right after the contest ends?
I shouldn't be the one posting this but the problemsetters :D
I just wanted to know why it doesn't happen. Why are you making fun of it ?
You'll understand that once you decide to handle your own round :)
I solved Div1 D like this and hacked. Is there any counterexample?
1) Try buying first k with money only 2) Try buying first k with money only, except the last "1000" of them
You're missing the case of buying first k plus the first "1000" after them.
Try this one?
It should returns 21900 by buying first ten of 2000 and the first 1000 (12-th position).
Accepted now, thank you all!
How can i know for which input was my DIV2B hacked?
Thank you
Page of hacks: http://mirror.codeforces.com/contest/854/hacks. Just find yourself by nickname
Your hack-case: 15 6. You write 1 12, right: 1 9
Today I learned: if s is a set, lower_bound(s.begin(),s.end(),v) is not guaranteed to be logarithmic. Use s.lower_bound(v).
I learned that in an official contest :') , AFAIK in worst case it can run in O(N^2)
Yep. Got TLE on problem A today because of it. Luckily some frantic Googling let me fix it in time :)
http://en.cppreference.com/w/cpp/algorithm/lower_bound
The number of comparisons performed is logarithmic in the distance between first and last (At most log 2(last - first) + O(1) comparisons). However, for non-RandomAccessIterators, the number of iterator increments is linear.Mike Bought a nitro for the systest :D
Fastest system test I've ever seen!
Maybe this is the reason the contest was extraordinary! :O
Shut up morty, let me do the talking. burrrp
Bugatti CF Systems
can someone tell me what is wrong with my code 30156568 for 2D(1B)?
I am also getting WA on same Test case :(
I think you miss a condition int your get_ans(): from 1 to i there must be n flights with different departure cites, and also from i + k + 1 to the last day, there must be n flights with different arrival cities.
I found that your code had some small mistakes:
var "myINF" was declared as a 32-bit integer, but exactly it should have declared as a 64-bit integer.
the answer could equal 1e12, so the INF should be a little bigger.
the max suffix or prefix ans may be updated more than once in one day, so in the function goright
dpr[i]=dpr[i]-prev+sumright[num];is correct.this is the correct version 30160358
thanks.
Can anyone tell me if there is a way to make 30158579 faster? In each query I use 6 calls to 2D Fenwick Tree, so the complexity is O(Q log^2 N).
Maybe compressing the coordinates and not using a unnordered_map.
Good day to you,
Firstly, such 2DFenwick also has "hash-map-complexity" which can't be neglected.
Well there were some other greedy solution for this problem anyway to keep problem, simply replace fenwick, you can:
Use some segment-structure, whic could answer: Number of numbers on "[L → R]" lesser/equal then "X" (if you want rectangle [L,X]→[R,Y]), you can ask [L,R,Y]-[L,R,X-1].
First structure, which could do it in "clear" O(logN^2) is merge-sort tree (segment tree with sorted number in each node. You use it as classical segment tree with binary searches)
Second — probably faster — way is Persistent Segment Tree (you can simply add "1s" in order of their heights). This works in O(log(N))
Hope it is understandable.
In case you are interested in anything (or it was not undestandable), don't hesitate to ask.
Good Luck & Hope it helped,
Have nice day!
~/Morass
Instead of storing a pair in unordered_map, try using an array of unordered_maps. Although 6 calls to 2D Fenwick tree seems unlikely to pass given the constraints and time limit.
I managed to make a 2D Fenwick Tree pass using the query logic of another submission:
http://mirror.codeforces.com/contest/853/submission/30166694 my 2D Fenwick Tree
http://mirror.codeforces.com/contest/853/submission/30149861 original submission for the logic
Turns out you can calculate everything using only 4 queries.
I managed to narrow down my answer for one question to two queries to fenwick tree, but still it wasn't good enough, probably this map/unordered_map is too much.
Edit: Nevermind, forgot about two corners, it's 4 calls.
What did the "rated extraordinary" mean, for this contest?
The rating will increase / decrease by a factor of 500 today. For example, in any other contest, if u get
, today you will get 
what does that mean ??? you mean for example +500 rating ??
Hint : I was sarcastic
lol i thought you were one of the problem setters my bad
i guess the contest it unrated :/
i guess the contest is unrated :/
Why using arrays here took 826 ms while the same code using vectors here took 264 ms.
you used
scanf. It's more fast thancinscanf faster than raw cin
Speed up cin & cout in C++
so is it rated？
my fault. rating updated when i refresh the website.
How does Div2C greedy approach work? We can create a bipartite graph with the left vertices as initial times and the right vertices as final times and an edge with the weight of the cost. It is a classic assignment problem. What condition in this question reduces the problem complexity making the greedy solution optimal?
Weak testcases ( in Pretest ) in DIV2-D. No integer overflow upto 75 testcases. Got overflow in testcase 76 due to
intdeclaration :(LOL, since when do people call testcases "weak" when they manage to fail their codes?
(Edited) Weak Pretests actually. If there were overflow cases in pretests, may be I could manage to figure out mistake during contest.
Can someone tell me why this does not get a TLE ?
http://mirror.codeforces.com/contest/854/submission/30162063
because c++ is clever :D this while is O(1) :
long long test = 1000000000000000000; while(test) {
and anythings like these are O(1) too is c++ :
int ans = 0;
for(int i = 1 ; i <= 1e9 ; i++)
or
int ans = 0;
for(int i = 1 ; i <= 1e9 ; i++)
my teacher M.Mahdi said these to me :)
Thanks a lot man... I tried to hack a solution containing similar type of loop and failed. at least learnt something new :)
what is the case 83 in div2.d ? any special case or overflow reasons ?
jiangIy ( first in div 2 ) . First contest encrypted submission. 25623055
Doesn't it violate Codeforces' "Can't-do"s (here)?
Point 4 of "Can-do's and Can't-do's":
It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work.
He is webmaster.
You can compare their code style.
30148890 29986148
I was in doubt if I would attend to a class or do the contest. It seems that it was worth taking the contest =D Thanks for the congratulations!