havaliza's blog

Codeforces Round #148
By havaliza, 12 years ago, In English

Hi all! :)

I'm glad to invite you to participate in Codeforces Round #148 today. I (Hamed Valizadeh) am the author of this round.

I'd like to thank Gerald (Gerald Agapov) MikeMirzayanov (Mike Mirzayanov) Delinur (Maria Belova) and Saeed_Reza (SaeedReza Seddighin) who helped me in preparing the round.

Score distribution will be the standard 500-1000-1500-2000-2500 in both divisions.

Hope you find the problems interesting to solve.

Good luck and have fun ;)

Update. Contest is over. Congratulations to the winners of both divisions! :)

Div1:

  1. tourist
  2. cerealguy
  3. Dmitry_Egorov
  4. RAVEman
  5. UESTC_Nocturne

Div2:

  1. LiWenHaoTianXiaDiYi
  2. goooooooopan
  3. jthread
  4. kolina
  5. xcodevn

And congrats to Endagorion who was the only one solving 238D - Tape Programming correctly during the contest.

BTW, I hope you didn't get sick of that boring problem! :-"

Update 2. The editorial is ready now, sorry for the delay. http://codeforces.net/blog/entry/5765

  • Vote: I like it
  • +273
  • Vote: I do not like it

Comments Comments (119)
| Write comment?
»
12 years ago, # |
  Vote: I like it +49 Vote: I do not like it

Two consecutive contests with Iranian authors, very good :-)

→ Reply
»
12 years ago, # |
  Vote: I like it +18 Vote: I do not like it

questions are going to be VERY hard :|

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why do you think so ?

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    fahmidan sualasham sakhte che berese be hale suala

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      may be the only reason why he's taken this low rate is that he's written it in phinglish(in farsi means writing persian in english).it's the translatoin: even understanding the questions is hard so how U wanna solve it??!

      → Reply
»
12 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Thankyou -- Good luck and have fun — -

→ Reply
»
12 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Codeforces Round #148 will lucky for div 2, :)

148 div 2 = 74

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

be Sure that Question will be So hard ! :) Do not Put your Rating in Danger !!! =))) GL everyone !

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    why are they going to be hard?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Because it has had a Three month Preparing Process and its Tasks Have been prepared in This Months :D and its Authors Are Havaliza + Saeed_reza

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Please, do not scare me!!! I hope get DIV1 today :(

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          Good and Hards Tasks... Now I am DIV 1 contestant!!!

          → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there's going to be a lot of math in this contest.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When the lags will be fixed?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    When the first contestants will give up ;) (seriously, I hope that the lag will not alter too much the contest :/ )

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Again it is — the crash!

→ Reply
»
12 years ago, # |
  Vote: I like it +30 Vote: I do not like it

This is not the first contest which gives me "**Bad gateway**" errors (502 — 504) instead of a contest start. I understand that is not supposed to be so, however, I would want to hear what exactly goes wrong with the server. Moreover, I believe there are plenty of nice guys over here who could probably be very experienced and helpful in configuring network/servers. Why don't we post some CodeForces issues as a public discussion? This kind of a solution would allow CF users to help the platform somehow.

→ Reply
»
12 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Pressing the F5 Key all the time...

Hope this is getting fixed soon!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Maybe the servers work has worsened because of you and some other users pressing F5 all the time?)

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Isn't it better to start on the 5 PM than 4.55 PM ?

→ Reply
»
12 years ago, # |
  Vote: I like it +63 Vote: I do not like it

http://www.quickmeme.com/meme/3rmsct/

→ Reply
»
12 years ago, # |
  Vote: I like it -15 Vote: I do not like it

nooooooooooooooooooooooooooooooooooo

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

I think Codeforces should use safe mode during contest time as they did few times in past. Server down before contest is ok but this may happen in contest time too. Topcoder also closes practise rooms during contest.

→ Reply
»
12 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Friends, nothing is perfect!!!!

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +75 Vote: I do not like it

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The server needs to be upgraded.

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it -18 Vote: I do not like it

Div 2 — B is not well defined. When we erase a character at position n and cp points to the character at position n+1, does it still point to that character (now at n) or does it remain at n+1?

Why the negative votes and no replies? Is there any place where we can ask questions to the organizers?

→ Reply
»
12 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Very easy problems. Thx!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Easy for you?

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    I never felt as stupid as I did on this contest =D even in div2

    Teach me, master, I want them to be easy for me too.

    WTB editorial!

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    I think, you cannot make the conclusions becouse of first and second tasks.

    → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Looks like its going to take a while to reach division one :s

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, div 2: I think just care the case n==3, another case the anwser is "2 2 2 2 2 ...". Is it right?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no but there are only two options: two smallest in one subsequence or each in a different one. there is no way to decrease the maximum value of F so we have to increase the minimum of F.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, the answer is without doubt "2 2 2 2 2 ..." only when n==2. In other cases we should check more conditions.

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

it looks problem E,DIV 2 was easier than D...:D

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    and it was the opposite in div 1 !!!!

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I recall a similar problem, at least on the surface, which also asked the minimum number of edges which direction you had to change. Maybe some people solved that problem and chose this instead of D, since it looked very familiar.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can't erase your comment, prepare to receive minus by the non-contestants who will not get it now that the system test phase is ended ;)

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are the pretests of С (div1) strong enough? I wrote solution 5 minutes before the end and realized that sometimes it can't find solution. So I just put line: if (best == INF) cout << 2. And it passed pretests! I'm 99% sure my solution is wrong but maybe someone can prove it? :)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It depends on your algorithm ... Maybe you can always find a solution?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think it doesn't work on bamboo graphs (e.g. O-O-O-O). Idea is the following: Choose one vertex i = 1..n and run DFS on tree to mark for every vertex: is the parent edge forward or backward. If this edge (to vertex j) is backward, we claim pair (i, j) to be good. If both pair (i, j) and pair (j, i) is good, we can relax answer with number of backward edges on the way from the root minus one.

      P.S.: Ouch, looks like I deleted some lines and now it relaxes just if pair (i, j) is good :)

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Aw .. I'm a little confused .. Hope you pass it!

        → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

I liked the contest. At the beginning problems confused me a lot, especially problem A. But when I thought a bit about them, they turned out to be solvable.

Unfortunately my Div 1 C failed...

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I can't agree more ~ The problems are all interesting and skillful.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ahhh... at last system test started. hope it won't take long time to finish.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Judging in not working!

Edit: Now working

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I missed a hack on problem B :( Someone in my room outputs "1 1" if n == 2...

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B Div 2 много у кого упала ...

→ Reply
»
12 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I did not spend much time on the problem E because of the following test:
7 8
1 2
2 4
1 3
3 4
2 5
5 7
3 6
6 7
3
1 4
2 7
3 7

The answer is 2 but if we consider only stops reachable in any case for each bus route we don't find a solution. I am wondering how many of those who submitted this problem know about this test?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice problems...But I'm lack in experience and my solution of B got FST...TAT

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm unluky :( ;(

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Pleeeease, don't make us wait, update the rating.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can smb explain to me how to solve problem C(Div2) or A(Div1)? Thanks in advance

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    hey, count how many number you can put in the place of a1, then how many number you can put in the place of a2 and so on .

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    2^m — 1 ways for the first number, 2^m — 2 for the second etc.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    f(n) = f(n-1) * (2^m — (n-1) — 1), f(1)=2^m-1. Here 2^m — (n-1) -1 means you have this number of ways to append a number to the valid sequence with length n-1. "-1" since you cannot use 0.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't understand.

      Why can you simply add unused numbers (apart 0) to a sequence of length n-1?

      Look at this sequence (n=3,m=3): 5 (101), 2(010), 7(111)

      All numbers are different, but 5^2^7 = 0.

      So it is a wool sequence: l=1,r=3

      Why am i wrong?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        At begining you have only "0" as foribbden element.

        After first addition, you have one more foribbden element (the added one).

        After second addition, you have next foribbden element (first ^ second). And so on.

        So, you must look at "accumulate xor" not (simply) values.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Thanks for your explanation.

          I had misunderstood the meaning of "n-1".

          And you can also be sure that all of the "n-1" accumulated XORed values will be different, so that there are exactly n-1 distinct numbers to be excluded:

          Else, it implies the previous n-1 elements would be a wool sequence:

          If XOR (1 -> x) = XOR (1 -> y), y>x would imply that XOR(x+1->y) = 0, implying it was a Wool sequence.

          Impressive how some people solved it within minutes =|

          → Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I wish this contest were the Elimination Round for BAYAN ... Thank you for the good contest :)

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Finally "Expert"! :)

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +43 Vote: I do not like it

    Multi account is bad. There is a lot of "Ashvili" account on Kutaisi, with one or two contests on the history, like if they create a new account when they are too low to gain a lot of rating. The codes present the same style (same freopen (why not, its common), but reduced indentation too), and you said "Finally Expert" like if it wasn't your first contest, but in your profile, you are a new contestant. Suspicion...

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 3   Vote: I like it +14 Vote: I do not like it

      More: the header "cmath" is often more present than "math.h" for C++, but here, for all the bukhnikashvili, there is "math.h".

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Anyway, he does not hide anything :D

      @Lashabuxo I'm hope that you remain blue after a few contests :)

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Haha. Better to sit quiet if you're cheating! :P

      → Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Nice Contest :D hope to see the Editorial soon..

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why in the sample test for div2 b: 7 4 1>3>22< 1 3 4 7 7 7 1 7 the answer for call l = 1 and r = 7 is 2 3 2 1 0 0 0 0 0 0.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    1>3>22<

    last 6 numbers are ignored for convenience

    1-> CP=1 DP=R MAP=0>3>22< X= 0 1 0 0

    2-> CP=2 DP=R MAP=0>3>22< X= 0 1 0 0

    2-> CP=3 DP=R MAP=0>2>22< X= 0 1 0 1

    2-> CP=4 DP=R MAP=0>2>22< X= 0 1 0 1

    2-> CP=5 DP=R MAP=0>2>12< X= 0 1 1 1

    2-> CP=6 DP=R MAP=0>2>11< X= 0 1 2 1

    2-> CP=7 DP=L MAP=0>2>11< X= 0 1 2 1

    2-> CP=6 DP=L MAP=0>2>10< X= 0 2 2 1

    2-> CP=5 DP=R MAP=0>2>00< X= 0 3 2 1

    2-> CP=5 DP=R MAP=0>2>0< X= 1 3 2 1

    2-> CP=5 DP=L MAP=0>2>< X= 2 3 2 1

    2-> CP=4 DP=R MAP=0>2> X= 2 3 2 1

    2-> CP=5 END

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If i can solve 3 problems in div2 & 2 problems in div1...Whose 1 will be better???

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It may vary between man to man. But according to my opinion, solving 3 in div II is only better confirming that any 2 of these 3 also appear on div I(Like 2 from (C-E))

    → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I see some ppls failed Problem B (div1) on test 6, giving the same wrong answer 190 (P.S. correct answer would be 200).

Is that a coincidence?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Many people have the same, good, algorihtm. Similarly, many people have the same, but incorrect algorithm :P Just coincidence :)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ;) But when you think carefully, there is no way you can come up with a combination which is even better than the best case, even with an "incorrect" algorithm.

      What you can do with an "incorrect" algorithm, is to get a worse answer. Am I right?

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh no I got WA on #6 and my answer was 190...However,I don't know why it's wrong = =

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I would suggest that you might have calculated the minimum value of the maximum value and the maximum of the minimum value separately while they might not be achieved at the same time.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        eh..no..I have thought about this — -...It's so kind of you to view my solution 2500928 (cause my poor english I cannot describe it TAT)

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          int min1=a[0].first+a[1].first+(i==1?h:0);

          This give me accepted. thx

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            oh no I misunderstood the problem,I thought f(i,j)=Ai+Aj+h if at least one of i and j is in the first subsequence!!Ahhh terrible~~~~~

            → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where else can i find the current contest questions being discussed????????

→ Reply
»
12 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Сложный раунд=(

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    if this was an answer to my question then sir plzzzzz give link coz i dont understand Russian............plzzzzzzz provide the link.......

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      You should use translator or simply skip comments in Russian ;)

      He wrote something about 'complex round =('

      And... here is right place to discuss this round's problems

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where can I find the solutions to the problems in contests?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Try to take a look at others' solutions but don't copy them.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any editorials?

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +42 Vote: I do not like it

UPD Ok it's published now

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

hey guys can anyone tell me how to solve Div 2 Problem C

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    try to make a new sequence of n numbers for each valid answer sequence that i'th element of new sequence would be equal to xor of first i elements of answer sequence . each element of new sequence will be different form others and it's between 1 and 2^m -1 ... so for every n and m number of answer sequences would be equal to this :

    (2^m -1)*(2^m -2)*...*(2^m -n)

    I hope this will help you :)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I can't get the first sentence at all...did you really mean the second word "sequence"? Each element of new sequence will be different from others? Are you sure? I thought (1,2,1,2) is valid since 1^2^1^2 == 0.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +2 Vote: I do not like it

        But the request is to count the sequences that are NOT a wool sequence...So (1,2,1,2) is invalid..

        → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

When the next contest start?

→ Reply