Hello Codeforces!
On Oct/15/2022 17:35 (Moscow time) we will host Codeforces Global Round 23.
It is the fifth round of a 2022 series of Codeforces Global Rounds. The rounds are open and rated for everybody.
The prizes for this round:
- 30 best participants get a t-shirt.
- 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.
The prizes for the 6-round series in 2022:
- In each round top-100 participants get points according to the table.
- The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
- The best 20 participants over all series get sweatshirts and place certificates.
Thanks to XTX, which in 2022 supported the global rounds initiative!
The problems were written and prepared by AmirrzwM, MohammadParsaElahimanesh and napstablook, AquaMoon, Cirno_9baka, mejiamejia, ChthollyNotaSeniorious, SSerxhs, TomiokapEace, SomethingNew, pakhomovee, rembocoder, SirShokoladina.
We would also like to thank:
- 74TrAkToR, for coordinating and helping a lot to make this round happen (
and rejecting all of my problems). - er888kh and Mp007mp for giving ideas for some problems.
- Our testers for testing and providing helpful feedbacks: er888kh, sinamhdv, SoheilE, DeadlyCritic, egfhdbfweryg123, gamegame, Kostroma, Endagorion, AndreySergunin, MELNIKOFF_OLEG, zemen, iwalainz, halin.george, -skyline-, mejiamejia, triple__a, TomiokapEace, SomethingNew, efimovpaul, Rhodoks, meowcneil, plagues, Milesian, blobugh, SSerxhs, apeiya, E404_Not_Found, RUSH_D_CAT, willy108, _Veritas, oolimry, aaaaawa and Ynoi.
- MikeMirzayanov for creating great platforms Codeforces and Polygon.
Round Information:
- Duration: 2 hours and 15 minutes
- Number of problems: 7 problems and 1 sub task
- Score distribution: 500-1000-1000-1500-(2000+1750)-2500-3500
- There is an interactive problem, so please see the guide of interactive problems if you are not familiar with it.
We have tried our best to write clear problem statements and make strong pretests and we are looking forward to your participation!
UPD: Editorial
It clashes with Google Kickstart, can this round be postponed pls? Thanks!
If you solve GK in 2h30min you still have 5min to rest before this contest.
I think, for every contest we should try to solve problems till end of the contest. Sometimes, last problem gets accepted in last minute of the contest.
If the contest gets postponed, it will be good for everyone.
Score Distribution?
Who is here after Kickstart ?
Not after; Along with kickstarter! I came at 8:05, solved howmany ever were possible, and went back to kickstarter. Glad to share I cracked a problem in kickstarter in this small time period.
It's not bolded (or math mode, I guess?) like it usually is, but it's in the third bullet point of the round information (end of post):
500-1000-1000-1500-(2000+1750)-2500-3500
E has the subtask, apparently
Hello. Is there any chance that the timing will be adjusted according to this request and this request? In fact, there was much more than just these blogs as I have seen.
Gotta emphasize the message again.
Well, is that indeed hard to postpone the contest by half an hour? I genuinely can't see any problems doing that, rather you will get a few hundred more participants that will be able to finish Google in time and then enjoy this event too. I believe there're a lot of people like me who wish to participate in both contest, yet try their best until the last minute on KickStart.
No, you will lose participants from China who wants to go to bed half an hour earlier.
Yeah, that somewhat does make sense, but going at 9.30 or 10,00 PM is I feel something more negligible than missing either a CF round or not going till the end on Google.
ed. Actually the region thing is both ended: US guys will for example get 30 mins more of sleep if needed and probs more will join, so can't really judge like that.
Hope to become IM!!!
completely failed after hacking myself(C)
as author of 4 problems I wish you experience great contest ...
as a. . . Welcome to our round!
Dear authors, Can you please postpone or prepone this round a little bit as the time is significantly coinciding with Leetcode Biweekly contest 89. i.e. Codeforces contest will start just 5 minute after the beginning of the Leetcode biweekly contest 89. Please authors, Can you reschedule this round a little bit . It will be hard for many of us to choose one contest between them. Thank You.
It isn't hard to choose, just do the global round and forget about Leetcode.
It's simple, Codeforces > Leetcode
what about google kickstart? it's from 12:00 to 15:00 UTC and Global round starts fron 14:30 UTC
Global round again Wow! Hoping for a nice round again!
I guess you forgot to mention t-shirts for top 30 and 20 random participants who will make into top 500.
Interactive Problem ftw!
Can it be postponed or preponed as it's coinciding with google kickstart and we need min. 30 min. Interval break as both of the contests are brain storming & wanna enjoy both the contest!!!
Hello! Should I participate in this round? Are the problems good?
Sure
How would you know?! You didn't even test >:((
Te tin minte.
Well, this was partly a joke (nevertheless, to improve, you should participate in rounds as much as possible, so the answer to the first question might be correct unconditionally).
I can answer more seriously: recently Um_nik has stated the real opinion in the comment section, and despite me upvoting the comment (I liked the interruption of continuous "the great contest ever" comments chain), I've later agreed with dario's point which stated Um_nik's comment improper. Indeed, it's one more step to reveal in the comment section The Problem Statements Mystery.
That is, I would not like any involved person answering you evenly. One of the solutions is to claim "good contest", but to do this, you don't even need to be a tester. So I've done it.
My dear friend, how do you want me to answer you. . .
Probabilistically it would be better if you didn't answer at all
Hope, I will become pupil after this contest :).
just enjoy and solve problems, do not thinking about too much on rating changes, i believe u will have a better enjoyment ^-^
yeah!! agreed
Nice to see AquaMoon in problem-setter's list
Me too, do you miss her?
I had CM performance in her 735 div-2 round last year so yes I always miss her
Then you'll see her announcement again soon.
Thanks for your support! o(*^w^*)o
Hello authors, Can you please postpone the contest by half an hour as Google kickstart will end at 20:30 IST. We will be very very grateful to you.
It will be good if this round can be postponed by half an hour, since google kick start happens 150 minutes earlier and last for 3 hours. (sorry the time cannot be changed, then I will do my best to AK the kick start within 2 hours and half)
Just a small clarification needed, will there be an update in the contest timings as it clashes with the GOOGLE Kickstart Round G which is supposed to last till 15:00 UTC?
Hmm, as I see, no one wrote a comment about clash with Google Kickstart??!!! So I have to write!
Please please please please, postpone this round!!!!!
yeah because they wrote a full-blown blog
Interactive problem 1
my solution: 176222751
Please help me. what's wrong in my code ?
your algorithm will take 10^6 queries, and there are only 25 queries allowed. So you need to learn binary search https://codeforces.me/edu/course/2/lesson/6/1 , or from any other website which you prefer.
But why wrong answer on test 1. it will take 12 queries. Is there any other reason ?
Sorry for the late reply, The problem in your code is that it will not answer correctly if the number to guess is greater than the number you have already set, you have set that to 1 (ans = 1) so every number is greater than 1 so your while loop condition will never be true. So you are just giving 1 as output everytime. So, if you want to go with the algorithm you have, you should set the ans to 1e6+1 (1000001) in this case otherwise (input_number+1) so that it is always less than that and while loop will keep running until you get the right number... Ofcourse in this case you need to do ans-- in the while loop.
As a tester, I can confirm that the round is well balanced and you'll enjoy the problems.
noc^2
7 problems and 1 sub task. I like it!
I'm not familer with global rounds,could someone tell me is it div.1 or div.2 or div.1+div.2 please?
div-1 + div-2
thx
Give me some upvote to get out of the negative contribution please ..
Hope to become expert after the cotest!
Hope to back to Master lol
Score Distribution?
score distribution?
why can't i register in the round ?
https://postimg.cc/xJQHJC6s/4c459b91 really thanks alot my day was ruined i was excited to take part in this contest ( i even think i have registered earlier but maybe i am not remember) ps : its strange now i can register thnx
hell, honesly i don't mind you downvoting me but at least explain me what happened
You can't register within 5 minutes of the start of the contest. If you miss the normal registration period you have to wait until they start allowing "extra registration" with is usually 10 minutes after the contest has already started
thanks for replaying i am partially sure that i have registered yesterday maybe i had forgot however, i don't understand why can't i register for the upcoming round? https://postimg.cc/34QsSnQx/86986dc6
'cause you already did?
Worst global round ever, downvoted.
Should beginers try it? What is the level of dificulty?
I would say the first 3 problems could all potentially be solved by someone who doesn't have a lot of experience with cp, but "beginner" includes a wide range of very different people.
Anyways, problems don't hurt, just go ahead and face them.. If you try and find them to be too tough for your level of experience just move on and go back to them another day or perhaps read the editorial once it's available.
.
Damn in D I just can't find an efficient way to sort each vertex paths and then sort these paths in the parent vertex paths because we can't go in the same visited vertex and once all the vertices of the of the same parent vertex are visited we consider these vertices unvisited (not their children).. I think I know the main idea but can't find a way to code it.
Correct me if I'm wrong
.
Well, sorting the paths is easy. The real issue in that approach is 1) the best possible path relies on which paths can be used, requiring 2^|# leaves| states, and 2) it is not clear to me that greedily choosing the best possible path is optimal.
It should be greedily because once we find all the possible paths we will repeat the same order so we could just sort these values in the array and depending on k%(number of leaves) we will know at which value we should stop
D was good problem, yet couldn't solve. How to choose the leftover k%(num_of_leafs) leaves, without breaking the rules(conditions) ?
Let assume dp(u, k) return best result at u with k and k + 1 paths. Then for each node, we consider x = (k % num_child) best child. And the next best child is the answer for k + 1.176362632
You only will use a child maximum once, so you only push to the parent the best child you didn't used.
D is easier, than B
aabra ka dabra
https://ideone.com/6Lludx
E2 when exactly three candidates remain killed me :(
Please say that D was DP on trees
Is Problem E an IMO problem?
It's essentially a special case of IMO2012 problem 3, except that this problem has an upper bound on the number of questions. But knowing this didn't help me anything, as in the IMO problem you just have to find a solution for the generalization to only one truthful answer in (k+1) questions (and in the end you can query 2^k + 1 numbers), but then your (mathematical) solution doesn't focus on minimizing the number of questions.
Great round! I love it <3
F is similar to a problem which I have made in our Online Judge (But this time I didn't solve F TAT).
And can someone help me find out the mistakes in this code ? Thanks a lot.
The mistake in your code is that the random numbers that it uses are of poor quality. Specifically, the lowest bit of the numbers returned by
rand()
has a low period, and adding the previous number and taking the result modulo N (when N is even) doesn't change that. In fact, it is not difficult to make a single test that will break any periodic RNG with a period less than 300000.In 176407464, I modified your code to replace
rand
withmt19937
, and it passed.I feel problem E is similar (same?) with BOI 2022 communication, correct me if I'm wrong.
The limit is a little smaller in E2.
How to solve E? I was thinking about sending two patterns 1100 and 1010 twice (So e.g. if n=8 the two patterns arrays are [1,2,3,4] and [1,2,5,6]). Then in any case we can reduce the search space by half.
For E1, eliminating 1/4 for every 2 queries is fine. I used two intersecting subsets.
Though solving n=3 is the hardest part of the task...
Wow, I feel stupid. I had two intersecting subsets as queries drawn on my paper, with various case distinctions about truth and lie etc. but I disregarded elements not in the subsets...
losing cyan cuz misread C's statement
i read in each operation it increases 1 to the suffix not i
Does anybody else misread C and tried to solve problem when you can increase suffixes just by 1?
yes, wasted 2 hours 5 minutes + 100 elo on an unsolvable task. i and 1 look too similar.
lol I also wasted my 30 mins with this same mistake.
Wait this was me too, spent almost 2 hours on it ...
Bruuh
I feel like I got the correct idea for D but bad implementation led me to a TLE. Is there a more effecient way to pick the optimal
paths % child_count
results among all children for every parent than simply sorting? Or maybe the intended complexity is actually O(n) and I am missing a detail?I used multiset, but with a memorization (I used vector<map<int, int64_t>> to record).
you can calculate Try(child, k) and Try(child, k+1) at one. This is my submission: 176362632
Ahh I thought about returning a pair but did not have enough time to think it through. Yours looks great. Thanks!
E1 solution(Chinese) how E2?
My idea was that we prepare two sets, $$$J$$$ and $$$T$$$ (for joking and truth). The idea is that if the latest query was honest, then the target is in $$$T$$$; otherwise, the target is in $$$J$$$. We can initialize them by querying half of the search space, where the half that's consistent with the answer goes to $$$T$$$ and the other half goes to $$$J$$$.
For each query afterwards, we can split $$$J$$$ into two halves: $$$J_1$$$ and $$$J_2$$$, and also split $$$T$$$ into two halves: $$$T_1$$$ and $$$T_2$$$. Then we query $$$J_1 \cup T_1$$$.
Let $$$J'$$$ and $$$T'$$$ be the new $$$J$$$ and $$$T$$$, and repeat. This way, we reduce the search space ($$$J$$$ and $$$T$$$ combined) by 75% in each query.
EDIT: Upon testing, I realized this doesn't work, since only half of $$$J$$$ is removed this way. The sizes of $$$J'$$$ and $$$T'$$$ are not necessarily the same, so half of $$$J_1$$$ is not necessarily 25% of $$$J \cup T$$$.
Divide number set $$$S$$$ into $$$a, b, c,$$$ and $$$d$$$,then query1:$$$a∪b$$$,query2:$$$b∪c$$$. Trust the results of two queries,we get a new number set $$$S'=a∪b∪c/a∪b∪d/...$$$(size of $$$3/4|S|$$$).
I am curious about the max rating fall on codeforces. It is a black weekend for me.
please someone tell me, what the wrong with my code for problem D 176366211
Take a look at Ticket 16294 from CF Stress for a counter example.
thanks, i got it,,
Any corner case for problem D?
How to solve C?
+1
+1
You can start from a[1], you want all the numbers after it to be bigger than a[1] so you can just add a[1] to the suffix [2:n]. then go to a[2] and add a[2] to the suffix [3:n] ans so on. Notice that for example adding a[1] to the suffix [2:n] would not affects on the differences between the numbers in the segment [2:n] so it would not affects how you have to deal with them.
G is unsuitable for a codeforces contest.
Why?
My idea during the contest is to use a segment tree to simulate augmentations in max cost flow. It is simple but requires tedious coding and effort to fit the memory limit. I thought this was the intended solution, but it seems that the intended solution is a much cleaner one, so I take my previous word back.
My solution works for any matroid. It is interesting that for this particular matroid there is another solution. Can you please explain how to solve it using flows? Does it work for arbitrary number of colors? What’s the complexity?
Overview of my solution 176404703:
Flow Graph.
Nodes:
Edges:
We want to find a maximum cost flow that saturates all edges of type 2. We will do this by adding an augmenting path for each day in decreasing order of day. All augmenting paths start from the source, pass through one or more topic nodes, and then the sink.
Efficiently adding augmenting paths.
It suffices to construct a data structure that maintains the following subpaths and their distances:
The maximum-cost augmenting path is the union of at most $$$k$$$ of these subpaths, plus a forward edge of type 4. Our data structure should also support updates of the form: Add or remove a range of backward edges of type 1.
In general, we can use a lazy segment tree to maintain the subpaths. The segment tree should support updates of the form: Add or remove some range of backward edges of type 1. The segment tree uses $$$O(nk^2)$$$ memory and takes $$$O(k^3\log n)$$$ time to process each day $$$x$$$, if there are $$$k$$$ topics in total.
Is there some reason why you process days in decreasing order? Seems like your solution doesn't depend on that.
Another thing is that theoretically there might be an issue of overlapping backward subpaths, but it can be fixed manually by removing overlapping part of the path, right?
It makes my implementation simpler (but it's not necessary).
I believe that if you take the maximum-cost path that passes through the minimum number of topic nodes, then it won't use the same edge twice. This should work because the graph can never contain any positive-cost cycles.
why this code got WA. T^T? I want to know WA testcast.. 176378204
Take a look at Ticket 16296 from CF Stress for a counter example.
thx .. !
Garbage pretests on C, lots of hacks and wrong submissions passed.
It's not about garbage pretests but strong programming debug testing skills IMO
Yeah yeah yeah next time replace the pretests with the samples. That can train your debugging skills so well!
Can anyone explain the approach for problem D?
Only I think F much easier than E1 and E1 much easier than E2?
Maybe because I am not good at math and interactive.
Anyone explain C ( I thought you can increase by one at each operation therefore I find next greater element for each from last and then made this current element equal to that and push this index min(diff,k) times but it was not that simple)
Each operation on index
i
only affects the relation betweeni
andi+1
, therefore each operation should be dedicated to some consecutive pair of items in which the first one is bigger than the second. Let's create a differences array in which we will storea[i] - a[i + 1]
for each0 <= i < n - 1
that satisfiesa[i] > a[i + 1]
. Sort this array in an ascending order, and these are your "missions". Now obviously we rather use the earlier operations to satisfy the small missions, so iterate over the missions array and subtract the value of the current operation (starting from the first operation) until you complete it.What's wrong if i just print 1,2,....,n? Can you tell me some counter test?
1
8
8 1 7 6 5 4 3 2
What would be wrong if I print index for every i such that a[i] + index = n+1?
So for example for array : 1 3 4 2
Why this answer is wrong? : 4 2 1 3.
After all the operations , array would be: 5 9 11 12.
So inversions is zero here. Did I understood question wrong? Jury is giving WA at this TC.
My Approach to E1 was the following: You ask for set A from [0 to 2 * (remain_size/ 3)] and set B from [remain_size/ 3 to remain_size]. if the responses are different, it means that the number is in the intersection between A and B, if the responses are the same, it means that the number is not in the intersection between A and B. Could someone please tell me what is wrong with this reasoning?
Not necessarily. The number can be in the intersection, with YES being the honest response, and NO being a joke.
Also not necessarily. WLOG suppose the number is in A but not B. Answering YES to both is valid, since the second answer can be a joke. Answering NO to both is also valid, since the first answer can be a joke.
It sounds like you are counting joking responses as lies (ie valid but inverted) whereas they should just be ignored entirely. YES YES doesn't eliminate anything because it means it's either in A or B without saying anything about the intersection.
oh I see, the jokes are not lies. Than you!
I think A is not that trivial. You might hesitate if you think a little bit more.
I guess many just reduce to k then use operation 2 once, but that won't work in the corner case "0 1 0" where k=2.
You don't need 1st operation at all. Just apply 2nd until array become [1] or [0].
Suppose n=20 and k = 15. After one operation-2 the array's length is 6 where you cannot apply operation-2 anymore.
Heck, then I misread more than one problem in this contest :^(
Can't you just do this - 1. If there is atleast one "1", answer is YES 2. Otherwise answer is NO
Yes that's still correct, but the actual operations to achieve [1] might need case analysis.
Yeah, but we are trying to find out why this works.
If n > 3 then you can choose any 1 and there will always be two adjacent values not including that value which can be used to reduce n with operation 1 until n == k.
Then you just have to check that n, k in (2,2), (3,2) and (3,3) are all possible which is easy to do (can all be done without ever needing operation 1).
Yeah, this one also works, thanks for sharing!
Actually, your approach is correct with single distinction: you should reduce to 2*k-1 and apply 2nd operation twice (like in this corner case you mentioned).
And if n < 2*k-1 — reduce to k as you supposed initially.
Yes we can just use operation2 when k=2. k>=3 is the general case.
Yeah, I noticed the flaw :)
Corrected for the general case.
In my opinion that's the best way a problem A/B can be. Still challenging, so you have to think to come up with a solution and beginners can develop their problem solving skills further than just improving implementation skills, but with a simple solution, so any beginner can solve it.
Memory limit exceeded on C, wtf ?
How the fuck does taking the difference array and not sorting it pass pretests in C?
Wrong Ans on test case 46, what? :( 176324763
Lol me 2! Got FST'd for the first time! I got a time limit exceeded error on test 39. ANyone else?
Got MLE on test case 45 :(
Got WA on test case 47
Yeah, me too. FST on TC 39. >:|
Same! I think everyone who tried to be greedy without proof failed on TC 46
I got lazy to implement a lookup function in o(n); truly deserve that TLE :(
nice contest but little sad that couldn't finish coding D in time , GRs should be given 2:30 hrs I think atleast
Is F solvable with Mo?
Maybe hard because of the variety of $$$k$$$
It has updates, so that would be O(N^5/3)
I coded Mo with updates in $$$O(n^\frac{5}{3})$$$ but I can't make it pass. Maybe it's doable with tweaking the constants enough. The general idea is the following.
Let's maintain $$$\mathit{cnt}[x]$$$ — the number of occurrences of a value $$$x$$$ and $$$\mathit{cnt}_2[i]$$$ — the amount of values that have $$$\mathit{cnt}[x] = i$$$. That is trivial with Mo with updates.
How to obtain the answer for the query $$$k$$$ from that? Well, we want to take gcd of all $$$i$$$ such that $$$\mathit{cnt}_2[i]$$$ is non-zero. Then check if it's divisible by $$$k$$$. Obviously, there are $$$O(\sqrt{n})$$$ non-zero values.
How to use that fact? Well, let's split the values into the ones that occur at least $$$P$$$ times in the entire array at least once throughout the updates. There will be about $$$\frac{n + m}{P}$$$ of them. To find them, maintain a set of values sorted by their $$$\mathit{cnt}$$$ and mark the top ones as big after every update. Must be $$$O(m \cdot \frac{n + m}{P})$$$ in total.
So, we can check the values of $$$i$$$ from $$$0$$$ to $$$P - 1$$$ naively and then $$$i = \mathit{cnt}[x]$$$ for all big numbers $$$x$$$. That sums up to a $$$O(P + \frac{n + m}{P})$$$ query. So the optimal $$$P$$$ is around $$$\sqrt{n + m}$$$. Since taking consecutive gcds doesn't make your complexity multiply by log, it's still just sqrt.
So there is a Mo with updates part that is pretty slow complexity-wise and all the other parts that don't exceed sqrt but have a large constant I guess.
Thank you, got it
It's good idea to find answer dividing cnt on small and large values, I came up with similar idea, but couldn't implement
Yeah, my question was more likely "is there some implementation which fits TL" rather than "is it solvable"
Why does this pass lmao. I have not seen a solution like mine and I'm going to assume I somehow BSed through the problem.
https://codeforces.me/contest/1746/submission/176328481
It's correct. The number of position where given and sorted differ (which will always be even) is exactly twice the number of swaps needed. If answer is X, first X mismatches would have a[i] = 1 and b[i] = 0, and second X mismatches would have a[i] = 0 and b[i] = 1. These lead to X swaps.
Thanks for the explanation. I had that train of thought and decided to go with it, and I wasn't sure if it was true for all cases and if there was a corner case that I was missing. Thanks again.
No problem
Because it's correct solution.
Weak prestests for C
Too many authors make a round tough.
Why so many FSTs on C? I guess many small cases were included in pretest.
Actually, most fsts were from hacks with really small n (like 6 or 8). They just didnt put all permutations of small size on either pretests or systests.
what is the test 47 on problem C ? A lot of people are fallen down in test 47
I want to know how the answer of problem E changes.
My solution is: ask $$$82$$$ queries, each query contains $$$\dfrac{n}{2}$$$ numbers, randomly choose from $$$1$$$ to $$$n$$$.
A number $$$y$$$ can be the answer if and only if for every $$$i$$$, it satisfis query $$$i$$$ or query $$$i+1$$$. That is, if the answer is fixed, the possibility of recognize a wrong answer is $$$1-0.75^{81}$$$, It will get correct answer of a single test case with a possibility of $$$\gt 0.99999$$$. But the solution doesn't work on test $$$13$$$ for many times.
The grader is adaptive
But I want to know how it works.
The grader probably has two sets: the possible x values if the last answer was a lie and if it wasn't.
There are some solutions to E1 can be searched on the internet.
First , Second , Third
Should it be unrated ?
And what happend to F ?
Also this one: Codechef GUESSG.
Gonna tell my kids that contests used to have strong test cases
Really interesting E1-E2 problems!
Lmao FSTed both C and D :pepe_cry:
Tough round. What is the logic for problem C? I didn't get it, but many others thought they got it but failed system testing.
.
If you have a permutation of size n, you can always add to it in a way that all numbers become n+1. For example, for the permutation 3 2 4 1:
[3, 2, 4, 1] + [2, 3, 1, 4] = [5, 5, 5, 5]
(this ignores what is added to the suffixes)
Finally, it is important to notice that the suffix additions won't change the relative order of the numbers in a way that it creates an inversion. The number of inversions will be 0. This way you can construct the answer.
Spent over 2 hours on the question and didn't even understand the premise. Thought it was increasing by 1, instead of i.
.
https://www.codechef.com/submit/GUESSG?tab=statement
can some1 help me in my B submission getting runtime error in test2 while all cases i can think of are coming right
This line here is wrong :
if(num0==n || num1==n) cout<<0<<endl;
look at this test case :
answer is 3 not 0, another question what is the purpose of these variables :
count, ok, temp2
, I think they are useless.thank ill recheck
editorial?
I misread ques C I thought that we can increase suffix of a by 1 rather than 'i' T_T
Sad Story: I passed pretest of problem F and got WA3 on system test. After system testing, I resubmitted 10 times (with different comments each time) and passed system test each time. What a terrible luck!
These are the accepted submission IDs after system testing: 176386615 176386593 176386555 176386511 176386479 176386450 176386432 176386407 176386386 176386363
Me too. The same code got AC after ST but failed ST. So sad.
Setters should definitely be more careful than this when setting a randomized problem.
Editorial mentions "chance of failure is around $$$\frac{1}{2^{30}}$$$ so it's safe to submit", but nowhere they take into account the fact that you're answering 300000 queries for 100 test cases, so when you're running your algorithm 30000000 times, it doesn't look so foolproof anymore, does it?
As soon as I read the problem I realized there was a decent chance someone would fail system tests here, and unfortunately it seems to have happened.
First time?
https://codeforces.me/blog/entry/69036
Need testcases for D as the test 2 is quite a big one.
Never waited this eagerly for any editorial.
Attention!
Your solution 176348990 for the problem 1746E2 significantly coincides with solutions Tutis/176348990, null_awe/176378653. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I copied code from https://oj.uz/submission/592003
oop I'm on the other side of this, also copied code from https://oj.uz/submission/592003
Can some one please help me why my subission failed for problem C?
In C I print index for every i such that a[i] + index = n+1?
So for example for array : 1 3 4 2
Why this answer is wrong? : 4 2 1 3.
After all the operations , array would be: 5 9 11 12.
So inversions is zero here. Did I misunderstood the question? Jury is giving WA at this TC(Test case 2).
Submission No: 176389069
1 3 4 2 -> 1 3 4 3 -> 1 5 6 5 -> 4 8 9 8 -> 4 8 13 12
as you can see there is one inversion in final array
Because the array would be: 4 8 13 12
If you add 1 to the number in position 4, you are not adding 1 to the 4 in the original array. Following the approach so that all numbers become n+1 (ignoring suffixes) the answer is 3 2 4 1. Here 1 is added to the number in position 3.
how to solve E1/E2?
any hint for today's D? I know the fact that I need I start with 1 and c1 will be k ,then go to its' children and divide their parent's value of C among them in a way that that everyone has C value of parent / child count & (parent / child count) + 1 but in which order should I distribute I am confused about that, any hint ?
Since larger C is always better, sort by the difference of two possible target function values of children.
I did same but this gives TLE 176402693. Any hint.
can someone explain the solution for problem C
You can start from a[1], you want all the numbers after it to be bigger than a[1] so you can just add a[1] to the suffix [2:n]. then go to a[2] and add a[2] to the suffix [3:n] ans so on. Notice that for example adding a[1] to the suffix [2:n] would not affects on the differences between the numbers in the segment [2:n] so it would not affects how you have to deal with them.
I think google kickstart is the common source from where people copied but i want to know proper reason why my code is not accepted for problem A and B and there may be chance that some concept matched with the other but whole code is not matched.
You can start from a[1], you want all the numbers after it to be bigger than a[1] so you can just add a[1] to the suffix [2:n]. then go to a[2] and add a[2] to the suffix [3:n] ans so on. Notice that for example adding a[1] to the suffix [2:n] would not affects on the differences between the numbers in the segment [2:n] so it would not affects how you have to deal with them.
What I written the code my code is correct because during the contest it is showing accepted but status is skipped after end of contest so i want proper reason why my solution of A and B is skipped.
I am sorry that this happend to you but I really don't know how it works or why the system skips solutions.
do you know how to talk to system?
No, Sorry
Anyone knows how to solve interactive problems on c#? I got Idleness limit exceeded despite flushing console Submission:176402733
Bad pretest. Got FST and dropped to candidate master.
Have you tried proving your solutions instead of guessing?
I didn't, but I realized the mistake I made in the code just after I saw "failed system test". So I think stronger pretest can avoid such kind of sad stories.
I think what you said have reason. But it can't be an excuse for bad pretests.
I'm ikun, Henry Xu please shut up
FST for D because the inf I set is too small. LOL.
too weak pretest for problem c
There is a problem,if someone in the same room of me, and he also solve some problems,then some of his friends want to cheat, he don not wanna take any risk,so he might take picture of my code and send to his friends. Or there is no way for my solution D are similar to 2 people who submit a long time after, that might be a really serious problem
I can't find another way how that 2 people get my solution for the problem D. I do not send mysolution to anyone ever
However no one in your room locked D. It's impossible.
What if this actually happened? What should we do to prove that we're innocent?
It could be a really serious problem,and someone might have done this before.
I m surprised that few people didn't thought about two pointer in B. Got ac with two pointer.
please read all the codes before you say that
srry bro didn't notice that
It doesn't matter, but I think you'd better say "few people" 'cause we can't ready all codes.
k bro will take care of that
Em, "few" means not much, so "few people didn't" doesn't mean what you want to say in my opinion, right?
When/where will the drawing for the t-shirts be announced ? For once I managed to do top 500
ao tao dau duma
Congratulations to tshirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.
As usual, we used the following two scripts for generating random winners, seed is the score of the winner.