Hello Codeforces!

We are glad to invite you to the upcoming “Ozon Tech Challenge 2020”, which will start at Mar/03/2020 17:35 (Moscow time). The round will be open and rated for everybody!

This round is initiated and supported by Ozon.

Ozon — one of the leading players in e-commerce (provides its customers with over 2.5 million product names in 24 categories), a tech company that actively developing its IT department. They already have the largest Golang team in Russia, a proprietary WMS fulfillment management system completely written by the Ozon team, 250 million lines of logs per day, collected on the site and in the Ozon mobile application. Ozon experts perform at the leading profile conferences GoperCon, Heisenbug, GoWayFest, GolangConf, and also at the company site meetups are held for the IT community.

The company shows great interest in the support of the developer community — for schoolchildren there is Ozon Academy, for the older audience there is an internship program Ozon Tech Camp and training program Ozon Masters.

Participants will be asked to solve **8** problems in **2 hours 15 minutes**. Scoring will be announced a bit later.

The problems were created by Akikaze, Ari, Kuroni, zscoder, xuanquang1999, and antontrygubO_o

We would like to thank:

- Maripium, gamegame, hugopm, dorijanlendvaj, ngfam, ngkan, and 265918 for helping with the preparation of the tasks.
- ecnerwala, 300iq, puppies_and_rainbows, benson1029, user1324641, victoralm, Mbfibat, SeehtEntity, tmwilliamlin168, McDic, pajenegod, leduythuc, MrDecomposition, all_too_well, manish.17, aryanc403, hetp111, God_Ra, ScarletS, TselmegKh, cfalas, omgursocute, Redux, and BencilSharpeniro for testing and giving feedback as well as suggestions to the rounds.
- MikeMirzayanov for the wonderful Codeforces and Polygon systems that made this contest possible.

Thanks to Ozon for the gifts to the participants:

- top 10 participants will receive stylish branded backpacks and branded T-shirts;
- 11-20th participants will receive compact portable chargers for 10000 mAh and branded T-shirts;
- 21-60th participants will get branded t-shirts;
- another 30 T-shirts will be played among the rest of the participants, who solved at least two problems, randomly.

We hope everyone will find an interesting problem for themselves. Wish everyone a successful round and high ratings! Good luck!

** UPD1: **

** Score distribution: **

** 500 — 1000 — 1250 — 1750 — 2000 — 2500 — 3250 — 4000 **

** UPD2: ** Editorial

** UPD3: ** Congratulation to the winners!

Information about prizes will appear soon.

Is anybody going to talk about the "no subtasks" tag? :))

Is it rated?

rated

AC round #2

Wise decision to be honest. ;)

Finally prizes

Small prizes though

Any prize is great!

No subtasks![ ]()

It's soooo real!lol(#ﾟДﾟ)

Hah,that's a serious problem. However,no matter whether you will get the T-shirts finally,wish you enjoy the competition!

On my way home I saw this meme and planned to change the text on the pink monster to "using question instead of problem", but thanks, that even better! :D

Nothing Here

i just realized your name means toucan, the bird in rainforests. or maybe i just had too much moonshine

In my opinion, a person who has a better rating should have a better chance of winning a prize! (For 30 T-shirts) This is fairer!

Will all sponsored rounds be combined? :(

How to make round with prizes not combined?

Prizes only for div1, or for top30 of div1 and top2 of div2.

And I didn't know what there will be prizes in all sponsored rounds.

Only for Div1 sounds unfair and the round becomes just the usual round for majority of participants.

If you make prizes for Div2, Div1 people are likely to create fake accounts.

Sponsored rounds usually have prizes or are elections to some onsite competition, in which case it's also reasonable to make round combined.

Why? Making qualification rounds before most important (third) online round of Google Code Jam is also unfair?

that's a plus :)

top2 div2 isn't much easier than top30 div1

I don't know of this happens in reality, but when round is combined it makes sense for organising company to promote the competition on their own channels. If div2 is without prices it makes much less sense for them because newly registered users can't actually win

Ok, this is a very good point.

Official drink of the contest

Solve two problems! That's so great for me, maybe I will get my first T-shirt in these rounds.

With <1% probability? You are the big optimist.

Worst case: about 30/10000=0.3%.

Best case: about 30/2000=1.5%

But 0.3%>0% !

You should keep trying with 2+ solves as in future you will be able to solve more

nah it is bigger than 0.3%. All of the competitors will not solve 2 problems.

Previous combined round have ~7000 participants and only ~4500 of them solved at least 2 problems, so your estimation of 10000 is very inaccurate. Anyway 0.3% < 1% so I don't understand the reason of this calculations.

That is the worst case :(

Of course impossible XD

Wish you good luck!Hah( ´▽` )ﾉ

.

.

Good question. If only the name of the contest gives us that answer.

Are there any previous Ozon Tech Challenge contests held on Codeforces?

No, it is the first one.

Believe it or not, I'll get the shirt

1%

1% is still too good, lets say there are 6000 participants that solve 2 problems. 30 out of 6000 XD, 0.005 chance.

multiply 0.005 with 100 ,to get percentage.... i.e. 0.5 % still close :->

multiply it with 200, to get percentage.....i.e. 100% we all win.

That feeling when you really need a new backpack knowing that you have no chance to win...

what's the score distribution?

It is going to be announced closer to the beginning of the round.

Can I participate in this contest? I don't know the full process. Anybody help me plzz.

spoiler0) write "is it rated?" in the comments

1) register for the contest in contests page

2) when contest starts, solve problems and submit them

3) after the contest your rating will be updated according to your performance

Thank you so much ♥

Yes you can.

Thanks

No, an actress like পরীমনি shouldn’t participate in codeforces contest!

A ball

A lot of problem setter and tester including 300iq.I think this contest will be interesting.

Sorry, but is any of authors or testers working in Ozon?

No

leduythuc

:thinking:

Lol. I just reposted. Originally it was the reply to the meme which said "I'm out because Akikaze is setter" and that comment got removed. ¯\_(ツ)_/¯.

.

Ozon

≃Ozone≃O_{3}:)Why some users appear with it's real name, cities and in Black?

I wish every round is combined

TFW you can't submit a solution because "You have submitted exactly the same code before", list of submissions is empty, and mirrors are not working, nice

// And it isn't a joke :(

Same here!

What is more! We can not ask the questions in the contest interface because of request status code 500 error!

Did you use late registration? I did, probably this is the source of bug

I didn't. It doesn't matter where the source, it just should not happen. And what surprises me most is the fact that this is a new bug. At least I never heard about this issue before

agree

I dislike this contest!

Same here! I cannot submit any task, but I want to participate in the lottery!

Me after solving A, B and waiting for the contest end to see if I win a T-shirt or no :

farewell, rating

There is another contest tomorrow , you should be able to make it back.

turns out, i disappointed the cf rating formula enough with my initial 4 rounds that I'm still getting rating even with poor performance:(

Was randomized solution supposed in F?

Probably. I don't see any other way especially because it can be costly to even factor everything on the input.

I have a deterministic solution for F — answer is always less then N + 1 (since we can always make everything even in at most N moves). Then it means we can only change smallest element d to (d — N, d + N). We can make a sieve upto 10^6 to find all primes in factorization of all numbers in this range, and then proceed with classic algorithm for each of those primes. I couldn't see what's the upper bound on number of primes like that, but I assume it's pretty small :P

What if every element in array is big prime number and also elements in array are pairwise different? Do you proceed n times?

I factorize all elements in range (d — n, d+n) for one element of the array (in my case minimum), so this test should not be a problem

Yea, sorry. I misunderstood you

I just tried this solution, but n could be 2*10^5 and there're 17,986 prime numbers between 1~200,000. since we need O(n) time to obtain the sum of move counts for such prime number, it seems like 17,986 * 2*10^5(n) cause TLE. Do you have any idea about this?

Yeah, my best improvement is saving global answer and terminating gcd check as soon as my partial answer is bigger. I think I can unpack my solution, so take it with a grain of salt :P

So it's something like $$$O(N^2/\log)$$$ with constant optimisations?

Probably yes, but I couldn't create a test where it would behave super badly. The "break when answer is bigger" check is pretty good in stopping almost all cases.

Yeah, that complexity is already pretty good for many $$$O(N\log^2)$$$ problems if the constant factor is good. I'd rather not bet on it in-contest though.

EDIT: This is wrong You can factor every number in O(nlogn) if you use a sieve like this:

But $$$a_i$$$ is up to $$$10^{12}$$$, so it will work too long

Yes, choose any two element x, y, get all prime factor of gcd(x-1,y-1),gcd(x-1,y),..., gcd(x+1,y+1). Then try each factor. Each turn, you might get the correct answer with probability 1/4.

Upd: choose any element x, get all prime factor of x-1,x,x+1. Then try each factor. Each turn, you might get the correct answer with probability 1/2.

I don't know, but at least I solved with randomized solution.

My Randomized SolutionRepeat 30 times as follows:

Total Complexity is $$$30 \times O(\sqrt{a_i} + N)$$$. It fails with at most $$$2^{-30} \approx 0.0000000931322$$$% probability.

How do you check the minimum cost in the whole set of primes T in O(N)?

The gap from A to F is pretty good, but G and H are too hard..

I am just curious how fo you generate these drawings they are really nice :)

They are made using PowerPoint. :)

Ah you're the type that does Data Siens on Excel

FaIr aNd BaLaNcEd cOnTeSt!

It was a tough game, but it was great!

How to solve D ?

Hint: Consider any $$$2$$$ leaves of the tree $$$u$$$ and $$$v$$$. Say $$$lca(u, v) = w$$$. Observe that $$$w \in $$${$$$u, v$$$} if and only if $$$w$$$ is the root.

SolutionMaintain a tree $$$T$$$ which is initially the given tree. Now, keep doing the following:

If $$$T$$$ has exactly vertex, then output that as the root. Otherwise, $$$T$$$ must have atleast $$$2$$$ leaves, so query any pair of leaves. If their lca is one of them then output that as the root otherwise delete both these vertices from $$$T$$$ and repeat this process.

As each step either returns the answer or deletes exactly $$$2$$$ vertices, we use atmost $$$\lfloor \frac{n}{2} \rfloor$$$ queries.

How the heck is F solved? I passed pretests with what I presume is a nasty wrong solution, though I don't think I'm capable of generating tests that break it. Is there anything clean for that problem?

We can always make gcd=2 by using <= n operations, so let's use only < n operations. Let's say we applied operation on i c[i] times in optimal answer, then at least for n / 2 indices c[i] <= 1(otherwise (n/2) * 2 >= n). So just pick some index i and try to prime divisors of a[i] — 1, a[i] and a[i] + 1. Not sure if it's good enough to fit into TLE though.

Fair enough, I guess that works. I feel dumb now.

How to Solve E?

I think you can construct the answer. Maximum possible number of triples is achieved in sequences like x, 2x, 3x, 4x, ..., kx, and you can calculate how many triples you can get for each k. If m > this number for n, the answer is -1. Otherwise you take the biggest number k less or equal to n, such that m is bigger than the maximum number of triples possible for this k. The first part of the answer would be 1, 2, 3, ..., k. Then you can add just one number: something like 2*k — 2*(how many more triples you need to get m in total), and you satisfy condition for m. If there are spare numbers left (n — k — 1), you can add a sequence of type (big number) * x — 1, which does not produce any more triples.

Thanks!

Great problems! What's the logic behind E?

how to solved D ??

For every query, pick 2 from the current graph having degree 1. If the LCA is equal to any one of the 2 nodes you queried for, it is the root! Else remove these 2 nodes from the graph and repeat the same process.

Nice contest! I hope, i will get a T-Shirt ;)

In case I win a random T-shirt.

More like

KharYusuf

now imagine not winning a shirt.

I don't think it's allowed to send portable chargers? (lithium batteries)

You can ship it on flights, given they satisfy the maximum mAh criteria. And I guess 10000 mAh is pretty much fine.

That's not true. Lithium batteries are only allowed to be hand carried in passenger planes or shipped in cargo planes. Since most mail services make use of passenger planes, they outright ban lithium batteries. Even if you use carriers like DHL you will need special approval.

Tell that to bootleg Chinese sellers on EBay.

How to solve C?

If a[i] % m = a[j] % m for some i < j, then answer is 0. Otherwise there are <= m numbers, so you can calculate answer in O(N^2).

Yeah the brute force will work, but I got a wrong answer in test case 15. Probably an OverFlow. I don't know what it is. I have used Long.

Got WA on Pretest 9 ;/

Codevoid solve() { int n,m; cin>>n>>m; ll ans=1L; ll num[n]; for(int i=0; i<n; i++){ cin >> num[i]; }

}

int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);

/* auto end = chrono::high_resolution_clock::now();

/ /double time_taken = chrono::duration_cast<chrono::nanoseconds>(end — start).count();/ /cout << time_taken*1e-9 << setprecision(9) << endl; */}

Not sure is it the case or not but...

A possible cause is absence of "ans %= m" inside the loop after the "ans *= ..." part. I think that int64_t could be not enough to hold the value.

I even tried that,

`(a*b) mod m = (a mod m * b mod m) mod m`

but got WA on the 9th pretest itself. So then I changed it to this and no luck.You probably meant O(m^2) because O(N^2) should be TLE for N=10^5.

~~I still do not get~~how to do that in O(m^2). Can you guys please explain?(The best I managed to try during the contest was O(N*m*log(N)), and I failed.)

If

`ans!=0`

for some`i`

and`j`

then it will be`O(m^2)`

and unless`m==N`

which is not the case(constraints).Got it (from this thread on this page).

The pigeonhole principle. When N > m, existence of two numbers which are equal (mod m) zeroes the whole product.

Is there a deterministic solution for

F?Very fine and

good statements. Thank you for these nice problems, but I had some problems with pretests on problems B and C -specially.If anyone's interested, the solution to F is described here.

Wow the solution to today's problem had been written 2 years ago

Thanks, I was wondering why that felt so familiar.

Another bloody lesson on CF Round: rand() only generate [0,65536) on codeforces......

I got 6 wa and debugged for 20mins...Now I only hope that I can pass the system test...

The real lesson would've been to not have this covered by pretests.

Kinda tough to do that without keeping $$$N$$$ small in pretests.

We decided to be nice, it's a bit less unfun to fail in pretests compared to failing on a hack :)

Bro, Thank you for being nice and preparing this excellent round~

Very good point! I am very grateful now.

Just realized I haven't touched pretests of F. Completely forgot what I've done last year with hacking rand() lul, good thing someone else covered that.

This round was one of the most interesting rounds I've participated!! Sooooo Amazing!!!!!

I think it's better to give a warning in the blog if the contest contains any interactive problem(s).

I guess there is no rule as such.

Usually the problem setters are kind enough to let us know before-hand so that anyone who is new to such problems, will take a look at it. :)

Yeah. Actually that's why I am talking about this. Anyone who is not familiar with such problems may learn before participating and solve more problems.

Why only interactives? Just make the problemsetters announce all the problem topics so those who aren't familiar with them can learn them beforehand.

Okay. It makes sense. I got the point :)

"**The resulting string does not have to be empty**." due to this statement i got 2WA + late submission in B problem anyone faced same issue

oh wow so i will get WA since i just deleted all the possible brackets...... (()) would fail for me :/

actually i just realized i did solve it correctly since the number of deleted brackets dont matter , it is only the number of operations that matter.

I did the same mistake. My answer should fail on cases like

`()`

but got an AC insteadYou should be grateful that the pretests covered it.

I FSTed. :(

Does D involves finding longest diameter of the tree, then query end points of that dia, if output of the interactor is one of the 2 ends, return that as that root. If not, then if interactor's output is a vertex not lying on the longest dia, return that vertex. Else (if lca returned is on the dia (but not the ends)), then check recursively the same process in the subtrees of that lca (by removing connection of lca and its neighbors that are not on the dia)?

It is more simple. Query two leaves, if response if one of those leaves, thats ans. Else remove those two leaves. Repeat.

this approach will fail if all the nodes are connected to the same node

in that case you can output the last input we receive from interactor since that is the only vertex which will be left as we have removed all other vertex by removing 2 vertex n/2 times .

If the output of interactor, say w, is not one of the 2 ends(say n1 and n2) then you remove the edges connecting w to n1 and n2. You find the longest diameter again and repeat the process.

implementing using this https://codeforces.com/contest/1305/submission/72494365 , but failing on 102th test case. Can you please help me with what am I missing?

Upd: Nevermind. Got accepted, found the bug.I did something related to diameter of the tree.

You may notice you want to remove a lot of nodes, which are not candidates to be the root in each query, until you are left with one, which is done (fitting exactly in queries) by the approach in the editorial, too.

I, instead, went on querying the ends of the diameter, and removing all nodes (and of course all other nodes in "subtrees" of the diameter nodes, except the LCA returned in the query, because all of them except the "w" returned in the query, are no longer candidates to be the root as all of them have atleast one vertex "above" them), and continued to do so until I have one node remaining.

Systest when, fellow Stalker?

How to solve G?

Tests are strong (at least not shitty) this time, yes?

Pretty sure making strong tests for F is a difficult problem in and of itself. My shitty solution passed pretests, we'll see about tests.

I also have something what I'm not sure about in E.

Also was close in G, we'll see in upsolving.

Well, your solution definitely can't get WA because the last part of your code checks all large divisors of (some number)$$$\pm n$$$ and every number will be modified at most $$$n$$$ times. The only thing I'm not 100% sure of is whether it's fast enough.

Yes, in worst case scenarios it can check ridiculous amounts of primes (millions) and it checks each linearly. However, lots of optimizations and early stops make it very fast on most data.

P.S.

Accepted in 561ms. I am not capable of generating tests against it even if I strongly believe it's slow. Can't prove any good complexity either, but oh well, it passed.

There are at most (78498 (number of primes <= 1e6) + 2 * n) primes in the factorization of numbers in [x-n, x+n] and that's a kinda loose upper bound anyway so it's not millions.

Hacks for C:Hack Test Case2 2

1 2

You can prove that when $$$M < N$$$ the answer is $$$0$$$. But, even if your source code assumes that when $$$M \leq N$$$ the answer is $$$0$$$, you will get pretest passed. (There is some hack cases like above)

For me, first, my source code assumed that when $$$M \leq N$$$ the answer is $$$0$$$, and then I resubmitted. So I was able to notice hack case earlier, but there is no such source code in my room :(

I checked that for all N < M the answer is 0 but how to formally prove it ?

There exist i,j i!=j such that a[i]%m==a[j]%m, hence (a[i]-a[j])==0 (mod m).

If a and b have the same result after modulo m, |a — b| mod m = 0. Then it's pigeonhole principle.

I guess you meant M < N. According to the pigeonhole principle, among >M numbers there will be at least two (call them a_i and a_j) with the same remainder upon division on M. Since there will be |a_i — a_j| or |a_j — a_i| in the product, the entire product will be divisible by M.

Does that mean we assume all numbers given will be distinct?

Well, if some two are not distinct, that still have the same remainder. Moreover, then the product will be 0 automatically.

Ok now I get it that for n > m even if we all are distinct there will be 2 that have same modulo by m. Thanks for your help

After staring at C for a good 20 mins, I had an epiphany. Pigeonhole principle! I smirked like the ninja in https://www.youtube.com/watch?v=pKO9UjSeLew

And then wrote m>=n in my pigeonhole condition instead of m>n

FML

Nice problems with clear statements.

TFW B is harder than F >:/

Weak.Pretests on C

Prepare for Polish Mafia in uphacking ;_;

mnbvmar, show them what you think about them.

Hiiii Can you check this submission. Is this agreed in contest? https://codeforces.com/contest/1305/submission/72343610

As idea looks just like a solution from editorial. Of course, it looks like full of bugs, but it's typical obfuscation, which can be found in many places in CF (and is against rules!). Ofc I'm talking about #define int long long.

Please hack 72364530 72364506 72364194 72364859 . They all are same with a change in constant.

72364859 and 72364466 are exact same but one got WA on tc93. P̶r̶o̶b̶a̶b̶l̶y̶ ̶a̶ ̶h̶a̶c̶k̶.̶ Dori added them ~20 mins before start of round.

These are my ugly brute forces which survived system tests during testing. Idea was to run sieve and check all primes up to a constant (5e7 in the present case.) and then randomly pick a no and try to factorise it up to primes 1e4 then assume leftover prime and gcd and check it.

The intent was to break solutions which doesn't check factors $$$a_i+1$$$ or $$$a_i-1$$$ .

pajenegod has some similar solns which sieve up to 4e8 (using some superfast sieve.) and runs under 2s.

One plan to break them was to increase $$$a_i$$$ up to $$$10^{14}$$$ but we didn't want to force factorisation in O(primes up to $$$10^7$$$) instead of O($$$\sqrt a_i$$$)

You know that there is no rating limit for uphacking, yes? You can also try.

We tried hacking them during testing of the round.

Btw only div1 users can up hack.

shouldnt n^2 solution for C fail?

yes it would, however a (n <= 1000)^2 solution wouldn't, all answers for n > 1000 are always 0's. this is why you only calculate the answer for (n <= m).

For anyone interested in detailed analysis of problem C -- Here you go!

Can any one plsss check this submission . How on earth this random submission got accepted. Its cheating https://codeforces.com/contest/1305/submission/72343610

I had the proper idea for

F, but my deterministic solution of course got TLE, but didn't realize I can do a randomized solution. I have never solved a contest problem with randomization till date. Can someone help me how to get started with such randomized solutions, so that it gets intuitive when I see a question in future to use a randomized solution with high probability. :)Does anything faster than $$$O(N^2)$$$ exist for C if the modulus was large?

from what i've seen the absolute difference instead of a normal difference ruins most possibilities of coming up with mathematic solution. ++ for an answer.

If you sort the numbers in decreasing order then you can remove the absolute.

I can only present a polylog solution, which should run way slower than the $$$O(n^2)$$$ solution in practice. After sorting the array we can get rid of the absolute value part. Then use divide and conquer, split into two subproblems of size $$$n$$$, then we need to multiply something which can be done using multipoint evaluation of a polynomial, which is a typical problem that can be solved using D&C and FFT in $$$O(n\log^2{n})$$$, therefore the overall complexity is $$$O(n\log^3{n})$$$.

By understanding how multipoint evaluation works, you can make it in $$$O(n \log^2 n)$$$. Assume for simplicity that $$$n$$$ is a power of two. In fact, for each $$$i$$$, we want to find the remainder of the division of $$$(x - a_{i+1})(x - a_{i+2})\dots(x - a_n)$$$ by $$$(x - a_i)$$$.

For each interval $$$[L, R]$$$ of the form $$$[2^i \cdot j, 2^{i} \cdot (j+1) - 1]$$$, compute $$$(x - a_L) \dots (x - a_R)$$$. Call it $$$P_{[L, R]}$$$. (This is in fact needed in multipoint evaluation as well.)

Now, a recursive function $$$f(L, R)$$$ will compute all the results for $$$i \in [L, R]$$$. This function will receive $$$(x - a_{R+1})(x - a_{R+2})\dots(x - a_n) \mod{P_{[L, R]}} =: Q$$$. If $$$L=R$$$, we're done. Otherwise, let $$$m := \left\lceil \frac{L+R}{2} \right\rceil$$$ and notice we can call $$$f(L, m-1)$$$ with $$$(Q \cdot P_{[m, R]} \mod{P_{[L, m-1]}})$$$, and $$$f(m, R)$$$ with $$$(Q \mod{P_{[m, R]}})$$$. Each multiplication and modulo operation can be done in $$$(R - L) \log (R - L)$$$ time, hence $$$O(n \log^2 n)$$$ total runtime.

Edit:notice that the "normal" multipoint evaluation does almost exactly the same stuff, only that $$$f(m, R)$$$ is called with $$$(Q \cdot P_{[L, m-1]} \mod{P_{[m, R]}})$$$; so that in each step, $$$f(L, R)$$$ will receive $$$\prod_{i \not\in [L, R]} (x - a_i) \mod{P_{[L, R]}}$$$.Can you provide links to some similar questions?

Problem C was :

Pigeonhole principleI don't understand why my sub idleness

Plz help me

I think that you need to send a new line when you print the answer.

vs

I have found out why it was idleness, when i used

cout << flush;

its no longer idleness. Btw tks bro.

Comment on problem C: Next time, when $$$O(nm)$$$ solutions didn't suppose to pass the TL and $$$n=200000$$$, choose your $$$m$$$ like $$$3000$$$ or something!

Your solution is correct!

The TLE was caused by an overflow

You can see my submission of your code Here..

Ohhh, Thank youuuu! Now I feel much better!

Hello, my solution for "B" got an Runtime Error on Test 24, where the String was all "(" (length;1000). The code gives correct answer on this case ("0", that is) on my editor, as well as some online editors too, when checked upon.

Can someone please, check out and tell where it could have got a Runtime Error, because I don't think it (the code) can give Runtime Error.

Thanking you with anticipation!

Solution Link: https://codeforces.com/contest/1305/submission/72323474

`ll i=0, j=close.size()-1;`

This will init j to huge value if close is empty.Got your point,

But actually j's value is saved "-1" through this statement, in most of the editors, as I told, above.

Then, why does it assign a large value of "j" on the Editor and Compiler of CodeForces? Please explain the reason, if you know!

Thanks!

The vector.size() returns size_t, which is unsigned.

However, if it is -1 the code still is undefined, since j is used as an index, and -1 is not allowed there, too.

The "while" loop condition is there for not allowing the neg. value of "j".

j>=0

This condition will stop that, anyways.

Now, the code works, when I write the equations as follows:

ll j=close.size();

j--;

Then, it works!

Why is it happening like that?

MikeMirzayanov

Also, when I write "int", instead of "ll", it works!

int i=0, j=close.size()-1;

Can someone explain, why?

The type of

`.size()`

is`size_t`

which is an unsigned integer type, so if the size is`0`

and you subtract it by one, it will overflow (it may become a large integer). Therefore, you should not subtract the size without type casting.If you use

`ll j = close.size();j--;`

or`int j = close.size();j--;`

,`close.size()`

will be cast to`ll`

or`int`

, which is a signed integer, before you subtract it, so it works.If you use

`ll j = close.size() - 1`

,`close.size()`

will be subtracted before it is cast, so it is wrong. But if you use`int`

instead of`ll`

, it "may" (since overflowing is an undefined behavior) be correct.`size_t`

is a 4-bytes integer type and so is`int`

. The binary result of subtracting an unsigned integer is as same as a signed integer type with the same size commonly, so the binary value of`(size_t)0 - 1`

is as same as`(int)-1`

. (The value is the maximum value of a 4-bytes unsigned integer which is $$$2^{32}-1$$$, but the maximum value of a signed 4-bytes integer is $$$2^{31}-1$$$, so it will overflow to -1 when you cast it to`int`

.)`ll`

is not like that. Although the value of`(size_t)0 - 1`

is -1 when we regard it as an`int`

, it cannot be cast correctly to`ll`

.Got the point.

Thank you so much, for such a nice explanation!

when we get the result of random t-shirt winner

I guess they first have to eliminate those hundreds of smart people who, after solving A and B, started modifying their codes to send from other accounts, instead of solving C.

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters and update them again!

Excuse me, I don't know how to report the cheating behavior, but it seems like the User Qingyu98821, who got the second place in Contest Codeforces Round #624 (Div. 3), is suspected of making his code obfuscated.

In problem B of todays contest it is clearly mention ed in the question that after applying the operations the string does not have the empty size. So naturally for test cases in which string is Simple string any answer is not possible.Kindly check the question..

"Does not have to be empty" meant it could be empty, or non-empty, will not affect the verdict.

Mind your English, please. And if you were unsure about the statement, what prevented you from asking?

ok.from next time i will ask during the contest itself..

the resulting string does not have to be empty means that after the operations the remaining string must be of non-zero size.

Actually not. That'd be "the string cannot be empty" or "the string must not be empty".

How to get test cases for D?

How is it possible?

Time: 15 ms, memory: 148 KB

Verdict: OK

Input

6 4

1 4

4 2

5 3

6 3

2 3

Participant's output

3

Jury's answer

1

Checker comment

ok Passed.

when the prize is T-shirt Its possible

Interactive test data is quite different from normal problems.

In this problem specifically, the "input" showed in the submission details is equivalent to the hack format described in the statement, and the "output" here is number of queries used (actually this part is quite a placeholder, since I implemented the process of judging the answer to be in the interactor, not the checker).

Thanks

I solved 2 problems in the whole contest. I was relieved by this . My submission was accepted so I started thinking about next problem. Now I only got 1 correct submission . What is this ???? Who should I report to for this incident? :(

Looks like your solution on B failed on system test.

To make it clear, ịn a contest your solution will be judged by a smaller set of tests (called "pretests"). After contest time, it'd be judged again.

We tried our best to make the pretests strong, but it's certain that not every case can be covered. :(

Btw your error was on this line

You should have checked o<close.size() && o<open.size() before doing open[o]<close[o]. That would have given you AC, 72370968.

One good thing about making this mistake is that you know now how to avoid it in the future!

Thanks I got it :)

Give me T-shirt

You'll get a T-shirt if you're lucky, Because there are only 30 T-shirts, good luck everyone.

I am just wondering what tourist does with all those T-shirts and iPads that keep piling up...

Obviously he puts on all t-shirts at once and pretends to be an onion while simultaneously watching 20 cooking shows on his ipads

Actually when I read it I picture Um_nik doing that. I don't know why.

I guess because in 1 T-shirt I look like a human in 20 T-shirts?

You made my day with your joke ... I am laughing now :)

tourist be like:

Im so sad because i miss the last one second to submit my D answer.And after the contest ,i checked it's right...

.

Great round, really nice non-standard problems.

When t-shirt winner will be announced?

this contest broke my record: the previous greatest rating change(with the maximum absolute value) is +131 and now it's -145. QWQ

-157, hold my beer

Seems you were overrated before the contest :)

In fact my real rating is around 1400

if my submission gets partially acceptd or it passes 3-4 testcases, will that be counted or not?? I am not getting rating mechanism, kindly help??

No

My rank go up about 200 after the system tests...

When the t-shirt winners will be announced?

I think they have finished removing fake accounts.

Why Rollback, any valid reason please?

Click

I guess removal of fake account done by team codeforces. Waiting for tshirt winner announcement

And the winners of t-shirts are (congratulations!):

Hey MikeMirzayanov! I can see my name in this list, might I ask how do I redeem this Tshirt? Like where can I fill in my delivery addresses and everything? (newbie at this section of forces)

You can fill it at your home page where you can see an address page and select your T-shirt size.(also a newbie at this section,figured it out just now)

Thank you!

Excuse me,if I see my name on the list,but didn't filled the address beforehand,if I filled it now can I still receive it?(didn't even thought I'd be able to use the address page)

Similar query here , MikeMirzayanov.

Congrats to Pajaraja for his 11th consecutive rating increase, all the way from Specialist!

Thanks! Hopefully I won't end up taking a trip back to Specialist now.

orz!!

When will the T-Shirt winners be announced ?

Here\n

trqwertg..