Codeforces Round #176

12 years ago, # ^ |

← Rev. 2 →

+39

I totally agree.I'm excited because this round is at 12.00MSK.We Chinese coders don't have to stay up at 23.30(Chinse Time) to participate.At first I thought this round is by a Chinese or Janpanese coder,but it seems I'm wrong.Thank you tunyash for this round at such great time!

I think,if Codeforces can have variable contest times like Topcoder,more coders will participate and Codeforces will become better.It is necessary to do so if Codeforces is to overtake Topcoder and become the first largest online programming competition site.

→ Reply

jiejie

12 years ago, # ^ |

totally agree ^_^

→ Reply

michaelalan

12 years ago, # ^ |

I quite agree with this view.

→ Reply

dc.

12 years ago, # ^ |

← Rev. 2 →

agree too

→ Reply

nikalosaberidze

12 years ago, # |

:(((( at this day, tomorrow i have maths olympics :((( it begins at 10 o'clock and end at 2 o'clock :((((

→ Reply

jiejie

12 years ago, # |

I like this starting time of the contest! Hope the starting time will be variant,(not limited to 7:30pm in Russia) so that more US or Chinese coders will attend the contest.

→ Reply

12 years ago, # |

-9

Will points distribution be standard or dynamic?

→ Reply

PAP

12 years ago, # |

last contest was great.I hope it will be great too

→ Reply

kavishrox

12 years ago, # |

I hope for a more organized editorial this time ... Guys take 1 day but give us good editorials .

→ Reply

MehrdadM

12 years ago, # |

-8

As you can see many people couldn't participate this contest ... It might be good for some countries but it's not for most ...

→ Reply

12 years ago, # ^ |

+22

I mean variable contest times.I'm not suggesting we always have contest at 12.00MSK,there's no doubt we need 19.30MSK contest time.For example,I suggest 30% contest set at morning of MSK Time.

→ Reply

MehrdadM

12 years ago, # ^ |

-9

perhaps that's much better idea ...

→ Reply

MDantas

12 years ago, # ^ |

← Rev. 2 →

As lsmll said, it should be good to everyone, so it's fair enough to variable the time so anyone will have a chance to participate. It's 5 A.M here in Brazil but i'm still gonna participate even though this time I really should be sleeping.

→ Reply

kphmd

12 years ago, # |

-39

Test photo.

→ Reply

E_star

12 years ago, # |

good for Chinese users.

→ Reply

AKGMA

12 years ago, # |

+16

By the way, past tense of "read" is "read", not "readed".

→ Reply

AlimA

12 years ago, # ^ |

-13

Nice comment ;)

→ Reply

SeyedParsa

12 years ago, # |

+11

My first contest in travel! Good luck!

→ Reply

EasyHacking

12 years ago, # |

Time limit for Div2 B is too long :( even brute force from k to 1 can pass :(

Got an Unsuccessful Hacking Attempt when trying to hacking one of those brute force solution :(

→ Reply

Killever

12 years ago, # ^ |

can you give me the link of this solution i think brute force will get TLE

→ Reply

OmarEl-Mohandes

12 years ago, # ^ |

Here is one .. Actually it's kinda weird O.o , I implemented this solution in the practice and got TLE , but when I tried mikhail's code got AC .. I think it depend on the optimizer somehow!

→ Reply

Killever

12 years ago, # ^ |

same to me got TLE :D with same solution

→ Reply

latvian

12 years ago, # ^ |

The reason for TLE in your case is, if I'm not mistaken, the use of long long in the line for (ll i = k - 1; i >= 2; i--) { whereas the AC solution uses int for i. As a long long takes up more space in the memory in comparison with integer, it also takes longer to perform calculations with it (here: 'i--'). In this case it makes the difference between TLE and AC.

→ Reply

OmarEl-Mohandes

12 years ago, # ^ |

Yes you are right about this .. But I think in general the intended solution is binary search , and the brute force should't pass.

→ Reply

12 years ago, # ^ |

You know, there is an O(1) algorithm (as opposed to the $\text{[math]}$ algorithm of binary search), if you want to do some math. My submission, for example, is the implementation of the result: 3390910

→ Reply

dj3500

12 years ago, # ^ |

+10

Is sqrt really O(1)? I guess you could argue it's really fast, but actually it uses binary search (which is O(log k), not O(sqrt(k))).

→ Reply

http://codeforces.me/contest/287/submission/3388316

12 years ago, # ^ |

Square root is O(log k)? I have always assumed that it's (along with the four arithmetic operations) constant. My bad. Thanks for clearing it up!

Also, yeah, I meant O(log k) for binary search. I must have been in a hurry to type O(sqrt k) instead.

→ Reply

Sklyack

12 years ago, # ^ |

I think the sqrt function calculates the square root with fixed relative error, so it's O(1).

→ Reply

pobelter

12 years ago, # ^ |

Here is a c++ implementation:3396062.

→ Reply

NikitaPogodin

12 years ago, # ^ |

→ Reply

kvtoraman

12 years ago, # ^ |

-6

Even this Solution passes. Time:2000 ms :SS

→ Reply

Rubanenko

12 years ago, # |

+14

Those who like permutations should be quite successful this time :)

→ Reply

Kianoosh

12 years ago, # |

+34

wow! All System Testing was only 4 minutes!!! Thanks for this great testing!!

→ Reply

JuanMata

12 years ago, # ^ |

probably because there were fewer participants than usual....i myself didn't participate as it was at a different time and i forgot about it...

→ Reply

HosseinYousefi

12 years ago, # ^ |

I agree with you, The time of the contest was good but I forgot it too!

→ Reply

_toothless_

12 years ago, # |

+15

Systest complete within just 2 refreshes :D

→ Reply

kinpa200296

12 years ago, # |

+34

Fast system test... Great!!!!

→ Reply

12 years ago, # |

← Rev. 3 →

To those who solved div1 A quickly e.g. within 20 minutes, how did you observe the trick(when n%4>1 return -1)? Thanks.

→ Reply

Rubanenko

12 years ago, # ^ |

I think writing backtracking may be useful here.

→ Reply

michaelalan

12 years ago, # ^ |

Use next_permutation to do brute-force first.

→ Reply

12 years ago, # ^ |

With this method, did you manage to quickly find the pattern?

→ Reply

michaelalan

12 years ago, # ^ |

Of course, we can use this method to find all solutions (n <= 13) within a minute. And the pattern is very clear. Try it.

→ Reply

12 years ago, # ^ |

+28

Well I didn't solve it within 20 minutes (and I'm div 2 anyway), but I suppose it's pretty simple:

Suppose f(i) = p_i. We have f(f(i)) = n + 1 - i, so f(f(f(f(i)))) = i. So the permutation is effectively cycles of 4, 2, 1. However, there can be no cycle of 2 (otherwise f(f(i)) = i ≠ n + 1 - i if $\text{[math]}$ , and if $\text{[math]}$ , then it's a cycle of 1), and the only cycle of 1 can only be done if $\text{[math]}$ , so there is at most one cycle of 1. Hence everything is in cycles of 4 except for possibly one element. This means $\text{[math]}$ or $\text{[math]}$ .

When in the contest, I visualized it by an n × n board where you put a piece on row i and column j if p_i = j, and noticing that everything are the vertices of squares except for probably the middle element.

→ Reply

12 years ago, # ^ |

← Rev. 2 →

This is a brilliant idea. However, I still have two questions.

What's the meaning of the cycle? Seems like some kind of abstract algebraic construct like group?
I don't understand your last sentence above(i.e. and noticing...), can you clarify it?

→ Reply

12 years ago, # ^ |

← Rev. 3 →

+12

First question:

Let's see a permutation 2, 3, 1, 4, 5. Note that p₁ = 2, p₂ = 3, p₃ = 1. So from 1, we can get to 2, then to 3, then to 1 again, and it repeats forever. So (1, 2, 3) is a cycle, of period (or you can say "size") 3. p₄ = 4, so (4) forms a cycle of period 1. Also note that we can multiply the period of any cycle by simply extending it: (1, 2, 3, 1, 2, 3) forms a "cycle" of period 2 × 3 = 6. I'll refer to a cycle with the smallest period (it cannot be broken into cycles) to be a "proper cycle".

If f(f(f(f(i)))) = i, then i must belong in a cycle of period 4, or in other words, a proper cycle whose period is a divisor of 4, hence why I can deduce that there can only be (proper) cycles of period 4,2,1. If the problem has been made such that f⁽⁶⁾(i) = i (6 iterations of f), I'd look for proper cycles of period 6,3,2,1.

Second question:

See the given permutation 2, 4, 1, 3 in the test case and what I made in my scratch paper:

.O..
...O
O...
..O.

As you can see, I put a piece (O) in row 1, column 2, indicating that p₁ = 2. Another one in row 2, column 4: p₂ = 4.

After making this, I noticed that everything is vertices of squares except for probably the middle piece (if there is any).

→ Reply

12 years ago, # ^ |

← Rev. 2 →

Elegant explanation, thanks.

I also have an observation, the correct lucky permutation is some sort of self-descriptive, taking n = 4 for instance, the answer is 2 4 1 3, the 2nd(value) element is the 1st(index) largest, the 4th element is the 2nd largest, the 1st element is the 3rd largest, the 3rd element is the 4th largest.

But I still don't know the meaning of "everything is vertices of squares", which squares?

→ Reply

12 years ago, # ^ |

Well, you can see that the four pieces in the above grid are vertices of a square, tilted a bit clockwise. Another example for n = 9:

.A.......
........A
...B.....
......B..
....O....
..B......
.....B...
A........
.......A.

Observe that A's make a square, and so are B's.

→ Reply

12 years ago, # ^ |

I finally understand. It's just a visual way describing the cycle of size 4 phenomenon. However, it's more precise to use the term "parallelogram" instead of square, isn't it:)

→ Reply

12 years ago, # ^ |

Actually you'll find that all the parallelograms will be squares (try to prove it :) ), but you can use "parallelogram" too if you prefer. Yes, it's my visual way of describing a cycle of period 4.

→ Reply

12 years ago, # ^ |

"I also have an observation, the correct lucky permutation is some sort of self-descriptive, taking n = 4 for instance, the answer is 2 4 1 3, the 2nd(value) element is the 1st(index) largest, the 4th element is the 2nd largest, the 1st element is the 3rd largest, the 3rd element is the 4th largest."

Of course. The p_i-th element is p_{p_i}, which by condition is equal to n + 1 - i. It is obviously the i-th largest element.

→ Reply

Endagorion

12 years ago, # ^ |

+33

Number of inversions in a square of a permutation is even, and number of inversions in permutation (N, N — 1, ... , 1) is N(N — 1)/2. It is clearly odd for N = 4k + 2 or 4k + 3.

→ Reply

12 years ago, # ^ |

That's correct. But could you explain the reason using no. of inversions to judge? I don't figure out the connection.

→ Reply

Endagorion

12 years ago, # ^ |

I don't quite figure what is the question about. If a permutation has an odd number of inversions, it can't be a square of any permutation. Therefore for N = 4k + 2, 3 answer doesn't exist.

→ Reply

12 years ago, # ^ |

Actually I don't understand what "square of a permutation" means.

→ Reply

Endagorion

12 years ago, # ^ |

A permutation applied twice consequently, like p_{p_i} in the problem statement.

→ Reply

12 years ago, # ^ |

Thanks, I got it.

→ Reply

12 years ago, # ^ |

← Rev. 2 →

The square of a permutation p is the permutation p_p; that is, if originally the permutation p has p_i = j, p_j = k, then the square of p (which I denote q) has q_i = p_{p_i} = p_j = k.

For example, if p = (2, 4, 1, 3), its square q is:

q₁ = p_p₁ = p₂ = 4

q₂ = p_p₂ = p₄ = 3

q₃ = p_p₃ = p₁ = 2

q₄ = p_p₄ = p₃ = 1

I assume that you already know "inversion". The square of any permutation has the property that the number of inversions in it is even. Meanwhile, by the condition of the problem, the square of the sought permutation is equal to the reverse identity permutation (n, n - 1, ..., 2, 1), which has an odd number of inversions for $\text{[math]}$ or $\text{[math]}$ , so they certainly can't be equal. So there doesn't exist any permutation whose square is the reverse identity permutation if $\text{[math]}$ or $\text{[math]}$ .

(EDIT: I keep making long comments and getting "ninja-ed" by people -_- But who cares.)

→ Reply

12 years ago, # ^ |

It's clear. All understood except "the square of the sought permutation is equal to the reverse identity permutation (n, n - 1, ..., 2, 1)", the reason?

→ Reply

12 years ago, # ^ |

Because the problem says that p_{p_i} = n + 1 - i.

If we expand this for all i, we get that (p_p₁, p_p₂, p_p₃, ..., p_{p_n}) = (n, n - 1, n - 2, ..., 1); in other words, the square of p is the reverse identity permutation.

→ Reply

12 years ago, # ^ |

← Rev. 2 →

About the parity of square of permutation, is there any proof? Given a permutation, how to decide whether it can be a square of some permutation?

→ Reply

12 years ago, # ^ |

That's the thing. I only recall that it is an established theorem, but I forgot the proof. Searching in Wikipedia also yields no result (although I think I saw the theorem in Wikipedia).

...Ah ya, here it is. I rephrase the (trivialized in Wikipedia) proof:

A permutation can be described by a number of adjacent-element transpositions. For example, (2, 4, 1, 3) can be described by (3, 4), (1, 2), (2, 3):

From (1, 2, 3, 4), we transpose elements on indices 3 and 4: (1, 2, 4, 3).

We then transpose elements on indices 1 and 2: (2, 1, 4, 3).

We finally transpose elements on indices 2 and 3: (2, 4, 1, 3).

To prove that we can always do so, it's simple: Just build the permutation we're going to make from the end (or from the front). The above sequence uses this algorithm: It constructs the permutation by first moving 3 to the end (as it's the last element), then 1 to the second-to-last index, and so on. (It's just lucky that after we move the 1, the permutation has been built already.)

Now, we note that the number of inversions changes by 1 for every adjacent-element transposition we made, so the parity of the number of inversions is equal to the parity of the number of adjacent-element transpositions we made. So, the parity of a permutation is equal to the parity of the number of adjacent-element transpositions. (This number may vary by simply adding something like (1, 2), (1, 2) as many times as you like, but the parity of the permutation always remain the same.)

Now, the composition of two permutations is just the product of their transpositions; in other words, the parity of the composition is equal to the sum of the parities of the two permutations used to build the composition.

Now, recall that the sum of two equal parities (even+even or odd+odd) is always even, and the square of a permutation is the composition of a permutation with itself. It's obvious that the parity of a permutation is equal to the parity of the permutation itself, so its square, which is the composition of the permutation and itself, must be even (as it's the sum of two equal parities).

I'm not sure how to determine whether a permutation is a square of another permutation or not though. I originally suspected that all even permutations are squares of some permutations, but (2, 1, 4, 3) doesn't satisfy it, so I don't know.

→ Reply

12 years ago, # ^ |

Oops, I got it now. Because P(P(i)) = n-i+1, so applying P(P(*)) on 1 through n, the result is the reversing sequence (n,n-1,...1). Thank you for the reply.

→ Reply

voover

12 years ago, # ^ |

Each of the elements, for which i != n -i + 1, needs to be in the cycle of size exactly 4. So we need to partition all elements (or all but one) into such cycles.

→ Reply

12 years ago, # ^ |

Yes. My concern is how to prove that conclusion. chaotic_iak's approach seems nice.

→ Reply

iroro

12 years ago, # ^ |

I just didn't prove anything and submitted it on 10th minute :) My prove was like «can it be that there won't be any 2 (mod 4) or 3 (mod 4) tests in pretests? :)»

(Disclaimer: I use this only on contests)

→ Reply

12 years ago, # ^ |

Quite brave action:P

→ Reply

kphmd

12 years ago, # ^ |

eg. 5

1 -> ? -> 5
2 -> ? -> 4
3 -> ? -> 3
4 -> ? -> 2
5 -> ? -> 1

Case1:

1 -> ? -> 5 -> ? -> 1 2 -> ? -> 4 -> ? -> 2

merge above

1 -> 2 -> 5 -> 4 -> 1

Case2:

3 -> 3 -> 3

→ Reply

flashmt

12 years ago, # |

← Rev. 2 →

+19

It seems that m = n in all pretests of D. That may explain for some WA on test 7 I think.

→ Reply

tmt514

12 years ago, # ^ |

I fell into this trap ._./

→ Reply

MDantas

12 years ago, # |

← Rev. 2 →

+31

Nicely done problem setters, that was an absolutely amazing contest. It was worth staying up all night.

→ Reply

caustique

12 years ago, # |

+81

Congratulations to al13n! 2 victories in a row seems impossible if you're not Petr or tourist but he did it!

→ Reply

al13n

12 years ago, # ^ |

+81

Thanks! I have no idea how it is possible O_O.

→ Reply

MinakoKojima

12 years ago, # ^ |

+30

New IGM ? ..

→ Reply

YuukaKazami

12 years ago, # ^ |

+34

Congratulations!

You are really amazing :)

→ Reply

cup_of_tea

12 years ago, # |

-8

Div 1 B can be solved by the naive algorithm...

→ Reply

nathanajah

12 years ago, # ^ |

I think it's not so naive, you need to think how to do the cycle, without moving too much numbers.

→ Reply

cup_of_tea

12 years ago, # ^ |

Yes, but I was waiting something much harder. Same for the third problem.

→ Reply

kvtoraman

12 years ago, # ^ |

← Rev. 2 →

But this Solution passes :S

→ Reply

nathanajah

12 years ago, # ^ |

That's B div 2 :S

→ Reply

dhm

12 years ago, # |

+14

This contest was great! nice problems !

→ Reply

cplayer

12 years ago, # |

Div1 B can be solved by Brute-Force?

→ Reply

Eurekash

12 years ago, # ^ |

YES

→ Reply

Flawless

12 years ago, # |

Question could have been little more clear.. at last i figured.. !!

→ Reply

phantom11

12 years ago, # |

ACRush was in my room today and he became WARush today!!!

→ Reply

k0st1a

12 years ago, # ^ |

what does that mean ?

→ Reply

logic_max

12 years ago, # ^ |

His 4 solutions failed system tests.

→ Reply

jonathanirvings

12 years ago, # ^ |

← Rev. 2 →

not really. two of his solutions are TLE :)

→ Reply

olimpo

12 years ago, # |

DIV 1 problem C TLE for using cin...

→ Reply

shervinkh

12 years ago, # ^ |

You should use cin with ios_base::sync_with_stdio(false);

→ Reply

ikbal

12 years ago, # ^ |

why " ios_base::sync_with_stdio(false) " is makes cin fast ?

→ Reply

Quelloquialism

12 years ago, # ^ |

This link explains that if this flag is true, it maintains the stream state in both cstdio and iostream so you can mix scanf/cin calls (or printf/cout). Turning it off means cin won't advance stdin, so it does less work to read the input.

I failed the same problem as olimpo because of being slow with input, but it's nice to discover something new like this...thanks, shervinkh!

→ Reply

shervinkh

12 years ago, # ^ |

← Rev. 3 →

In default case, cin and cout don't use buffering. This behaviour enables programmer to use scanf, printf and cin, cout in a program simultaneously. Using ios_base::sync_with_stdio(false) tells cin, cout that you don't want to use scanf, printf with cin, cout. So cin, cout use smart buffering with lots of speed up (more efficient than scanf, printf). I think the latter case should be default. but its the decision of C++'s creators.(may be because of ability to use cin, cout in old c programs that use scanf, printf). for large inputs and outputs (1e5 or 1e6 or more words) that is usual in algorithmic contest program buffered input and unbuffered input differ a lot in the speed. so in every algorthmic contest program it is recommended to use that call in the beginning of the program.

EDIT: It seems that while i was writing this, Quelloquialism has written the answer.

→ Reply

martinezgjuan

12 years ago, # |

Div2 C says "any integer i" meets the condition, not "every" or "all". I thing it's not even ambiguous, I did the wrong algorithm because of that :s

→ Reply

daidailanlan

12 years ago, # |

← Rev. 2 →

Nice Contest! For 286A - Lucky Permutation, I'm quite interesting on how to prove that there's no solution when n % 4 equals 2 or 3.

→ Reply

shervinkh

12 years ago, # ^ |

If you draw Permutation Graph You'll see that every cycle should be of length 1 or 4. so we couldn't have 4k + 2 or 4k + 3 nodes.

→ Reply

daidailanlan

12 years ago, # ^ |

Nice! I got it! Thank you so much.

→ Reply

Martin

12 years ago, # |

+58

!!!!!!!!!!!!!!!!!!!!!!!! The problem D has n, m to read, but read m variables next and read n variables next. The pretest do not contain the situation when n is not equal to m... TAT TAT TAT

→ Reply

tunyash

12 years ago, # ^ |

-6

I'm sorry, I didn't noticed that. My fail.

→ Reply

hex539

12 years ago, # |

← Rev. 4 →

+16

The input format for 286D - Tourists's is a bit strange - {#queries, #events, events, queries} instead of the more usual {#events, #queries, events, queries}.

Typical: The one time I'm good enough at algorithms to write a correct Div1-D solution, I'm also not literate enough to read a Div1-D statement properly.

Upd1. Looks like Martin also had this problem, and I don't type as fast as him.

Upd2. There are 12 contestants affected: Contest Status (look for WA#7)

→ Reply

SeyedParsa

12 years ago, # |

Could someone help me? my submission 3392032 got TL on test 41 in system testing but my next submission after the contest 3392661 got Accepted I just changed the size of my arrays from 1000005 to 2000005, but I think 1000005 was enough! wasn't it?

→ Reply

ShadowDancer

12 years ago, # ^ |

replace "cin" by "scanf" first, then submit again

→ Reply

SeyedParsa

12 years ago, # ^ |

← Rev. 2 →

Thanks, got Accepted! but why did this submission (3392661) get accepted? I just increased the size of array!

→ Reply

ShadowDancer

12 years ago, # ^ |

Maybe server was too busy first time? (see 41 test "Time: 1921 ms, memory: 23488 KB")

→ Reply

P___

12 years ago, # ^ |

Your first submission is also accepted.

→ Reply

abhineet08

12 years ago, # |

Enjoyed doing this contest.. Nice questions !! :)

→ Reply

YuukaKazami

12 years ago, # |

← Rev. 2 →

+58

drop 3 times in a row

lose IGM title so quickly

→ Reply

R_R_

12 years ago, # ^ |

+41

Looks like your ability has been transferred to wjmsbmr

→ Reply

YuukaKazami

12 years ago, # ^ |

+32

Actually she is my girl friend :)

But she is better than me >_<

→ Reply

Eurekash

12 years ago, # |

+14

Is today's contest unrated?

→ Reply

Ortiga

12 years ago, # ^ |

Why! ... no reason for what you say

→ Reply

Eurekash

12 years ago, # ^ |

+11

Up to now, the rating wasn't changed.

→ Reply

12 years ago, # ^ |

← Rev. 2 →

-13

Usually it will be updated an hour (or even later) after contest...

→ Reply

nathanajah

12 years ago, # ^ |

It's already more than two hours (almost 2.5 hours) and the rating haven't been updated yet..

→ Reply

M.H.D

12 years ago, # |

good problems! thanks :D

→ Reply

phantom11

12 years ago, # |

+28

How did this person become a candidate master even with a rating of 1555 ?

→ Reply

K.And.

12 years ago, # |

-8

Can anyone please explain this to me :-

For every unsuccesful submission , theres -50 so why does a user gets same score as me when he has 4 unsuccesful submission and i have none and the only question we both have solved is done at same time!

More specifically here , user 'abhinav92003' and i have got same score/rank. Hows this possible ?

→ Reply

Nicolas16

12 years ago, # ^ |

← Rev. 2 →

You don't get -50 when you eventually don't succeed to solve the problem. Here, you both solved one problem in the same time so you have the same score. He tried to solve B unsuccessfully, you didn't try, I don't think you really deserve a better score than him...

→ Reply

K.And.

12 years ago, # ^ |

@Nicolas16 , okay i get what you have said. And is there -50 for 'Failed System Tests' ?

→ Reply

Nicolas16

12 years ago, # ^ |

← Rev. 2 →

What do you mean by Failed System Tests? Actually, when you solve a problem, your points for this problem is equal to the score corresponding to the time you took to solve it, minus 50 points by previous failed submission (unless it is on the first pretest). And there is a minimum so that someone who solve a 500 point problem with 10 wrong submissions don't get 0 but 150.

→ Reply

phpduke

12 years ago, # ^ |

← Rev. 2 →

vote ups

No , i think you got it wrong . By 'Failed System Tests' , i think @IITian meant that one gets AC during the contest and after contest , at final testing , compiler judges it wrong! For that i think he was asking wether or wether not is -50?

→ Reply

12 years ago, # ^ |

I believe that it doesn't give any penalty, much like unsuccessful problems (submissions that don't pass pretests and the problem is eventually not solved) don't give penalty.

→ Reply

phantom11

12 years ago, # ^ |

Points are deducted for unsuccessful submission only when you have solved the problem. He has not solved the problem.

→ Reply

kavishrox

12 years ago, # |

-7

Can someone explain me how to approach problem D of division 2?

→ Reply

M.H.D

12 years ago, # |

-6

it passed almost 2:30 hours after the contest and still the rates are like before!!! why ?

→ Reply

jonathanirvings

12 years ago, # |

ratings were updated

→ Reply

wzc1995

12 years ago, # |

+27

I enjoyed this contest very much! Thanks :)

→ Reply

serbanstan

12 years ago, # |

Hi everyone! I realized during the contest that problem B Div. 1 could work using a brute-force approach, however I was unable to maintain the cycles without moving too many elements at once. Could anyone who solved the problem correctly give me a hint on how I could achieve this?

→ Reply

mugurelionut

12 years ago, # ^ |

+17

If you look at some of the accepted solutions you will notice that you can think of each move which is performed as follows: Let's say that the elements which are the first in their blocks are on positions P(1), P(2), ..., P(Q) (obviously, P(1)=1). Then, instead of thinking about cyclic shifts, imagine that all the elements stay in place, except:

the element from position P(Q) goes to position N+1
the element from position P(Q-1) goes to position P(Q)
...
the element from position P(1) goes to position P(2)

This way, you only get to move the elements on the positions P(1), ..., P(Q), and your sequence can now be found on the positions 2, ..., N+1 (instead of 1,...,N, as in the beginning). At your next move you will simply have to consider the fact that your sequence does not start at position 1.

→ Reply

serbanstan

12 years ago, # ^ |

Very cool. Thanks!

→ Reply

12 years ago, # |

← Rev. 2 →

I got hacked in Div 2 A . this is my solution , can anyone tell me the test case or my mistake

int main() { char a[6][6],c=0;

for(int i=1;i<=4;++i)
{for(int j=1;j<=4;++j)
cin>>a[i][j];}

for(int i=1;i<=4;++i)
for(int j=1;j<=4;++j)
{   int c=0;
    if(a[i][j]==a[i+1][j])
    c++;
    if(a[i][j]==a[i][j+1])
    c++;
    if(a[i][j]==a[i+1][j+1])
    c++;
    if(c==3 || c==2)
    {cout<<"YES";return 0;}
}
cout<<"NO";

}

→ Reply

logic_max

12 years ago, # ^ |

← Rev. 4 →

.#.#
##.#
....
####

In this case, first 2x2 square is a possible answer. You should also check if 'c' is 0.

→ Reply

12 years ago, # ^ |

my bad :( just didnt paid attention .

→ Reply

pllk

12 years ago, # ^ |

← Rev. 2 →

Here the answer is YES but your program prints NO:

#.#.
.#.#
#.#.
.#..

→ Reply

12 years ago, # ^ |

just amended this line

if(c==3 || c==2) to this line if(c==3 || c==2 || (c==0&&(i!=4 &&j!=4))) and got accepted

→ Reply