Codeforces Round #443

6 лет назад, # |

+16

Why the delay?

→ Ответить

nileshjha19

6 лет назад, # ^ |

Mission 6000 :p

→ Ответить

6 лет назад, # ^ |

Mission accomplished. :P

→ Ответить

6 лет назад, # |

delayed))

→ Ответить

PinkRabbitAFO

6 лет назад, # |

Delayed again...

→ Ответить

ViciousCoder

6 лет назад, # |

Delays, delays, delays :P :P

→ Ответить

Sorryforpartyrocking

6 лет назад, # |

6000 reg only div2? Not bad :)

→ Ответить

misael

6 лет назад, # |

servidor is very slow today, hope the contest continue rated.

→ Ответить

rsFalse

6 лет назад, # |

+17

+10 min as usual

→ Ответить

pls_be_short

6 лет назад, # |

-12

for the writer,pls be short!

→ Ответить

6 лет назад, # |

Why test case 3 in div 2 C is 0? Is there no program? Thanks!

→ Ответить

Glebodin

6 лет назад, # ^ |

it's empty

→ Ответить

_S1MPLE_

6 лет назад, # ^ |

its special :p !!

→ Ответить

6 лет назад, # ^ |

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!

→ Ответить

egor.okhterov

6 лет назад, # ^ |

It's the number of operations that your new function does before returning the value.

For example, if k = 2:

int modify(int value)
{
   int value1 = value & 100;
   int value2 = value1 | 3;
   return value2;
}

If the k = 0, then you have the following function:

int modify(int value)
{
    return value;
}

→ Ответить

6 лет назад, # ^ |

Thanks!

→ Ответить

6 лет назад, # ^ |

How did you know it was empty?

→ Ответить

Sharon

6 лет назад, # |

-7

What is the hack for B?

→ Ответить

linhcooocaaa

6 лет назад, # ^ |

4 2 2 1 3 4

→ Ответить

JustInCase

6 лет назад, # ^ |

+21

When the winner is changed most of the people count the new number of wins to be 0 but it should be 1 :D

→ Ответить

kunal1234

6 лет назад, # ^ |

Failed on TestCase 33 due to this reason feels so stupid.

→ Ответить

dieumerci

6 лет назад, # ^ |

4 2 2 3 1 4

→ Ответить

Ahmed-

6 лет назад, # ^ |

← Rev. 2 →

4 2

1 3 2 4

→ Ответить

satyaki3794

6 лет назад, # |

← Rev. 2 →

How to solve Div-1 C and D?

→ Ответить

rajat1603

6 лет назад, # ^ |

+45

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 min_i and max_i 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.

→ Ответить

mouse_wireless

6 лет назад, # ^ |

← Rev. 2 →

"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

→ Ответить

ivan100sic

6 лет назад, # |

+129

Summary of my performance this round.

→ Ответить

fmota

6 лет назад, # |

← Rev. 3 →

Ignore ...

→ Ответить

rajat1603

6 лет назад, # |

+54

Why i prefer dynamic scoring

→ Ответить

doraemonrobocat

6 лет назад, # |

← Rev. 2 →

what's wrong with this 31762295 for div2 B??

→ Ответить

WhaleVomit

6 лет назад, # ^ |

vector.erase is O(n)

→ Ответить

6 лет назад, # |

+20

The problem C in Div. 2 was nice. Required a good bit thinking (atleast for me). My mind was blown...

→ Ответить

getSchwifty

6 лет назад, # |

How to solve div2 C ? Was it like taking Xor , and , or of all values and print in the same order. ?

→ Ответить

__B

6 лет назад, # ^ |

no that will not print the correct answer.

Try in this input:

|1 Take x as 2.

→ Ответить

getSchwifty

6 лет назад, # ^ |

Thanks , Then what was the algorithm behind this you constructed to solve ?

→ Ответить

filippos

6 лет назад, # ^ |

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? :)

→ Ответить

marcosvcloures

6 лет назад, # ^ |

← Rev. 2 →

a = 1023
b = 0

for each (op, val) in input:
    a = a op val
    b = b op val

From there, we can see that for each bit in a and b:

bit on / off: no operation;
bit on / on: or operation;
bit off / on: xor operation;
bit off / off: or and xor operation.

→ Ответить

stevie1024

6 лет назад, # ^ |

bit off / off: and 0 operation

→ Ответить

SarvagyaAgarwal

6 лет назад, # ^ |

-21

You can just do these 2 operations : AND (a ^ b) XOR b

→ Ответить

shubhiks1032

6 лет назад, # |

+11

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

→ Ответить

Flavius

6 лет назад, # ^ |

+11

oh...

→ Ответить

teamskiy

6 лет назад, # ^ |

sad(

→ Ответить

abx_2109

6 лет назад, # ^ |

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 :(

→ Ответить

eanacra

6 лет назад, # |

Hacked 3 solutions in the last 3 minutes... (my last hack was 3 seconds before the end) So tense!

→ Ответить

6 лет назад, # |

Как решать С Див. 2?

→ Ответить

zhussupov

6 лет назад, # ^ |

← Rev. 2 →

1) Нужно обратить внимание на следующее: Пусть изначальное число равно х, а первое действие — & a. Тогда если i-ый бит числа а равен 0, то i-ый бит результата тоже будет равен 0 вне зависимости от х. Аналогично если действие — | a, тогда если i-ый бит числа а равен 1, то i-ый бит результата тоже будет равен 1. Если действие — ^ a, то если i-ый бит числа a равен 1, то i-ый бит результата изменится на противоположное значение, иначе останется.

2) Таким образом для конечного числа мы можем узнать для каждого бита будет ли он равен 1, либо равен 0, либо противоположен изначальному соответствующему биту, либо не изменится вовсе.

3) Теперь составим числа ans1, ans2, ans3 следующим образом:

ans1: в двоичном представлении нулю равны те биты, в которых в конечном числе они равны нулю, в остальных — 1.

ans2: в двоичном представлении единичке равны те биты, в которых в конечном числе они равны единичке, в остальных — 0

ans3: в двоичном представлении единичке равны те биты, в которых в конечном числе они должны поменяться на противоположное значение, в остальных — 0.

Ответом будет:

& ans1

| ans2

^ ans3

→ Ответить

MaksymOboznyi

6 лет назад, # ^ |

Спасибо, но возник вопрос: под конечным значением в ans1, ans2, ans3 подразумевается конечное значение для какого числа?

→ Ответить

zhussupov

6 лет назад, # ^ |

Конечное число — это число, которое мы получим после применения всех n операций

→ Ответить

MaksymOboznyi

6 лет назад, # ^ |

Да. А к какому числу из диапазона от 0 до 1023? Или все равно?

→ Ответить

zhussupov

6 лет назад, # ^ |

Для любого. В этом то и вся суть.

→ Ответить

6 лет назад, # ^ |

Огромное спасибо!

→ Ответить

6 лет назад, # |

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.

→ Ответить

ilern

6 лет назад, # ^ |

Div 2 C?? Are you kidding me??

→ Ответить

Divyansh_19

6 лет назад, # ^ |

He means Div.1 C.

→ Ответить

ilern

6 лет назад, # ^ |

I think so :p, Div 2 C is not a Graph Theory problem at all

→ Ответить

6 лет назад, # ^ |

Oh yeah, div1C

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

How did you bring connected components into picture Jefe ??

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

Okkay Got it !! Thanks

→ Ответить

6 лет назад, # ^ |

Answer is number of strongly connected component or what ???

→ Ответить

6 лет назад, # ^ |

Answer is the size of the initial connected component (they form a directed path)

→ Ответить

Desperate.

6 лет назад, # ^ |

n is 5×10^4 though. Won't it get TLE?

→ Ответить

6 лет назад, # ^ |

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 ??

→ Ответить

Jakube

6 лет назад, # ^ |

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.

→ Ответить

http://codeforces.com/contest/879/submission/32374450

6 лет назад, # ^ |

Thanks I got it . :)

→ Ответить

P___

6 лет назад, # ^ |

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?

→ Ответить

8shubham

6 лет назад, # |

← Rev. 2 →

+11

And again I will fail C :( When do I will come in div1 :(

OMG It passed :p. Finally here I come div1 :D

→ Ответить

tantam75

6 лет назад, # ^ |

I know that feeling :(

→ Ответить

bktl1love

6 лет назад, # ^ |

I'm dreaming about blue colored handle...

→ Ответить

Swistakk

6 лет назад, # |

+86

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.

→ Ответить

voover

6 лет назад, # ^ |

← Rev. 2 →

+34

I hope I haven't missed any edge cases, but basically what I did was:

Preprocess the single bus to remove as many teams as possible
Process all the buses together, removing teams that came from the two consecutive buses
At this point, if the "middle" buses (other than first and last) have contestants from more than one city, we're done. Otherwise, we take the prefix from the first bus, the number of participants from the middle buses, suffix from the last bus and do stuff in the naive way.

→ Ответить

Jhin

6 лет назад, # ^ |

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

everything is explained .

→ Ответить

egor.okhterov

6 лет назад, # ^ |

-26

Just curious.
Is it easy for you to get the idea from source code 31746290?

→ Ответить

Binary-grid-colouring

6 лет назад, # |

+49

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...

→ Ответить

Fred_Flintstone

6 лет назад, # |

-7

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 :(

→ Ответить

O(NQ) solution for problem D .

6 лет назад, # |

← Rev. 2 →

How to solve Div2 E or Div1 C ???

→ Ответить

linhcooocaaa

6 лет назад, # |

How to solve div 2c ?

→ Ответить

marcosvcloures

6 лет назад, # ^ |

a = 1023
b = 0

for each (op, val) in input:
    a = a op val
    b = b op val

From there, we can see that for each bit in a and b:

bit on / off: no operation;
bit on / on: or operation;
bit off / on: xor operation;
bit off / off: or and xor operation.

→ Ответить

final_tsu

6 лет назад, # ^ |

+11

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

→ Ответить

attiw

6 лет назад, # ^ |

i don't understand. please explain more. why 1023 and 0, what i can get from them after the n operations.

→ Ответить

final_tsu

6 лет назад, # ^ |

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!

→ Ответить

attiw

6 лет назад, # ^ |

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.

→ Ответить

anonymousbuggy

6 лет назад, # |

How to solve Div2 D?

→ Ответить

arbyzexe

6 лет назад, # |

Здравствуйте , почему в 33 тесте в задаче B div2 ответ 4?

→ Ответить

igorpastukh

6 лет назад, # ^ |

Сначала играют игрок с силой 1 и игрок с силой 4, так как 4 > 1 то игрок силой 4 побеждает в партии и получает первую победу, игрок с силой 1 уходит в конец очереди. Далее играют 4 и 3, 4 > 3 так что игрок с силой 4 получает вторую победу подряд и становится победителем.

→ Ответить

Marco_L_T

6 лет назад, # |

+17

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.

→ Ответить

Anadi

6 лет назад, # ^ |

← Rev. 2 →

It was hard, but i remember harder contests, for example http://codeforces.com/contest/704.

→ Ответить

MrDindows

6 лет назад, # |

Ugly code, without any beautiful optimizations, but ... AC =)

→ Ответить

adamant

6 лет назад, # ^ |

$\text{[math]}$ solution for C: click

→ Ответить

ainta

6 лет назад, # |

Thank you for Great 5 problems!

btw, After contest I accepted E by add one character on my TLE code (And I knew that could cause TLE, but my unconsciousness omitted that character). and I passed only A :(

I really liked this problemset although I'll get -170 :) I hope future codeforces round keep this quality.

→ Ответить

ainta

6 лет назад, # |

+68

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 :)

→ Ответить

Wild_Hamster

6 лет назад, # |

+56

Tests for div1B are weak. Noam527 found a test, that breaks my AC solution:

4 3 3

1 1 2 1

http://codeforces.com/contest/878/submission/31762139

My solution outputs 6, while it should be 0.

→ Ответить

P___

6 лет назад, # ^ |

It is very bad to provide a hard task with weak tests:

Not many people will solve it and they would be upset that other guys have accepted incorrect solutions.
Those, who solved it correctly, would be upset that some other folks have accepted incorrect solutions, lowering their achievement.
Those who have accepted incorrect solutions would also be upset, as this gives them no satisfaction and unjustified points. (Not 100% sure about that though.)

→ Ответить

iMurat

6 лет назад, # |

← Rev. 2 →

Долго же я думал, где память подводит...

→ Ответить

Um_nik

6 лет назад, # |

+38

Challenge: div1D with k ≤ 1000.

→ Ответить

Swistakk

6 лет назад, # ^ |

Do you have a solution on mind or is it just your wishful thinking? Looks really hard

→ Ответить

Um_nik

6 лет назад, # ^ |

I think that my solution will work (except for input and sorting (the latter can be done in linear time))

→ Ответить

satyaki3794

6 лет назад, # ^ |

Can you please explain your solution? I could not understand the code.

→ Ответить

Um_nik

6 лет назад, # ^ |

+28

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 $\text{[math]}$

→ Ответить

Weakness

6 лет назад, # |

Well,good problems today.

→ Ответить

fight_back

6 лет назад, # |

can anyone please explain Div 2 problem C logic ? thanks in advance :)

→ Ответить

6 лет назад, # |

← Rev. 2 →

I failed test case #7 on problem C div 2.

Can somebody tell me what is wrong with my result?

Participant's output

2
& 1019
^ 260

Jury's answer

2
| 4
^ 260

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

2
& 242
^ 1008

Answer

2
| 781
^ 253

Checker Log ok Ok

Thanks in advance!

→ Ответить

Jakube

6 лет назад, # ^ |

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.

→ Ответить

Jakube

6 лет назад, # ^ |

So you should see, the order of the operations matters.

→ Ответить

6 лет назад, # ^ |

Thanks!

→ Ответить

rand0m_ng

6 лет назад, # |

← Rev. 2 →

+25

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.

→ Ответить