Привет! В 25.07.2023 17:35 (Московское время) начнётся Codeforces Round 888 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 7 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Задачи были придуманы и написаны нашей командой: myav, Aris, Gornak40, senjougaharin и Vladosiya.
Также большое спасибо:
MikeMirzayanov за системы Polygon и Codeforces.
tute7627 за красное тестирование раунда
- oversolver, sevlll777, pavlekn, zwezdinv, Sokol080808, 74TrAkToR, vladmart, EJIC_B_KEDAX, Vladithur, KseniaShk, Be_dos за жёлтое тестирование раунда
- moonpie24, FBI, meowcneil, NintsiChkhaidze, Phantom_Performer, SashaT9, spike1236, Kalashnikov за фиолетовое тестирование раунда
- TheGoodest, Pa_sha, Sasha0738 за синее тестирование раунда
- Syuzi777, Tahseen за бирюзовое тестирование раунда
Всем удачи!
UPD: Разбор
May 19, 2023 what
May be Time travel xD
//I don't know why, but my comment got sent 2 times, don't pay attention
Here before "My first unrated contest" comments
hoping to solve atleast 3 problems
it's ironic that all the testers are not actually eligible for div 3...
except cyan ones
cyan wasnt there when i posted the comment lol
Love your profile picture
Waiting for this! Me also hoping to solve at least 3 problems. Best of luck to all contestants :)
Hoping to become Expert in this round
.
why is there no cyan, green or gray testers?
Palindromic Round!
i hope to be blue this time
A better version of the above given meme.
Oh nice idea!
I did not Copy it. You are just being jealous that it is the better than yours.
I think this makes a lot more sense.
but, rainboy is blue.
color doesn't matter the thing that matters is your coding skills
Yes Yes Color doesn't matter but what matters is Common sense which I can see is not common in you.
If you would have checked you would have known that rainboy is blue not purple, or are you color blind.
Regards;
Aiman.
rainboy's rating is changing fast, used to be purple, and this picture may be outdated, so you cannot say he/she is color blind (rainboy, on Jul 23, 2023; rainboy, on Jul 16, 2023; rainboy, on Jul 11, 2023; rainboy, on Jun 24, 2023).
rainboy's rating is changing fast, and used to be purple (rainboy, on Jul 23, 2023; rainboy, on Jul 16, 2023; rainboy, on Jul 11, 2023; rainboy, on Jun 24, 2023).
I have a really good feeling about that this would be my last rated Div. 3 contest and I would have become a blue expert after this 888ᵗʰ round of Codeforces!! May the Force be with us
.
This aged well
^^ i also became a green
I have exam (TT — TT)
Obviously, exams cannot be compared to codeforces :) Give up exams and choose to fail, embrace Div. 3
yaaaa Now,Let's ditch the exams and embrace our coding superpowers! (っ▀¯▀)つ
Hopefully, we will see a problem connected with number $$$8$$$, lol.
I think most of Div.3's are made by Vladosiya
Now I'm mostly helping new authors and sharing experience:)
why do you only make Div.3 why not Div.4
Goodluck to all :333
good luck everyone ^-^
best part of the comment section is I see anime pfpS and discover new interesting animes
As a participant of this round, I can confirm that this is a great contest and has great problems, :D
I think this will be a good one
I hope I become Specialist wihs me luck
I hope this round will be the great round of Div.3!
spoiler : it wont
Yes it was but sadly A is hardeset problem
Good luck
how many problems i have to solve to become pupil??
Out of competition, but I'll try my best to do it ^_^
I want to do it but I can't stay up late!
It is so good to have a contest every few days, hopefully i can cross 1500 today
I don't know if this is the right place to say this, but I've noticed for a while now that div3 round announcements say that you can only qualify as a trusted div3 participant if you "do not have a point of 1900 or higher in the rating." Shouldn't that number be 1600 instead?
I think this is a translation error. My understanding (from the original announcement of the trusted participant system) is that you must never have had a rating above 1900. In other words, if your rating is above 1900 at one point but then falls below 1600, Div. 3 rounds will be rated for you, but you will not appear in the official standings.
Experts to lower rankings in Div.3 be like:
After playing div2,I feel that div3 and div4 are still suitable for me
literally no one asked
Nobody asks for any comment. By your logic, comment section should always be empty.
Tends to Pupil:)
I wanted to add a few friends, although I was just preparing for the contest with the attitude of testing the waters
hoping to solve at least 4 problems
Thanks for this contest!
In first line of blog "You will be offered 6-8 problems" .Later "You will be given 7 problems and 2 hours and 15 minutes to solve them ".So, 7 problems will be there ?.
yes
6
It's fun that the round will be rated for me.
tbh I don't see it as fun because you may become cm today by spamming div-3 , I think div-3 should be unrated for participants if they are >=1600 during participation even if they registered for div-3 when <1600
But I won't be in this contest because my mom doesn't let me stay up all night.
come on bro stay up , don't be a mommy's kid
Why do you have to stay up all night? Look at tourist. Maybe he just need to wake up and spend about just only half an hour to ac this contest (equal to the time i understood problem E). Maybe u can follow that way :D.
J4F
hope to be specialist in this contest
Don't forget int overflow — use long when you are summing up!
I am at the lowest confidence in my life.
888 is a special number!!!!!!
I missed 777 and 666, at least I won't miss 888 round
Good Luck everyone
Good Luck
I will solve atleast 5 problems.
You are strong!
so she knows what awaits her. emmmmmmhahahahaha~
not good, the problem statements were not clear at all and were very ambigous
Thank you Vladosiya very much. This is the best Div.3 contest I've ever written.
Why I an rated ??????
That's so crazy! How come?
Because you registered while you were specialist.
┭┮﹏┭┮
Readforces
my guy only read A and decided to conclude the entire contest was readforces
It is still readforces because half the time I'm trying to decipher what the problems are saying, the statements can definitely be phrased better which a lot of people have mentioned also
readforces isnt unclear wording, its when u got paragraphs upon paragraphs for a problem statement
any hints to G?
Yes/NoForces
D: Let difference d[0]=a[0], d[i]=a[i]-a[i-1] when i>0. If the missing prefix sum is n*(n+1)/2, then {d[i]} will be a permutation of [1, n] missing one element. Therefore, for this case we need to check in {d[i]} are pairwise distinct and inside range [1, n]. Otherwise, we will have a[n-1]=n*(n+1)/2, and n-2 elements of {d[i]} will be inside [1, n] and distinct, the last element will be the sum of 2 missing elements. So for this case we need to check if {d[i]} contains n-2 different numbers inside [1, n].
E: First for potions with infinite supply we can just set their cost to 0. Then, if potion i can be obtained mixing {j[1], j[2], ...}, we add a directed edge (j[t] --> i) for each j[t]. Since no potion can be obtained by mixing itself, these edges will from a DAG (directed acyclic graph), and we can run dp on the topological order of the DAG: Let dp[i]=sum(cost[j]) where edge (j --> i) exists, and cost[i]=min(cost[i], dp[i]).
F: If a[i], a[j] and x have only 1 bit, then if a[i]==0, a[j]==0, we can set x=1 then (a[i]^x)&(a[j]^x)=1, if a[i]==1, a[j]==1, we can set x=0 then (a[i]^x)&(a[j]^x)=1, if a[i]!=a[j], no matter how we set x, (a[i]^x)&(a[j]^x)=0. So we need to find (i, j) such that a[i]==a[j]. For general cases, we need to minimize (a[i]^a[j]) so that sum(t: 0<=t<k, the t-th bits of a[i] and a[j] are same)(1<<t) = (1<<k)-1-(a[i]^a[j]) is maximized. This can be processed using a trie, or sort a[i] and find the minimal a[i]^a[i+1].
G: For a single query (a, b, e), the maximum height of nodes on the path cannot exceed h[a]+e, which means, we can pass an edge (u, v) if max(h[u], h[v])<=h[a]+e. Therefore, we can sort queries by h[a]+e and sort edges by max(h[u], h[v]), then solving queries using dsu.
F can be solved by property of xors:
min(x^y, y^z) < x^z , for all non-negative integers x, y, z (x < y < z)
so we can sort a, and find min xor of all a[i] ^ a[i + 1]
Is there any intuitive proof of this property of xor?
yes, you can read it here
Find first bit so that: -it is in some of the numbers -it is not in all of them Then it's either in $$$y$$$ and $$$z$$$ or only in $$$z$$$ (because $$$x < y < z$$$). In both cases it can be seen that this bit is in $$$x \oplus z$$$ but not in $$$min(x \oplus y, y \oplus z)$$$. Later bits won't matter
Why ans can be calculate by ans = mn | ((a[i+1].fi ^ ((1 << k) — 1)) & (a[i].fi ^ ((1 << k) — 1))); ?
actually it is just: ans = (a[i+1].fi ^ ((1 << k) — 1)) & (a[i].fi ^ ((1 << k) — 1));
at first we want to maximize some (a[i] ^ x) & (a[j] ^ x), now suppose we want to use some Kth bit up to k, then you can see that Kth bit have to be in both of a[i] and a[j], or doesn't appear in both of them,
suppose a[i] has Kth bit and a[j] has not, then let's try to get this bit in our result
using Kth bit in x: (1 ^ 1) & (0 ^ 1) = 0, not using Kth bit in x: (1 ^ 0) & (0 ^ 0) = 0
from above it is easy to see that it is efficient to minimize xor
so we don't care about cases where a[i] has some bit and a[j] hasn't or reversed.
there left two cases:
|1. both a[i] and a[j] have some Kth bit
to get this bit we shouldn't use it in our x, (1 ^ 0) & (1 ^ 0) == 1
|2. both a[i] and a[j] have not some Kth bit
to get this bit we have to use it in our x, (0 ^ 1) & (0 ^ 1) == 1
since we can use all bits up to k, our x should contain all bits up to k, where a[i] and a[j] haven't them.
|1. (a[i+1].fi ^ ((1 << k) — 1) taking all zeros from a[i] up to kth bit
|2. (a[i].fi ^ ((1 << k) — 1) taking all zeros from a[j] up to kth bit
|3. (a[i+1].fi ^ ((1 << k) — 1)) & (a[i].fi ^ ((1 << k) — 1)) combining zeros, where a[i]'s Kth bit = 0 and a[j]'s Kth bit == 0
I hate that I didn't see this comment ahead of time (although it may have been posted after the game)
Thanks, got it :D
How do you thing is it possible to solve G if queries are online?
Using persistent DSU
Maybe we need to use some persistent data structures.
For each edge $$$(u,v)$$$, let the cost of the edge be $$$\max(h[u],h[v])$$$. Then for query $$$(u,v)$$$ where $$$u\neq v$$$, the minimum of the maximum height of the nodes on the path is equal to the minimum of the maximum cost of the edges on the path. So we can build MST and use binary lifting to find the answer.
I did try to write the binary lifting solution for G (feeling dumb after finding out doing it offline is much easier). I get a WA on test 4. I'm not sure whether my implementation is wrong or there indeed exists a counter-case that one of the best path doesn't lies on the MST.
215605164
Maybe my online solution can help you 215601542.
I write the Kruskal's algorithm and build a tree to solve it.
Build a kruskal reconstruction tree(or dsu tree) and find lca of the 2 nodes in each query
minimizing xor of two elements can be done easier: sort the array, answer will always be the xor of two consecutive elements.
F can be solved by max prefix for the binary presentation, there's maximum two unique numbers with the same max prefix. once we identify the max prefix, we can use a map to collect the ones that have the same max prefix, or we can just sort and compare adjacent elements.
Bad statement for most problems :(
+1
+2
+1
+1
Indeed one of the worst contest ever
Yes-NoForces!!
i feel language was bit difficult.
Learning tries was after all worth it saving me today. Problem F felt really good to AC :)
It can be solved using recursion without tries
can you share your implementation
[submission:https://codeforces.com/contest/1851/submission/215630074]
The key idea is to find two numbers with miminum xor. Let's try to find to numbers with common $$$k-1$$$ th bit. Divide the array into two so that in two arrays $$$k-1$$$ th bit is common in all numbers. Solve recursively for $$$k-2$$$ th bit and so on. If you put ending conditions correctly, this will work
Thank you :), i am pretty bad at recursion so was not sure about how to implement it even after getting intuition. Since i solve nearly all bitwise problems involving some random function going bit by bit in linear iteration
funny my solution looks almost exactly like yours. mine didnt pass tho :(
215616590
Bro ours look same. even both of us failed on same testcase :(
Can also be solved by taking xor of two closest numbers. (Adjacent elements in sorted array).
You just have to find optimal 'x' for all the pairs of adjacent elements of the sorted array of 'a', whichever pair gives max (ai^x & aj^x) is the ans.
whats the reasoning behind adjacent elements ?
I have an intutive explanation, for a bit to be included in the maximum answer either its not set in the two chosen indices or set in both, exploiting this information note that we can greedily start by trying to get the kth bit set first, so the whole array is divided into two multisets, one which doesnt have this bit set and other one has all the elements with this bit set, how to achieve this? Just sort the array, all the numbers which have kth bit set will be together, this holds(try to visualize this, it will make sense), Now if I want the kth bit to be set in the maximum answer, the final answer is going to be any two adjacent ( Just note that all the numbers with kth bit set will be consecutive, then among those all with k-1th bit will be consecutive and so on, and also numbers with kth bit set the numbers with k-1th wont set will be together, since thats just the nature of sorting), so if you were to write a bruteforce divide and conquer the final set will be some two consecutive numbers. Sorry if its lengthy but its a bit intutive to explain by writing
Really nice and intuitive explanation makes a lot of sense. So the very first part figuring out that bits of both the numbers need to be either both set or both unset gives us an idea that the closer they are in their binary representation at higher bits, better will be the answer.
Yes that's the key idea thats why taking minimum adjacent xor in the sorted array works but you can check for all the pairs as well
Its is pretty amazing that how value of $$$a$$$ and $$$b$$$ can be chosen independently of $$$c$$$ and the problem boils down to finding the optimal pair with minimum xor and $$$c$$$ can be then found using $$$a$$$ and $$$b$$$
can you share your idea with tries? I tried to solve the problem with it, but I failed.
We have the following function
We will get a bit set in the result of this function only when both bits of $a$ and $$$b$$$ have same value and $$$c$$$ opposite of them. That can be done by writing a truth table.
I stored all the numbers using Trie. Then iterated over all the elements of the and for each element tried to find the one which gave optimal value.
For that i begin iteration from root node and bits of current element $$$a$$$ and see if i can get bit same as that of $$$a$$$ in $$$b$$$ or not. You can refer my submission 215602305
nice one! thanks
It was hard for me to concentrate on reading those problems, I liked it tho
D was awful, imho
I think my F is hackable
Submitted just after the contest got over.
Overall looks like a decent div3 contest, I have enjoyed solving A-E.
How to solve E ?
How to solve E ?
reread the statement and you ll see that if you draw the graph of elements (needing each other) it will be a dag -> just do a simple dp on it. my submission: 215587840
I thought that G was about finding a path, so that $$$max - min \le e$$$. Btw, would there be a solution if this was asked?
Lets Go Pupil here I come..........
rank 834 can add 39 to become expert?
By rating predication, you will get +30
Use this extension for rating prediction Carrot
Nice problems but bad statments for most of them , thanks anyway!
What the hell
Can someone share their solution to B, C and D.
B — sort odd values and even values while not swapping odd and even with eachother, then check if array is sorted. C — you need to find shortest prefix that there are at least $$$k$$$ occurences of $$$c_1$$$, and the shortest suffix that there are at least $$$k$$$ occurences of last color. If first and last are equal, you just need to check that there are $$$k$$$ tiles with color $$$c_1$$$, else you need to check that sum of lengths of the found prefix and suffix is less or equal to $$$n$$$ D — didn't attempt
Here's what I am doing for B, It is the same as you described.
Sort the array and compare it with the original array if both elements at same position are odd/even then its YES if NO then NO
problem E is an easy version of one of the provincial team selection test for NOI of Ahhui, China 2014(AHOI2014) problem. See in here:https://www.luogu.com.cn/problem/P4042
a
It's a place where u recognize how stupid u are.
sorry
D was frustrating.
can some one explain this sample case for problem E
4 2
1 1 5 4
2 4
3 2 4 3
0
2 2 4
1 2
how is the answer 0 0 0 0 , here
Notice that Nastya already has unlimited numbers of potions 2 and 4 so the answer for 2 and 4 is 0. Also, to get potion 3 you can use potion 2 and 4 so you don't need any coins for potion 3 and the same for potion 1 so the answer is 0 0 0 0. Hope this helps!
Thanks , I got it
potions 3 can be obtained by potions 2(costs 0) + 4(costs 0) = 0
potions 1 can be obtained by potions 2(costs 0) + 3(costs 0) + 4(costs 0) = 0
Thanks , I got it
In problem A, is there any specific reason why Vlad cannot talk to the person on the same steps of the escalator??
Two people with heights a and b can have a conversation on the escalator if they are standing on different stepsIt is given in problem statementI know bro.... it just bothered me becoz it is not so realistic
ohhh, XD
There is one type of escalators that has very narrow steps, that each step can only hold 1 person. I think the author is referring to that type of escalators??? :)
but many people can be on the h+m and h-m step ? weird escalator
lmao didn't think of this
It might be realistic because in some cities it is a known rule that people stand on the right and walk/run on the left side of an escalator. So, two people standing and talking on the same step will bother people in a rush.
Oh i see.. thanks
Vlad has bad breath.
Hello, could someone please help me figure out why my code is giving a runtime error on E? I don't usually use python https://codeforces.com/contest/1851/submission/215620727
You can think of it as a depth-first traversal for each end product, towards the ones it depends on
Maybe it's the python recursion limit/deep recursion issue, I know very little about python but I've seen similar kinds of questions regarding recursion/dfs traversal of a tree popping up here on codeforces.
That must be it! I will try with stack, thanks for the tip.
EDIT: That was it, AC'd now. Thanks!
By default python has 1000 as the maximum recursion depth. Theoretically you've got to change it via sys.setrecursionlimit(), let's say sys.setrecursionlimit(10**5) and then it works, but in practice it will most likely give you memory limit exceeded on codeforces. So you just have to rewrite it without using recursion sadly, just directly use stack.
Interesting stuff! Glad I used python this time, got to learn :D
What problems A and E :<
too hard to know what these problems asking aboout :<
Lol I didn't even understand the statement of problem E. Eventually, i just did wat-task-told-me-to-do + my guess and intuition and AC-ed :D
if problem E, the statement "Moreover, no potion can be obtained from itself through one or more mixing processes." is removed, I guess we need a scc to solve it?
No, because if there is a cycle, then you:
a) have one of the potions in the cycle which is trivial or
b) don't have any of the potions. In that case, you will eventually revisit a node. Since a revisit is only possible due to a cycle, you will realize that the node came via a cycle and then can just buy the cheapest potion in that cycle.
I solved it using modified dijkstra, checked the editorial and was confused so read the problem statement again. I think even the top folks solved it using modified dijkstra only.
Time to switch to hackforces
Problem statement is very hard
Forth problem is very interesting, I hope I solved it correctly)
Thank you for having blank lines after the answer after every test case in Problem G. It made understanding the sample answer easier.
Could you share your approach for G?
Let $$$H$$$ be your current height and $$$E$$$ your current energy. If we go $$$x$$$ units up, your height changes to $$$H + x$$$ and energy changes to $$$E - x$$$. On the other hand if we go $$$x$$$ units down, your height changes to $$$H - x$$$ and energy changes to $$$E + x$$$. In both cases, the sum of your height and energy stays constant (equal to $$$H + E$$$, the sum of your original height and energy).
Consider some query where you start from mountain $$$a$$$ with $$$e$$$ energy. This means that anywhere you go, the sum of your height and energy will be $$$h_a + e$$$. In order for your energy to stay non-negative, your height must not go above $$$h_a + e$$$. This means that you can go to any mountain $$$u$$$ with height $$$h_u \le h_a + e$$$ and you cannot go to any other mountains.
Now, we can solve the problem in the following way:
Consider the mountains and roads as an undirected graph. We will keep a DSU to tell which nodes (mountains) are reachable from each other.
Sort all nodes $$$u$$$ in increasing order of $$$h_u$$$ and sort all queries in increasing order of $$$h_a + e$$$.
When handling a query, we need to add all nodes $$$u$$$ with $$$h_u \le h_a + e$$$ and edges between them into the DSU. We can iterate over all nodes satisfying the above which have not yet been considered and add all edges going from those nodes to nodes with lower height to the DSU. After that, the answer to the query is
YESiff nodes $$$a$$$ and $$$b$$$ are in the same component.Doing the above for all queries using a two-pointer approach is $$$O(n\cdot\alpha(n))$$$.
Total time complexity: $$$O(n\log n)$$$ due to sorting.
(slow) implementation: 215567991
Now, Waiting for the Editorials
Hope to become newbie after this contest
I couldn't debug G in time.Loved all the problems.
My thiscode gives correct output on my compiler and also on online compilers but somehow this is giving wrong answer on the Codeforces judge , what's the reason , please look into it.
Your binary search could return -1 as index of array which is an undefined-behaviour.
I have doubt in problem statement of problem E.It is not mentioned whether cycle will exists or not.
“It is guaranteed that no potion can be obtained from itself through one or more mixing processes.“
"It is guaranteed that no potion can be obtained from itself through one or more mixing processes."
In F there is no need to know Trie , my solution is just greedy + binary search
my solution was just sorting array and checking answers for consecutive numbers
yeah watched it , your solution best solution
Can anyone please explain the statement of problem e i still can't get it
There are $$$n$$$ potions, each has its own cost. Each of the potions can either be bought or obtained by mixing some of the other potions. You have an unlimited number of $$$k$$$ potions which means you can use them for free. For each potion determine the minimal cost you should spend in order to obtain it.
Thank you. But I'm still kinda confused in test case 1 in samples why we should use potions 2 4 5 for making the first potion (i know it's cheeper i mean why we should use three potions)?
The first number of each line is the number of potions we have to use. The potions itself go afterwards.
The contest was really nice! Though a lot of solutions were leaked during the contest on youtube, would request to run tougher plagiarism checks for this contest and ban those IDs who posted the solutions on youtube or copied them.
i took this contest while in an airport lol
can someone help me understand why am I getting runtime error for this code (problem C round 888 div3):
Try this testcase
Can E be solved using Dijkstra?
Can someone please explain why this solution is getting TLE in question E. I have used dfs. I have been stuck for an hour.
here's the modified accepted solution. Classic mistake ;p
Thanks a lot!! Also why didn't passing adj[] by value affect the complexity? Edit- I got it, since we have passed a pointer to the array not the whole array thats why it didnt affect the complexity
you need to send the arrays by reference (like sky_full_of_stars did)
Why am I not in the standings?
If you check the "unofficial" box, it shows me, but if you uncheck it, it doesn't.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
take part in at least five rated rounds (and solve at least one problem in each of them) do not have a point of 1900 or higher in the rating.
Thank you!
How to solve D and E? Why the problem statements are too boring?
F is similar to 1721D.
waiting for editorial...
the thing be sey you fit wait tire and nothing fit drop now...I no expect any editorial to drop until like after 1 or 2 days after them don finnish the contest..I no know why dem dey do like that sometimes. Me I feel sey dem supposed to don already prepare the editorial down before dem even start the contest sef..
Long statement sucks.
can someone explain why we can't solve e with simple array based approach. my code is wrong, but i am trying to update values to 0 for potions which r unlimited and then calculate cost, and simply giving the output by comparing. code
Oga, you no fit understand am be say you no fit understand am..Try to figure am out by yourself or else, I no think sey anybody get time to give you mouth for here
in D testcase 10:
prefix sum is: [13 21 36 42]
could not we assume initial array like this? [13, 8, 15, 6, 2]
[13, 8, 15, 6, 2] -prefix sum-> [13, 21, 36, 42, 44] and assume he lost [44]
what i am doing wrong?
initial array is not a permutation. Your task is to find out if the given array can matches permutation. A permutation of n elements is an array of n numbers from 1 to n such that each number occurs exactly one times in it.
thank you.
I was able to solve one problem, but still am unrated. Any reason for that?? (This was my first ever contest. Sorry if I'm being dumb)
To qualify as a trusted participant of the third division, you must:
Hey, one thing to clarify, does the triangle sign at the very right of the standings table mean the rating change?
Another question, Will I get the ratings of my 5 contests added, or won't they be added? (After i become eligible for rating)
It will be rated for you. Wait for the system tests to get over.
but kgb said that I need to be qualified for Div 3, by participating in at least 5 rated contests and solving at least 1 problem.
"Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you."
This is what's written immediately below in bold.
Boy was that a hard round. I could solve A and B in the first 40 minutes, and could only think of a DP solution for C :cry:
I could think of better than DP for C in 15 mins but it took me 45 mins to come up with the correct code.
Doesn't require DP though.
I'm sure it doesn't; guess I've been practicing way too much DP (and not other things) haha
Lol, initially, I too thought of a DP solution, seeing that it requires subsequence matching sort of problem. However, observing that it only requires checking of possibility of the pattern rather than optimization, I thought of the other solution.
Ah, that's cool! What's the other method?
Why the contest is begin shown unrated despite of being written "rated for less than 1600"?
It is rated,ratings will get updated after system testing.
seems that I have my first aked Div.3 contest :)
I failed system test on problem D because of integer overflow, and missed the chance to solve all the problems during the contest :(
Who knows, has system testing already ended or not?
Yes, it ended, hacks included
thanks
when ratings will update?
My solve E O(n) has Time Limit 14 bruh?!?!?!
It's not O(n),you're not updating p(i).
Testing has finished.When will rating update ?
ублюдок
My solution for D fell on system tests because I used int instead of long long in one line where I forgot a_i <= 1e18 when I was writing it. This is really annoying, and I think that a test case like that should've been on main tests. But oh well, lesson learned, from now on I'm always using #define int long long
So do I!
Next message: "My solution got TLE on system tests, then I submitted it without #define int long long and got AC. I think that a test case like that should've been on main tests"
Reached Pupil after this contest that I'm happy
Hoorah! My rating became >1000 this round :D
This contest is quite good
Finally made it to Pupil after a year of hard-work 😊
Congratulations!
https://codeforces.com/contest/1851/submission/216352004
wrong answer Jury has better answer (13) than participant (12) (test case 1)
Jury output: 1 3 14 My output: 1 3 12
(3⊕14)&(1⊕14)=(0011⊕1110)&(0001⊕1110)=1101&1111=1101=13
(3⊕12)&(1⊕12)=(0011⊕1100)&(0001⊕1100)=1111&1101=1101=13
What is wrong with 12 as 'x'?
Your output is 1 3 13 as I see
It has been a week but still cheaters not removed
To the respecful writers of the contest,I apologize for using ideone.com during the Round 888 Div 3. I regret that happended without my knowledge. I usually use codeblocks for c++ and Notepad for Java code in both languages based upon the question.But multiple testcases dont work at once so I used ideone.com. I use my personally mail-id and changed the settings(public access to my code). But for this contest I have used my College mail-id for paticipating the contest without changing the settings of ideone.com. May be from there my code was stealed. I apologize for that I will not repeat the same mistake once again. I will take atmost precautions while attending the test and I won't use ideone.com in my entire life during contest. Kindly Excuse me for this one last time.I won't repeat it.
I hope this message finds you well. I am writing to address a concern regarding my submission with 215612482 for the problem 1851D. I have noticed that there are similarities between my solution and that of another user, but I would like to clarify that I have not engaged in any form of cheating or plagiarism.
While I understand that the logic in my solution might coincide with someone else's, I can assure you that my approach and implementation are entirely original. It is not uncommon for multiple participants to arrive at similar solutions, especially for well-defined problems that may have limited viable approaches.
To further support my claim, I would be more than willing to provide a detailed explanation of my thought process, the steps involved in my solution, and any relevant code snippets that may help demonstrate the uniqueness of my approach.
Hello MikeMirzayanov,
Today I got a message from the system regarding the coincidence of my submission with my friend decltype_t submission.It is because of using common resource. In these codes we used the same templates for graph, topological sort, and for debugging. This is the proof for same. Graph template Topological sort template Debug template. However, the main logic is different.
We(Me and decltype_t) hail from same college and follow the same resources for practicing. We also have a combined repository. You can see the same here. I agree that it's my mistake that I didn't give the credit to the author for using his/her template. You can also check our previous graph or tree based question solutions where we have been using the same templates.
Thank you for providing this excellent platform.
my solution got skipped just because logic looks like others but i worked it after one wrong submission and just optimized it several times so not my fault it looks like others solutions
Dear MikeMirzayanov , kindly look into this as my logic was based on optimization of if else cluster statements in previous submissions
thanking in advanced for looking into this!!
Attention!
Your solution 215580877 for the problem 1851E significantly coincides with solutions Milind_Sharma/215580877, fredreicc_/215618955. 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.com/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.
This is ridiculous, having same logic does not mean copied code, all of my submissions are now skipped. I have never copied a single code in any of my past contest. This is clearly a false positive.
I fail to see how my code is similar to the other user, also I submitted around 1 hour earlier.
Please take a look at the codes yourself and decide 215580877 and 215618955.
MikeMirzayanov Vladosiya
MikeMirzayanov Vladosiya I have too been plagarised in this contest unnecessarily. I have even solved F problem that too within first 30 min. please check my code its not at all similar with others. I dont understand why I got plag. I had simple dfs call so that i can calculate the answer minimum just by topo sort. PLease see my code and give my ratings back. Its clearly wrong to plag someone who works hard. Kindly look into it and help me out.
'MikeMirzayanov Vladosiya Your solution 215615024 for the problem 1851E significantly coincides with solutions steve58/215601188 ...This is something not expected from codeforces the solutions by this guy and me is completely different I have used a simple graph topo sort which is having very common template of dfs call let me show you my code:
Here after taking the cost and making changes in its value depending upon free resources I had topological sorting in my code.I have used a simple dfs function which goes and checks its neighbours ahead then finally in ans array i stored the final minimum value of the cost and after topo sort value. My code is way different from one I am plagarized with . Please look in it and give my ratings back.
Hello, MikeMirzayanov Today, I've received a message from [email protected] that my code for the problems A and B are similar to the codes of the user kishorenanda. I really don't know this person and even where is he (or she) from. The codes are really short, so they could be similar to the codes of any other person who had just the same idea. But now all the solutions that I've sent to the system are erased from my official sendings. Rewatch my solutions, please. My solution for A: 215511238 My solution for B: 215514366
any idea for problem E (advance)? Where the graph has cycles?