Hello everybody!
Round 443 will start on Thursday, 26 October in 17:35 MSK.
Tasks are prepared by me, Konstantin Khadaev. It's my first round on Codeforces. Thanks to zemen, AlexFetisov, vepifanov, and Belonogov for testing problems, KAN for coordination, and MikeMirzayanov for this site and the Polygon platform.
Both divisions will have five problems to solve in two hours.
Scoring: in Div 1: 500 — 1250 — 1250 — 2000 — 2500, in Div 2: 500 — 1000 — 1500 — 2250 — 2250
Good luck to all!
UPD1: Congrats to the winners!
Div 1:
Div 2:
PS :- IT IS RATED -___-
You triggered the curse :/
Wow, Two contests in two days(CS Academy and codeforces) and written by the same author. I enjoyed the problems on CS academy, Hope they are good tomorrow too!
Is it rated means? I am new so i didn't understand what rated means.
Its the most common "three words" you will find on the CF. Next common three words is "how to solve".
=i'll make a submission...
-What is the complexity of your code ?
= O(N^3)
-
A could be quite reasonable depending on the problem. Consider the problem you are solving and the bounds, instead of making a sweeping statement on complexity.
i know , it just a joke :(
Is it rated?
you made the same comment last contest...
and got the 5th place in the contest !
ignore
Фалунь Дафа хорош
will it be available C#?
Codeforces Round #https.
I want to describe this not only as a contest, this is an opportunity to explore new thinks for everyone, and this can give a handfull of distribution of our future succes so I wish good luck to everyone and PLUSES ^-^ at the end.!
Great!
Can't register.
Simillar thing happened when I tried to login. I think server is very slow and unstable right now.
While registering, Error- "HTTP Status 403 -" :(
I was registered to the round, but now I see that I'm not registered and I can't register again (HTTP Status 403)
Apache Tomcat/8.0.46
Wow the scoring distribution is announced so early! I guess this is a non-"traditional" round...
It is traditionally delayed...
Why the delay?
Mission 6000 :p
Mission accomplished. :P
delayed))
Delayed again...
Delays, delays, delays :P :P
6000 reg only div2? Not bad :)
servidor is very slow today, hope the contest continue rated.
+10 min as usual
for the writer,pls be short!
Why test case 3 in div 2 C is 0? Is there no program? Thanks!
it's empty
its special :p !!
I don't get it, man!
(output => the length of your program)
Why ^ 0 is not a program?
Why empty program as output? (No program as output)
Thanks in advance!
It's the number of operations that your new function does before returning the value.
For example, if k = 2:
If the k = 0, then you have the following function:
Thanks!
How did you know it was empty?
What is the hack for B?
4 2 2 1 3 4
When the winner is changed most of the people count the new number of wins to be 0 but it should be 1 :D
Failed on TestCase 33 due to this reason feels so stupid.
4 2 2 3 1 4
4 2
1 3 2 4
How to solve Div-1 C and D?
div1C
Consider graph where there are edges from A -> B iff A can beat B , now consider each SCC in this , if a node can beat atleast one from this SCC and if atleast one from this SCC can beat this node , this node also belongs to the SCC , so an SCC can be characterized by mini and maxi which denotes min value of ith game strength of someone from this scc and similarly for max. This breaks the graph into a chain of SCC's , when you add a new node , find where it should belong in this chain , it will either belong complexity between 2 scc's or at the endpoint of the chain in which case just add this , or it will result in merging of a subarray in this chain into this node.
"when you add a new node , find where it should belong in this chain"
But assuming the worst case that at step #k you have k SCCs in the chain, doesn't this mean that the overall complexity becomes O(n^2*k)?
There's probably something I don't understand in your explanation. Could you maybe elaborate just a little bit?
Thanks in advance :)
EDIT: ah, nevermind, you can probably keep the SCCs sorted for each k and use lower_bound() or something similar
Summary of my performance this round.
Ignore ...
Why i prefer dynamic scoring
what's wrong with this 31762295 for div2 B??
vector.erase is O(n)
The problem C in Div. 2 was nice. Required a good bit thinking (atleast for me). My mind was blown...
How to solve div2 C ? Was it like taking Xor , and , or of all values and print in the same order. ?
no that will not print the correct answer.
Try in this input:
|3
^2
|1 Take x as 2.
Thanks , Then what was the algorithm behind this you constructed to solve ?
Suppose you have a 10 digits binary numbers — let 'xxxxxxxxxx' be his digits : what happen to those after the N operations? Can we get the same result with just 1x of each binary operation? :)
From there, we can see that for each bit in a and b:
bit off / off: and 0 operation
You can just do these 2 operations : AND (a ^ b) XOR b
Those rooms in which there are no hacks are going to be destroyed by system tests. n = 10, k = 4, arr = {1 5 4 3 2 10 9 8 7 6} ans: 5
oh...
sad(
Oh.The sad moment when you realise there were about 14-15 WA solutions in your room and still you couldnt figure out a hack. In my room there were no hacks at all :p.Dont know why I missed this case :(
Hacked 3 solutions in the last 3 minutes... (my last hack was 3 seconds before the end) So tense!
I think for div 2 C the key is strongly connected components.
If you look at the directed graph of the strongly connected components it is always a straight line.
For each strongly connected component we need to save only two arrays of size K (the one with the minimum power levels for each skill and the one with the maximum power levels).
Thus we can save the strongly connected components inside a map (the key for the map is a structure containing the two arrays and the size of the component).
In order to add a new vertex we need to use a lower_bound on the map and then iterate through the map mixing together the new connected components.
Div 2 C?? Are you kidding me??
He means Div.1 C.
I think so :p, Div 2 C is not a Graph Theory problem at all
Oh yeah, div1C
How did you bring connected components into picture Jefe ??
we add an edge from vertex a to vertex b if player a can beat player b in at least one game. Then the players that have a chance to win the game are the ones that can reach every node. Of course these nodes form a strongly connected component.
Okkay Got it !! Thanks
Answer is number of strongly connected component or what ???
Answer is the size of the initial connected component (they form a directed path)
n is 5×10^4 though. Won't it get TLE?
Jefe Sorry to disturb !!!! How would you solve for this one n = 3 k = 2 1 2 2 1 3 3
so In the first case, a single node is present ,then the second node comes and two directed edges are formed 1->2 and 2->1 . How do you get answer here ??
First the first node forms a SCC -> answer = 1.
After adding the second node, you have a SCC nodes 1 and 2 -> answer = 2.
The third node will form a SCC by itself, and this SCC is better than the previous SCC (they form a directed chain SCC{3} > SCC{1, 2}). The answer will be the size of the best SCC -> 1.
Thanks I got it . :)
I like the idea of that key structure.
You find a position of the first characteristic and then move up and down looking for min/max on the next ones (expanding the interval), correct?
And again I will fail C :( When do I will come in div1 :(
OMG It passed :p. Finally here I come div1 :D
I know that feeling :(
I'm dreaming about blue colored handle...
Huh, these were really hard B and C. How to properly solve B? I did something like binary exponentation of reductions (sequences when consecutive groups of same people are merged and when I see interval of length k of same numbers I throw it away). However when done naively these reducted sequences can grow a lot, so I kept only a big suffix and prefix of them, but I am not sure about correctness of the way I did it. On the beginning I tried to reduct initial sequence, then reduct result concatenated two times and consider some cases, but that seemed to be really prone to bugs.
I hope I haven't missed any edge cases, but basically what I did was:
can u please help me in my code for this problem I really tried hard for it and i just don't want that effort to be useless
http://codeforces.me/contest/879/submission/32374450
everything is explained .
Just curious.
Is it easy for you to get the idea from source code 31746290?
This is not a Div.1, it is Div.0... I spent a lot of time to solve 1B. Anyway, I need to go to sleep...
Noooo.. I screwed up on div2C! I submitted 30 sec before end of contest and got WA because i thought that x was <= 2047 and not 1023 :(
How to solve Div2 E or Div1 C ???
How to solve div 2c ?
From there, we can see that for each bit in a and b:
same method as mine but in the bit off / off case , I used & operation instead of using | and ^ ..
Any particular reason why you used | and ^ instead of just using & ?
Anyways, here's my solution if you are interested.
Short explanation : observe that 0 to 1023 means all numbers having 10 bits.. Also observe that all the & , | and ^ operations actually apply to INDIVIDUAL BITS rather than the full number... So keeping a = 1023 and b = 0 means all bits of 'a' are set to 1 and all bits of 0 are set to 0.
so accordingly check what happens to them AFTER applying all the 'n' operations, If no change ==> means the AND bit was '1' , or bit was '0' and xor bit was '0' and so on..,
my submission --> 31767545
i don't understand. please explain more. why 1023 and 0, what i can get from them after the n operations.
see, 1023 == (1 1 1 1..... 1) (10 times) and 0 == (0 0 0 ...........0) (10 times)
so basically we can treat 1023 and 0 as rather a SET of 10 bits..
now apply all the mentioned operations,
after applying if the a particular bit of 1023 remains 1 and that bit of 0 remains 0, this means that all those operations do NOT CHANGE THAT PARTICULAR BIT IN ANY NUMBER! Why? --> well that's because in every number that particular bit can be either 0 or 1 and no matter what that bit is , it wont change because we have tested it for both 1 and 0
Similarly there are 3 more cases , all the cases have the same reasoning , i.e. if 1 1023 bit changes but 0's bits do not change it means that whatever be the number that Bit has to be equal to zero,
apply same reasoning to get to the final answer!.. Hope this helps!
Thankyou.W hen i read your previous comment my mind was not registering the fact that BITS OPERATION apply to single bit, so i didnt understood the solution. so one day when i was working on something, suddenly my mind clicked and i was able to solve it. This was good problem.
How to solve Div2 D?
Is the Div.1 contest really of the difficulty of Div.1? I spent more than 1h 40min working on B and only resulted in 5 Wrong Answers on pretest.
It was hard, but i remember harder contests, for example http://codeforces.me/contest/704.
O(NQ) solution for problem D .
Ugly code, without any beautiful optimizations, but ... AC =)
solution for C: click
Thank you for 5 great problems!
btw, I got AC on E after contest by adding one character on my TLE code (I knew that could cause TLE, but my unconciousness omitted one character). and I got only A passed :(
I really liked this problemset although I'll get -170 :)
Tests for div1B are weak. Noam527 found a test, that breaks my AC solution:
4 3 3
1 1 2 1
http://codeforces.me/contest/878/submission/31762139
My solution outputs 6, while it should be 0.
It is very bad to provide a hard task with weak tests:
Challenge: div1D with k ≤ 1000.
Do you have a solution on mind or is it just your wishful thinking? Looks really hard
I think that my solution will work (except for input and sorting (the latter can be done in linear time))
Can you please explain your solution? I could not understand the code.
Let's suppose we have only one query of third type. Then we can maintain only the characteristic which we are asked for. Now let's do binary search on answer (there are only k possible answers), then we can maintain only one binary characteristic: is the real characteristic bigger than our bound (from binary search). Max/min on binary characteristic is equivalent to or/and.
Now we can do parallel binary search for all queries of the third type and do our operations using bitsets.
Complexity will be
Well,good problems today.
can anyone please explain Div 2 problem C logic ? thanks in advance :)
I failed test case #7 on problem C div 2.
Can somebody tell me what is wrong with my result?
Participant's output
Jury's answer
Checker comment wrong answer The participant's program isn't equivalent to the input
I passed this one with the same idea, grouping by operators:
Output
Answer
Checker Log ok Ok
Thanks in advance!
Just try any input, e.g. 0. With the input program: ((0 ^ 125) ^ 377) & 1019 = (125 ^ 377) & 1019 = 260 & 1019 = 256. With your program: (0 & 1019) ^ 260 = 0 ^ 260 = 260.
So you should see, the order of the operations matters.
Thanks!
Cheater Report:- ImNaman and kingside have cheated as you can see even variable names are same for problem A and B and slight change in variables of C.
When will be editorial published?
still waiting :p
Editorial!!?
Will there be any editorial? Thx :)
Why are the editorials so late?
Can Anyone Explain Div 2 Problem A?
Iterate through the array of s[i] and d[i] and keep updating the present day of meeting the current doctor.
To update the present day, if (presentDay < s[i]) presentDay = s[i]
Otherwise, find the smallest value of k (>=0) such that: presentDay < s[i] + k*d[i] and put presentDay = s[i] + k*d[i] for that value of k
The answer will be the presentDay for the last doctor in the array
Where is the editorial??
http://codeforces.me/blog/entry/55435
thank you
Hello, can someone tell me where can I find the editorial of this contest? Thanks.
http://codeforces.me/blog/entry/55435
In proB, why test 5 2 1 4 2 5 3. The output is 4? I think the output is 5? Can someone explain for me?
5 2
1 4 2 5 3
first win: 4 because (1 < 4).
4 2 5 3 1
the second win: 4 because (4 > 2).
Answer 4 (because 4 won two wins in a row).
5 2 2 1 3 4 5 this test why the power's winner is 5 ? I think answer is 3 ?
5 2
2 1 3 4 5
2 1 3 4 5 winner is 2
2 3 4 5 1 winner is 3
3 4 5 1 2 winner is 4
4 5 1 2 3 winner is 5
5 1 2 3 4 winner is 5
5 have two wins. It means answer is 5.
Where is Editorial?
http://codeforces.me/blog/entry/55435
I get WA in Div2 C because of additional space at the end of first line. I thought that Codeforces typically ignores additional spaces at the end of line.