Codeforces Round #639 Editorial

4 года назад, # ^ |

-6

For a given n:

t = floor( ( -1 + sqrt( 1 + 24*n ) ) / 6 )

then the tallest tower that can be built from n is : 2 + ( (t-1)*(3t+4) )/2

keep subtracting this from n and recalculating 't' and tallest tower as long as n > 1

→ Ответить

Sibin_Thomas

4 года назад, # ^ |

-9

Why did you not take t = floor( ( -1 — sqrt( 1 + 24*n ) ) / 6 )?

→ Ответить

4 года назад, # ^ |

← Rev. 2 →

-6

t cannot be negative, t represents the index of the sequence: 2 7 15 26 ... and floor to make sure that index doesn't point to a term > n

→ Ответить

ViratKohli

4 года назад, # ^ |

-10

How did you compe up with this formula?

→ Ответить

AQZZ

4 года назад, # ^ |

More practical method is to use the recurrence from the problem and let https://www.wolframalpha.com/ solve it for you so you get n(h) (number of blocks needed to build pyramid of height h). Then you can also let it solve for the inverse and floor it to get the maximum height h' you can build using n blocks. This works because the function is increasing. Then you just do n -= n(h'). And you repeat this while keeping count.

→ Ответить

n1colai

4 года назад, # ^ |

If you look closely you can observe that in every structure there are complete triangles on every level except for surface. The no. of triangles are 1,1+2,1+2+3,1+2+3+4,....so on. so for nth structure there will be n(n+1)/2 no. of triangles, hence required card should be 3*n*(n+1)/2. But we know that we have to subtract base level no. of cards, hence final formula will be (3*n*(n+1)/2)-n. after rearranging this we get (3n^2+n)/2. Now you can reverse calculate highest tower n by making it equal to given number and solving the quadratic eqn.

→ Ответить

harshitsoora

4 года назад, # ^ |

But this show TLE on 10^9 test case 4. I don't understand why this is happening.

→ Ответить

4 года назад, # ^ |

you need to change 24*n to 24LL*n.

→ Ответить

harshitsoora

4 года назад, # ^ |

Can you please elaborate upon how this works, what is the error in earlier choice It would be a great help

→ Ответить

4 года назад, # ^ |

Long in cpp has maximum value (2^31-1), so it's bad when n = 1e9 and 24*n is 1e10, it is leading to overflow. You should use long long for variables where you're not sure whether you might overflow using int/long.

→ Ответить

piddddgy

4 года назад, # ^ |

← Rev. 2 →

a much easier to understand formula is (trng(n)*3)-n where trng is the nth triangular number. Notice that there are 1, 3, 6, 10... triangles in the structure and each triangle requires 3 cards. Then we subtract n cards, as we do not need cards at the bottom.

→ Ответить

_pastor_

4 года назад, # ^ |

← Rev. 2 →

i know a better approach to find the formula

for a height h there will be 2*h no. of cards at the base there will be total of (h-1)*((h-1)+1)/2 no. of triangles now just run a loop till n<2 https://codeforces.com/contest/1345/submission/79162987 link to my submission

→ Ответить

shejibri

4 года назад, # |

+14

loosed +160 delta

→ Ответить

Ser_Manish

4 года назад, # |

The problem set was really nice, looking forward for more rounds from you.

→ Ответить

Codersabbir

4 года назад, # |

-8

I am totally confuse dev2 A question.... Plz somebody plzz help me....

→ Ответить

Chy_Chy

4 года назад, # ^ |

In this problem, when you take 2*3 grid you see that you can not solve that puzzle, therefore you can not solve similar grids which has higher dimensions than 2. That means, if either row or column is 1 it can be sokved and if both are 2 it can be solved. Otherwise not. I hope now you understand.
Sorry for my bad english..

→ Ответить

IYAS.A.S

4 года назад, # |

Really great round but I am sad for this nice problem became unrated.

→ Ответить

Swistakk

4 года назад, # |

+35

For F, I went with a much more natural approach to me, where for each position we have 4 variables $$$r_i, y_i, b_i, e_i$$$ (I hope their meaning is clear, e.g., $$$r_i=1$$$ if i-th position is red). YB operations etc are basically swapping variables. Since result of each mix operation is white if all colors occur with the same parity and a proper color if one of them has a different parity than the others two, each mix operations produces 2 equations modulo 2 corresponding to the difference between parities of some two colors. However we have a nasty condition that exactly one out of $$$r_i, y_i, b_i, e_i$$$ should be 1 that can't really be expressed modulo 2, which seems like a big problem. However, what happens if we put there an equation $$$r_i+y_i+b_i+e_i=1$$$? We can get a faulty solution where $$$3$$$ out of these bits are lit. BUT, this system of equations has a very peculiar property that for every $$$i$$$, every equations contains an even number of variables $$$r_i, y_i, b_i, e_i$$$, so if we flip all of them then this will still be a solution! Hence if 3 of these variables are true then we can change them so that 1 of them is true and if we do this for every $$$i$$$ where it is needed then we will get a solution of equation system corresponding to the valid coloring!

→ Ответить

Gassa

4 года назад, # |

+67

The setting of 1344C - Quantifier Question is very nice. Thank you for the problemset!

→ Ответить

cs234_shrey

4 года назад, # |

Can somebody explain div2C, I can't get my head around the proof ?

→ Ответить

4 года назад, # ^ |

+16

consider a subset of rooms, from room 0 to n-1. let n = 5. CASE 1 let's assume a0 = 0, a1 = 1, a2 = 2, a3 =3, a4 = 4. Now, the guest in room 0 will go to -> 0 + a0 = 0 similarly guest in room 1 will go to -> 1 + 1 = 2 room 2 -> 2 + 2 = 4; room 3 -> 3 + 3 = 6; room 4 -> 4 + 4 = 8;

room 5 -> 5 + 0 = 5; room 6 -> 6 + 1 = 7; room 7 -> 7 + 2 = 9; room 8 -> 8 + 3 = 11; room 9 -> 9 + 4 = 13; .... and so on.

No guests get the repeating room {explained later}

CASE 2 let's consider a0 = 5, a1 = 7, a2 = 5, a3 = 8, a4 = 6; for room 0 -> 0 + 5 = 5; room 1 -> 1 + 7 = 8; room 2 -> 2 + 5 = 7; room 3 -> 3 + 8 = 11; room 4 -> 4 + 6 = 10;

room 5 -> 5 + 5 = 10; {gets repeating room} ******

in both cases, we can observe an arithmetic progression is forming . after every n__

Now if we observe both the cases, we can see that if, for a particular value of 'i' b/w 0 to n-1 if there exists a j, such that aj + j lies in the arithmetic progression of (ai + i), it implies that there will be a collision. This is because, a time will come when becomes (aj + j),

for example in case 2,

for i = 0 we can see that ai = 5 and i = 0; so the first term of the arithmetic progression is ai + i = 5 + 0 = 5; now we'll check for j = 1 to n-1, whether there is such a j for which aj + j lies in the arithmetic progression of ai + i with difference = n; so for j = 4, aj = 6, and aj + j = 10; so aj + j clearly lies in the arithmetic progression of ai + i ( 5 + 1*5 = 5) {ai + i + (x-1)*n = xth;}

this way we have to check for every i, that, whether there is a number which is in ap with ai + i and diff = n; this will take O(n*n). To optimize it we can just check whether there are more than one such numbers such that (ai+i)% n == (aj+j) % n because ai + i + (x-1)*n = aj + j; taking modulo both sides we'll end up with (ai+i)% n == (aj+j) % n and hence O(n).

→ Ответить

cs234_shrey

4 года назад, # ^ |

Thanks a lot!! just one thing that arithmetic progression of n also means that one should also be a multiple of other. So we just need to check if the taking the mod of (i+a[i]) gives same value as any other index.

→ Ответить

4 года назад, # ^ |

← Rev. 3 →

suppose we take n =3, a0 = 0, a1 = 1, a2 = 2; room 0 -> 0 + 0 = 0

room 1 -> 1 + 1 = 2

room 2 -> 2 + 2 = 4

room 3 -> 3 + 0 = 3

room 4 -> 4 + 1 = 5

room 5 -> 5 + 2 = 7

room 6 -> 6 + 3 = 9 ........ and so on

therefore room0, room3, room6, room9.....are in ap

similarly, room1, room4, room7, room10 ..... are in ap

and room2, room5, room8 .... are in ap

if any of the rooms in 2nd and 3rd row in this example are common with any room in first row {means are present in ap of first row,} Collison will occur. similarly if any rooms in 3rd row are common with any room in second row {means they are present in ap of 2nd row.} Collison will take place.

→ Ответить

4 года назад, # ^ |

yes

→ Ответить

MasterMind

4 года назад, # ^ |

← Rev. 2 →

This comment is by moha.jain credit to him for the explanation. and I re-wrote it to make it more readable.

Consider a subset of rooms, from room $$$0$$$ to $$$n-1$$$. let $$$n = 5$$$.

CASE 1: let's assume $$$a_{0} = 0$$$ , $$$a_{1} = 1$$$, $$$a_{2} = 2$$$, $$$a_{3} = 3$$$, $$$a_{4} = 4$$$. Now, the guest in room $$$0$$$ will go to $$$0 + a_{0} = 0$$$ similarly guest in room $$$1$$$ will go to $$$1 + 1 = 2$$$ room $$$2$$$ go to $$$2 + 2 = 4$$$; room $$$3$$$ go to $$$3 + 3 = 6$$$; room $$$4$$$ go to $$$4 + 4 = 8$$$;

room $$$5$$$ go to $$$5 + 0 = 5$$$; room $$$6$$$ go to $$$6 + 1 = 7$$$; room $$$7$$$ go to $$$7 + 2 = 9$$$; room $$$8$$$ go to $$$8 + 3 = 11$$$; room $$$9$$$ go to $$$9 + 4 = 13$$$; .... and so on.

No guests get the repeating room explained later

CASE 2: let us consider $$$a_{0} = 5$$$, $$$a_{1} = 7$$$, $$$a_{2} = 5$$$, $$$a_{3} = 8$$$, $$$a_{4} = 6$$$; for room $$$0$$$ go to $$$0 + 5 = 5$$$; room $$$1$$$ go to $$$1 + 7 = 8$$$; room $$$2$$$ go to $$$2 + 5 = 7$$$; room $$$3$$$ go to $$$3 + 8 = 11$$$; room $$$4$$$ go to $$$4 + 6 = 10$$$;

room $$$5$$$ go to $$$5 + 5 = 10$$$; gets repeating room

In both cases, we can observe an arithmetic progression is forming . after every $$$n$$$

Now if we observe both the cases, we can see that if, for a particular value of $$$i$$$ b/w $$$0$$$ to $$$n-1$$$ if there exists $$$a_{j}$$$, such that $$$a_{j} + j$$$ lies in the arithmetic progression of ($$$a_{i} + i$$$), it implies that there will be a collision. This is because, a time will come when becomes ($$$a_{j} + j$$$).

For example in case 2:

for $$$i = 0$$$ we can see that $$$a_{i} = 5$$$ and $$$i = 0$$$; so the first term of the arithmetic progression is $$$a_{i} + i = 5 + 0 = 5$$$; now we will check for $$$j = 1$$$ to $$$n-1$$$, whether there is such $$$a_{j}$$$ for which $$$a_{j} + j$$$ lies in the arithmetic progression of $$$a_{i} + i$$$ with difference equals to $$$n$$$; so for $$$j = 4$$$, $$$a_{j} = 6$$$, and $$$a_{j} + j = 10$$$; so $$$a_{j} + j$$$ clearly lies in the arithmetic progression of

$$$a_{i} + i$$$ ($$$5 + 1 \times 5 = 10$$$) => $$$a_{i} + i + (x-1)\times n$$$ $$$=$$$ $$$xth$$$

this way we have to check for every $$$i$$$, that, whether there is a number which is in ap with $$$a_{i} + i$$$ and $$$diff = n$$$; this will take $$$O(n \times n)$$$. To optimize it we can just check whether there are more than one such numbers such that

$$$(a_{i}+i)$$$ $$$mod$$$ $$$n$$$ $$$\equiv$$$ $$$(a_{j}+j)$$$ $$$mod$$$ $$$n$$$

because $$$a_{i} + i + (x-1) \times n = a_{j} + j$$$; taking modulo both sides we'll end up with $$$(a_{i}+i)$$$ $$$mod$$$ $$$n$$$ $$$\equiv$$$ $$$(a_{j}+j)$$$ $$$mod$$$ $$$n$$$ and hence $$$O(n)$$$.

→ Ответить

NerfThis

4 года назад, # ^ |

if n = 5, in your case 2, does not room 0 goes to room 0 + a[0] % 5 = room 0 ? Why does guest in room 0 goes to room 5?

→ Ответить

MasterMind

4 года назад, # ^ |

I think you are missing that the mod operation is on the subscript and not on $$$a_{i}$$$

if $$$n = 5$$$, then guest $$$0$$$ would go to

$$$0 + a_{0 mod 5}$$$ $$$=$$$ $$$0 + a_{0}$$$ $$$=$$$ $$$0 + 5 = 5$$$

→ Ответить

NerfThis

4 года назад, # ^ |

Ahhh, I see.

→ Ответить

me17b016

4 года назад, # ^ |

A little typo in this line $$$a_{i} + i (5 + 1 \times 5 = 5)$$$.

It should be $$$a_{i} + i (5 + 1 \times 5 = 10)$$$.

→ Ответить

MasterMind

4 года назад, # ^ |

thanks fixed

→ Ответить

cgDude

4 года назад, # ^ |

I solved by your approach but getting the wrong answer. Can you please tell me where am I wrong? https://codeforces.com/contest/1344/submission/79319693

→ Ответить

4 года назад, # ^ |

you have to take into account the mod of negative number with n

a[i] = a[i] + i; a[i] = (a[i])%n; if(a[i]<0){a[i] = a[i] + n;}

→ Ответить

cgDude

4 года назад, # ^ |

still wrong

→ Ответить

4 года назад, # ^ |

int main() { int t;cin>>t;

while(t--)
{

long long int n;

cin>>n;

long long int a[n],i;

unordered_set<long long int>s;

for(i=0;i<n;i=i+1)

{cin>>a[i];a[i] = i + a[i];}

for(i=0;i<n;i=i+1)
{

    a[i] = a[i]%n;

    if(a[i]<0){a[i]=a[i]+n;}

    s.insert(a[i]);

}
    if(s.size()==n){cout<<"YES"<<endl;}

    else{cout<<"NO"<<endl;}

}

} *****hope this helps

→ Ответить

R0cket007

4 года назад, # ^ |

if(a[i]<0){a[i]=a[i]+n;} can you explain this step plz

→ Ответить

4 года назад, # ^ |

modulus of a negative number can be written as a %m = (a + m)%m example: -1 % 20 == (-1 + 20)%20; =19;

→ Ответить

Ravan_2070

4 года назад, # ^ |

Consider the number line divided into segments of size n i.e [-1*(n) -2 -1] [0 1 2 ...n-1] [n n+1 n+2...2*n — 1] so now when you add to i + a(imodn) each i converts to some j which will be a index of one of these segments definitely.. What i am trying to say is that.. For example 1)n==3 Consider applying shuffling operation of segment [0..2] and we have a1,a2,a3 such that after shuffling 0->3,1->7,2->11 now 3 is actually at 0th position in its segment [3,4,5] 7 at 1st in [6,7,8] and 11 at 2nd position in [9,10,11] so in this example above we can see that each element results into an unique positions ,whatever be the segment it settles

So for such kind of example always the answer is YES!!

But consider this example

2) n==3 and we have a1,a2,a3 such that 0->3,1->6,2->11 so now 11 is still the 2nd position but 3,6 both are ones at 0th position Therefore such array a will result in generation of elements in which no 1st position element is ever created but the 1st position elements get converted to 0th position So Vacancy will be definitely created.. So for such kind of example the answer is NO!! * HOPE YOU UNDERSTAND..

→ Ответить

parveen1981

3 года назад, # ^ |

← Rev. 3 →

I know it's late but I think this is easier (it might help someone)
We know that a collision occur if for some $$$0 \leq i,j \leq n-1 $$$ where $$$ i \neq j$$$, the following condition holds true
$$$ i + k_1n + a_i = j + k_2n + a_j$$$ because $$$x+yn \equiv x \mod n$$$ where $$$0 \leq x \leq n-1$$$
Now, $$$i+a_i-j-a_j = (k_2-k_1)n$$$
$$$ \implies i+a_i-j-a_j \equiv 0 \mod n$$$
$$$\implies i+a_i \equiv j+a_j \mod n$$$

→ Ответить

spunkyyogi

4 года назад, # |

Can anyone explain why all numbers being distinct will not affect values of k>n?

→ Ответить

heyBossCanIGetAnACPlease

4 года назад, # ^ |

k refers to any integer and not any index of the array

→ Ответить

spunkyyogi

4 года назад, # ^ |

As because the rooms were infinite, my question was whether rooms with k>n would collide with those with k<n. It's sorted now. Thanks BTW.

→ Ответить

Sochu

4 года назад, # |

Can someone explain C again?

The shuffle isn't k + a[k mod n]?

→ Ответить

4 года назад, # ^ |

-9

The shuffle is k + (a_k mod n). So, for example, if a_1 = 12 for n = 7, room 1 will go to room 1 + (12 mod 7) which is room 6. Room 8 will also go to 8 + (a_1 mod 7) since 8 = 1 mod 7, so room 8 will go to room 8 + (12 mod 7) which is room 13. In general, room 1 + kn will go to room 1 + kn + (a_1 mod 7) = 1 + kn + 5 = 6 + kn. Hope this was helpful.

→ Ответить

4 года назад, # ^ |

← Rev. 2 →

Oops, I made a slight error. It is actually k + a_(k mod n). So in the example I gave where a_1 = 12 and n = 7, room 1 goes to room 1 + a_(1 mod 7) = 1 + a_1 = 13, and room 8 goes to room 8 + a_(8 mod 7) = 8 + a_1 = 20, and in general room 1 + kn goes to room 1 + kn + a_((1 + kn) mod n) = kn + 1 + a_1 = kn + 13.

→ Ответить

Sochu

4 года назад, # ^ |

← Rev. 2 →

I think it is room 1 + kn + a_((1 + kn) mod n)

→ Ответить

4 года назад, # ^ |

Yes, that's what I meant :).

→ Ответить

Colossus20

4 года назад, # ^ |

Yes, but notice that he is taking $$$0 \leq i < n$$$ so we have $$$i$$$ $$$mod$$$ $$$n = i$$$. The same goes for $$$j$$$.

→ Ответить

Sochu

4 года назад, # ^ |

I know that, but that proof from the tutorial: i+ai≡j+aj(modn), why everything mod n ?

→ Ответить

Torenu

4 года назад, # |

-8

Solved 3 problems before round was announced to be unranked. Never started that good :(

→ Ответить

IngaleAnkur10

4 года назад, # ^ |

-8

Same with me. Solved A,B,C within 20 minutes. I had a significant increase in rating even if I hadn't solved any other problem.

→ Ответить

4 года назад, # ^ |

-8

same to me haha,long time to escape from the level 'pupil' qvq

→ Ответить

Black_Be4rD

4 года назад, # |

+11

The decision of making this round unrated is highly appreciable. Many of us waited to check if our solution was correct before solving a new one. Feeling sorry for the problem setter/s. He/they must have worked so hard but a bug ruined all. Hope mike will find a way through this.

→ Ответить

IngaleAnkur10

4 года назад, # |

Can someone explain E in simpler terms? The concept of topological sorting is confusing me here. I understood the part of the graph being acyclic, but didn't get what they did next.

→ Ответить

Svlad_Cjelli

4 года назад, # ^ |

+19

Topological sorting isn't needed in this problem. The idea is, look at the numbers from a_1 to a_N in order. When you get to an index k, how do we know if we can put an A there? It's only possible if a_k is "not comparable" to any other a_i where i<k. So my solution is whenever we process an index i, we do two dfs traversals — one to mark all indices j where a_i<a_j, and one to mark all j where a_j<a_i.

This way, when we get to a_k, we checked if it was marked in one of the two ways. If it was marked, we have to put an E at k. If it wasn't marked, we put an A. In either situation, we do the two traversals.

In order to keep track of this, I kept two "seen" arrays — one array to mark seen vertices when going "up" the graph, and one for going down. As a result the solution was very clean.

I also checked for cycles in the same traversal, but you don't need to do that if it's too confusing — you can do it in a separate pass.

→ Ответить

4 года назад, # ^ |

why we can not fill all cell with south pole question D/B Div2/Div1

→ Ответить

Svlad_Cjelli

4 года назад, # ^ |

I think you replied to the wrong comment. But to answer your question:

Your solution has to have the property that all white squares are unreachable. If you put south pole magnets everywhere, then every square will be reachable by a north pole magnet, which is bad.

→ Ответить

4 года назад, # ^ |

thanks for your reply i got my mistake . yes i replied to wrong comment because before this i asked two times and no one replied so i find random people who was online ,and u was the first one

→ Ответить

IngaleAnkur10

4 года назад, # ^ |

Thank you so much. That was a great explanation.

→ Ответить

engeneersaw

4 года назад, # |

Div 2 C

Example:

3 2 1

In the fourth test case, guests 0 and 1 are both assigned to room 3.

0 1

In the test case, guests 1 and 2 are both assigned to room 2.

Why we have guest 2? I see only 2 rooms — 0 and 1. If k=0 and n=2, k+a[k mod n]=0+a[0]=0, so guest 0 still sit in room 0. And other guest assigned to room 2. Where is my mistake?

→ Ответить

kvansh

4 года назад, # ^ |

Read the problem statement carefully. There are infinite rooms.

→ Ответить

engeneersaw

4 года назад, # ^ |

guests 1 and 2 are both assigned to room 2 It means, that we have 3 guests: a[0],a[1],a[2], but at the beginning we have only a[0] that will be assigned to room 0 and a[1] that will be assigned to room 2.

Each of the two guests has their own room so we must return YES, but in example true answer in NO,because extra 3rd guest are in room 2 with guest 1

→ Ответить

https://codeforces.com/contest/1345/submission/79197607

4 года назад, # ^ |

in fact,we can assume that we have infinite room,each room contain a guest at the beginning.(we could think that there are infinite guests as well},so once we use the constraint to re-organize the position,all of the guest (infinite of course) will change there position by k+a[k mod n].so the example is ok whatever

→ Ответить

arthurg

4 года назад, # |

Can someone help me in figuring out why Div2D test 50 fails? Seems like I'm counting connected components incorrectly, but I can't seem to figure it out.. .

→ Ответить

Sherrrkhann

4 года назад, # ^ |

try f.second+1 < m

→ Ответить

arthurg

4 года назад, # ^ |

Ahh thank you for that suggestion :D

→ Ответить

Believe

4 года назад, # |

In div2 E, let's say we add egde from j's->k's(in_degree[j's]++. Assuming resulting graph is acyclic then we can make those vertices as universal if their in_degree is equal to 0. Can someone tell me what's wrong with my logic? Below is the link to my code. https://codeforces.com/contest/1345/submission/79209006

→ Ответить

emorgan

4 года назад, # ^ |

+15

Suppose I have a graph with two nodes and an edge $$$2\to 1$$$. Node $$$2$$$ has indegree $$$0$$$, yet the statement $$$\exists x_1,\forall x_2, x_2 < x_1$$$ is false.

→ Ответить

Believe

4 года назад, # ^ |

Thanks,I didn't focused on order of xi's.

→ Ответить

dejongh93

4 года назад, # |

For Div2.C, I tried a (supposed) N^2 solution and it got accepted: https://codeforces.com/contest/1345/submission/79212988 I suppose it can be proved that it will never actually do so many iterations. Otherwise, maybe test cases are not strong enough.

→ Ответить

emorgan

4 года назад, # ^ |

← Rev. 3 →

+12

Hacked it with testcase:

1
200000
0 0 0 0 0 ...

→ Ответить

https://codeforces.com/contest/1345/submission/79218763

4 года назад, # ^ |

haha really

→ Ответить

parker0523

4 года назад, # |

Does anyone know why in div1C,the answer of the testcase below: 3 2 1 2 3 2 is 1 AEE ?

shouldn't it be 2 AEA???

→ Ответить

nishant403

4 года назад, # ^ |

The problem is that, x3 < x2 Now you have fixed x2, (As There exists x2 comes first in order) , so not all x3 holds x3 < x2.

A requirement for universality is that the variable is only comparable with larger-indexed variables. It is mentioned in the 2nd paragraph of editorial.

→ Ответить

parker0523

4 года назад, # ^ |

thanks and I missed that part of requirement XD

→ Ответить

_dobby_

4 года назад, # |

In the sol. for Div2E/1C, I don't understand this

For each variable, we can find the minimum index of a node comparable to it by doing DP in forward and reverse topological order.

Please explain this.

→ Ответить

nishant403

4 года назад, # ^ |

← Rev. 2 →

+15

The requirement for a variable x(i) to be universal is that, In the directed acyclic graph, No node x(j) with j < i can reach x(i) and x(i) also cant reach such x(j). In other words, all nodes reachable from x(i) and reachable to x(i) should have higher labels.

To check that, we do DP and find minimum below and minimum above in reversed graph.

→ Ответить

kumaraditya1999

4 года назад, # ^ |

← Rev. 2 →

Can you explain this testcase:

5 4

1 2

1 3

5 1

4 1

The correct answer is: AEEEE.

I can make x2 and x3 anything and set x1 as min(x2,x3), I can set x4 and x5 according to x1 , So won't the answer be 2 EAAEE. What am I missing here?

→ Ответить

nishant403

4 года назад, # ^ |

Problem Statement says :

Note that the order the variables appear in the statement is fixed. For example, if f(x1,x2):=(x1<x2) then you are not allowed to make x2 appear first and use the statement ∀x2,∃x1,x1<x2. If you assign Q1=∃ and Q2=∀, it will only be interpreted as ∃x1,∀x2,x1<x2.

→ Ответить

kumaraditya1999

4 года назад, # ^ |

Oh I see.Thanks a lot for this!!

→ Ответить

_dobby_

4 года назад, # ^ |

Can I rephrase it as

The element with the smallest index in every chain of the poset gets 'A' rest all 'E'?

→ Ответить

zucker42

4 года назад, # |

← Rev. 2 →

Dang, I really like Div2F. I had the right idea for it but didn't implement because I thought it was wrong and it was unrated anyways.

Great problems...too bad there were technical difficulties.

→ Ответить

Ashukv

4 года назад, # ^ |

Could you please explain the idea behind this question?

→ Ответить

zucker42

4 года назад, # ^ |

Which part of the tutorial don't you understand?

→ Ответить

jum.yip98

4 года назад, # |

← Rev. 2 →

Started well off however for some reason, for div2D my submission solves all the test cases correctly on my IDE however does not seem to even get the correct answer for the very first test case when I submit it to the online judge. Any help would be appreciated — cheers

→ Ответить

zucker42

4 года назад, # ^ |

← Rev. 4 →

I get two warnings when compiling that, both which might lead to undefined behavior (I got the answer 6 when running it on my computer). One is that size is ambiguous (size is a std function you included) and the second is that k isn't initialized. I compile with -Wall -Werror -Wpedantic (and I have it so Vim + YouCompleteMe highlights such errors).

→ Ответить

4 года назад, # |

← Rev. 2 →

can someone tell why is this not optimal solution Question D div 2

→ Ответить

4 года назад, # ^ |

please some one reply

→ Ответить

4 года назад, # ^ |

What's your meaning, The 3*3 grid is all colored white?

→ Ответить

4 года назад, # ^ |

that image is solution (according to me) of first sample test case

→ Ответить

4 года назад, # ^ |

This is wrong answer. Because it's not possible for a north magnet to occupy black cell after some sequence of operations from the initial placement.

→ Ответить

4 года назад, # ^ |

yup i got my mistake thanks

→ Ответить

ajayNegi

4 года назад, # ^ |

← Rev. 3 →

Why in the first place do we need to place north poles in the grid? Or did I missed something? Can't the minimum no. of north poles be 0 in all cases except -1?

→ Ответить

4 года назад, # ^ |

The 0 is a acceptable answer. We need minimum the number of North poles.

→ Ответить

laboba

4 года назад, # |

+10

Poor Monogon.But the problems are really great.Thanks!

→ Ответить

CUSTStein

4 года назад, # |

← Rev. 5 →

I think there is something wrong with the Div2 C for it's type. $$$(k+a_k){\bmod n}$$$ instead of $$$k+a_{k\bmod n}$$$

And does anybody tell me why k is in[0,n — 1]?

→ Ответить

4 года назад, # ^ |

actually k is included in R.because we have infinite room.once we reorganize the position,we are able to let the k pos guest move to k+a[k mod n] position

→ Ответить

CUSTStein

4 года назад, # ^ |

o,It's my fault. But I cannot understand this code

why need we mod n in (i + a[i] % n + n) % n; and why i in [0, n — 1]

→ Ответить

4 года назад, # ^ |

← Rev. 5 →

Let's divide the R into segments,each segment contain n elements;

We find that for each ith element,it transforms to the (i + a[i] % n + n) % n th in one segment;

if every i in [0,n-1] obey the rule -- each transformation make unique pos in those segment,then for each new position of element,it won't be the same place(not violate the rule the problem statement show)

→ Ответить

4 года назад, # ^ |

← Rev. 2 →

as for i in [0,n-1],we can make sure that the other segment(such as [n,2n-1])is also follow the rule

actually,the range of i we choose could be the set which contain n successive integer

→ Ответить

http://codeforces.com/contest/1345/submission/79207288

4 года назад, # |

I had the right idea for Div2 C. Not sure where my error is, I'm pretty sure this checks if all the rooms are distinct, and it works for almost all the test cases, but fails on a couple for some reason...

Any help would be appreciated.

→ Ответить

4 года назад, # ^ |

← Rev. 3 →

Fixed your code the number you module is negative,which may cause problems

→ Ответить

4 года назад, # ^ |

Thank you! That was in fact the problem. I fixed it by replacing the insert line with

toAdd += j; toAdd %= n; if(toAdd < 0) toAdd += n; a.insert(toAdd);

I'm still a little confused though, because I thought my conditional (toAdd + j < 0) ? ((toAdd + j) % n) + n : (toAdd + j) % n took care of negatives. I'm new to C++ so maybe I'm misunderstanding what that expression does or how the % operator works. How was it possible for my previous code to return a negative mod?

→ Ответить

lightseba

4 года назад, # ^ |

% doesn’t do the mathematical mod, it does remainder. you have to add in the modulus to get it to be the mathematical modulus.

→ Ответить

4 года назад, # ^ |

What do you mean by add in the modulus? Isn't n the modulus there? Sorry I'm a little new to programming lol.

→ Ответить

lightseba

4 года назад, # ^ |

The modulus is the number that you're "modding" by. It's like the divisor in division; when you do $$$15\ /\ 5$$$, you call $$$5$$$ the divisor.

What I mean by adding it in, is consider $$$-9\ \%\ 5$$$. The result of this expression in C++ is $$$-4$$$, but in math terms, what we want is $$$1 \equiv -9 \pmod{5}$$$. So what we can do, is when we can add $$$5$$$ to the original expression (that resulted in $$$-4$$$) to get what we want, which is $$$1$$$.

Basically, if you want to compute $$$a \pmod{b}$$$, where $$$a$$$ can be negative, you write ((a % b) + b) % b

→ Ответить

4 года назад, # ^ |

But the expression a % b only returns the wrong value if a is negative, right? So if I have the conditional (toAdd + j < 0) ? ((toAdd + j) % n) + n : (toAdd + j) % n it checks if a is negative (in this case a is toAdd + j), and returns the bolded part where I do in fact add n (the modulus). If it's not negative I don't need to add it, I think. I'm still slightly confused. But thanks for your help!

→ Ответить

4 года назад, # ^ |

← Rev. 2 →

Like this? 79238791.

I guess the problem is toAdd + j can't be negative, which makes the statements behind that meaningless.

→ Ответить

sarthak2024

4 года назад, # |

← Rev. 2 →

Div2E/Div1C:
WA on pretest 5 -
I tried my to make a directed graph and check for a cycle. If it is acyclic, if some vertex has non-zero indegree, I give it an E, else it has an A. What is wrong with this logic? https://codeforces.com/contest/1345/submission/79197644

→ Ответить

4 года назад, # ^ |

Check this out. Link

→ Ответить

tudouuuuu

4 года назад, # ^ |

I also WA on pretest5 in contest. When I look other's AC code, I am wonder about test 15. In my program I get

3
AEAEA

Look at pretest 3, and 1 2 is can be ignored. I wonder why test15's answer is like

2
AEAEE

→ Ответить

tudouuuuu

4 года назад, # ^ |

Well, now I know why. wwwwwwwwwwwwwwwww

→ Ответить

gaurav1903

4 года назад, # |

+10

So unfortunate that the contest had to be unrated. The problems felt good and interesting. Hope the problem gets fixed today

→ Ответить

Pie-Lie-Die

4 года назад, # |

In Div1B/ Div2D, why can't we fill all cells with South pole? Monogon

→ Ответить

4 года назад, # ^ |

yes i have the same question

→ Ответить

pandastic

4 года назад, # ^ |

← Rev. 2 →

We can put a south pole magnet in any black cell. Out of the white cells, we can only put south pole magnets at intersections of completely white rows with completely white columns. If a row (or column) contains at least one black cell and we put a south pole magnet in one of its white cells, then the south pole magnet will be able to pull a north pole magnet from the black cell to the white area at some point, since each black cell must be reachable by a north pole magnet by the problem requirement. While all white cells must be unreachable by north pole magnets in any possible sequence of moves.

→ Ответить

code0rider

4 года назад, # ^ |

Nicely explained!!

→ Ответить

ajayNegi

4 года назад, # ^ |

Why in the first place do we need to place north poles in the grid? Or did I missed something? Can't the minimum no. of north poles be 0 in all cases except -1?

→ Ответить

pandastic

4 года назад, # ^ |

Because every black cell must be reachable by a north pole magnet, it is rule #2 from the problem statement. So we need at least one north pole in each black connected component (area composed of adjacent black cells). The only case when 0 north pole magnets is the right solution is when the entire grid is white.

→ Ответить

ajayNegi

4 года назад, # ^ |

Thanx for responding. It was written that it is possible for the N pole to reach the black cell and not must, and that's why I had such doubt.

Don't you think the problem statement was a bit confusing in the way that it used possible instead of must there?

→ Ответить

plehem

4 года назад, # ^ |

-16

Such a shit statement. I fucking urge contest writers to learn some basic English before writing problems. Time wasters like this really annoys me.

→ Ответить

4 года назад, # ^ |

Because North pole can't occupy white cell, and North pole can reach the cell which be occupied by South pole if they are in same Column or Row.

→ Ответить

4 года назад, # ^ |

Consider this situation.

Spoiler

If you fill all cells with South pole and put a North pole in the centre cell, you cannot satisfy rule 3.

Actually pretest 2 is a good example and you should check it out.

→ Ответить

brickiq

4 года назад, # ^ |

because a sequence of operations must exist for every black cell such that it ends up being occupied by a north magnet

→ Ответить