ZhNV's blog

Codeforces Round #324 (Div. 2)
By ZhNV, history, 9 years ago, translation, In English

Hello, Codeforces!

I'd like to invite you to Codeforces Round #324 (Div. 2). It'll be held on Tuesday, October 6 at 19:30 MSK and as usual Div. 1 participants can join out of competition.

Great thanks to Zlobober (Maxim Akhmedov) for helping me preparing the contest, to Delinur (Maria Belova) for translating the statements into English, to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon. This is my first round, and, I hope, it won't be the last one.

You will be given five problems and two hours to solve them. The scoring distribution will be announced later.

Characters from problems have their prototypes — my friends, familiars, native, and this round is dedicated to them.

UPD : 500-1000-1500-2000-2500

Good luck and high rating!

UPD2 Round has finished, thanks for participation!

Congratulations to the winners!

1). Siunaus

2). aasddf

3). M_H_M

4). lal

5). femsub

Editorial will be published later

UPD3 Editorial

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

Comments Comments (160)
| Write comment?
»
9 years ago, # |
← Rev. 4   Vote: I like it -103 Vote: I do not like it

Hope it will be a great Round :-) Happy coding :-)

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

Hope it's another interesting round. Good luck to all :)

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

I think clear problems with no story are better because there are many coders at codeforces that their main language is not english or Russian

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

    Totally agree. For me it is quite difficult to read and understand the storylines in English. Sometimes I even look up a dictionary for words that I don't know.

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

      It's a part of problem! You must have good English skills to understand storyline clearly. I think English tasks for Russian users will be more fair.

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

        and Russian tasks for American and UK users? =). It is nonsense.

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

          English is the main language of interaction between countries. You can't code in Russian; you code in English. So it makes sense that tasks should be in English.

          → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it -58 Vote: I do not like it

    :D

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

Best wishes to ACM ICPC — 2015 regional/sub-regional participants for their upcoming regional/sub-regional contest and congrats to those who already manage to qualify for ACM-ICPC World Finals 2016 — Phuket :)

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

"The scoring distribution will be announced later."
So mainstream ;)

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

So much grey。。

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

Lots of down votes here :D :v

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

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

Gayle Laakmann live session or this contest :D

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

    Isn't she over-rated?

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

    check this quora link quora. With all due respect ma'am, try to accept that there are people in this world a lot more smarter than u and being a bit** will not change that. :)

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

      Isn't she stupid for saying that? Gennady won't even care, let alone give her a comeback.

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

        yes i know.. in comments section she clearly states she knows him and compares herself and him as apples and oranges . LMAO XD

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

    Obligatory: Who?

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

The scoring distribution will be announced later later later late lat la l..........

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

where is scoring distribution ??

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

Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).

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

at problem d i output 3

2 2 23 i have wrong answer on pretest 1 , which has n=27 why? LE : my bad, sorry

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

    What was the problem?

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

      I forgot a return 1;

      The windows returns it automatically,but on linux is a big problem. Sorry guys for the misunderstanding

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

z

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

    why did you copy? this is bad

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it 
    cp 'solution of kieuquocdat123' 'copy of solution of kieuquocdat123'
mv 'copy of solution of kieuquocdat123' 'user gg.vdn1999'
    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

B — What's wrong with the solution 3^(3n) - 7^n ?

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

    Nothing.

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

      So it is actually right? I kept getting WA. Maybe I've got some mistakes in modular arithmetic ?

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

        Yep, with modulo formula is like this ((3^n) % MOD — (7^n) % MOD + MOD) % MOD. Because we can get negative number)

        P.S. sorry, didn't read posts below

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

    if(ans < 0) ans += MOD;?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
          int n;
    cin>>n;
    i64 s = 1, g = 1;
    for (int i = 1; i<=n; i++) {
        s = (s*7)%mod;
    }
    for (int i = 1; i<=3*n; i++) {
        g = (g*3)%mod;
    }
    cout << (g-s)%mod;
      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        cout << (g-s+mod)%mod;

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

          I feel so embarrassed :\

          And still. How could it possibly be negative?

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

            because 1000000007 mod 1000000007 is less than 100 mod 1000000007

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

            -3/2=-1 -3%2=-1 I don't like this either. It causes so many troubles...

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

        (g-s)%mod could be negative

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

      when u will get ans < 0 as 27^n — 7^n can never be zero

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

    That is what i did and it passed pretests

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

    check overflows.

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

    Logic behind formula? I failed very hard today ;_;

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

      There are total 27 possible way to distribute coins to 3 gnomes out of which 7 will have have sum equal to 6. And in our required answer we need to exclude that case. Since there are n such combinations we will have 27 ^ n — 7 ^ n.

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

    It's very cool to understand some dependence or notice combinatoric, but I simly considered second test and suggested, that it could be true. In a result, I was lucky :)

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

Problem 2: Just 3^(3*n)-7^n ;))

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

    27^n — 7^n : Still got wrong answer ...dont know why ...maybe becauze of MOD operation

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

      maybe when (7^n)%mod > (27^n)%mod, then you should write: ((27^n)%mod-(7^n)%mod+mod)%mod

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

      you forgot to add MOD if the answer becomes -ve. You should write like this: (27^n — 7^n + MOD)%MOD

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

    code by JAVA (3^(3*n)-7^n) % mod

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

dafuq is C pretest 9?

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

    seriously it's killing me to know

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

    I'm guessing something like this:

    INPUT
    5 1
    baset
    easej

    OUTPUT
    basej

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

      Tested with my program (which failed at pretest 9), and I got the correct output for that input.

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

      Yup Mine Passed that too :/

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

    may be some thing like it!

    4 2 abcd ebfg

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

How to solve problem E ?

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

    Greedily. Problem: sort the permutation with minimum cost. Let's assume that we already sorted first i elements(0-based). Let's p[j] = i. Then we need to find maximum ind such that i ≤ ind < j and j ≤ p[ind], it can be easily done by segment tree. Then swap elements at index ind and j. For each index i you will make O(n) swaps. Complexity O(n2logn)

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

      Are you certain this works? I submitted this and got stuck on pretest 14, and looking at your profile you didn't pass the pretests either (getting stuck much earlier than me).

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

        I wanted to write the same but was sure that it doesn't work;)

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

        Yes, that works. I didn't passed because I had wrong idea. I looked for maximum ind such that i ≤ ind < j and p[ind] > ind. This idea doesn't work for test: 4 4 3 2 1 1 2 3 4

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

    The minimum cost is achieved using any strategy that never moves any element further from its final location, since |i - j| is just the distance by which each element is moved (·0.5).

    One way to solve this would be putting all elements that need to be moved to the right in one set, those which need to be moved to the left in another set and always swapping the first element of the latter set with the last smaller element of the former.

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

How to solve D?

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

    If n is prime we print 1 n
    If n — 2 is prime we print 2 2 n — 2
    If n — 4 is prime we print 3 2 2 n — 4
    Else n = p1 + p2 + p3. We find closest prime number to n (p1). And we've got n — k = p2 + p3.
    n — k ~ log(N) (Don't remember why, shame on me). And just by brute force find p2 and p3.

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

    https://en.wikipedia.org/wiki/Goldbach%27s_conjecture

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

      Seriously, without knowing this conjecture, can anybody solve problem D? This kind of problem just piss me off!!!

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

        I solved D without this knowledge:D

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

          Then you (maybe without realizing) assumed that there is always valid p2 and p3 whose sum equals to n — p1. Problem guarantees there is a solution. It doesn't guarantee there is a valid (p2, p3) pair; that's why, you need to know Goldbach's conjecture.

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

            Yeah, you're right... This was just guess.

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

            You don't need to know it since the problem is simple enough to brute force. First check if n is prime, if so print. Else find largest prime smaller than n, now check if you can find one or two primes adding up to this (goes very fast since prime density is quite high), if so print. Else iterate.

            You know from the problem description that there is a solution, and you know that finding multiple fitting large primes is too slow so the only way left is to just find large primes and then see if you can find one or two smaller primes adding up to the result.

            This way you can solve for odd n as well since it is so easy to find a solution.

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

        Seriously, http://www.lmgtfy.com/?q=+integer+as+sum+of+three+different+primes

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

    I used Levy's Conjecture and Fermat's Little Theorem to solve D.

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

    I can't solve it during the contest due to a small mistake. But i did it right after the ending of the contest :/

    If n = 3, output 1 3 if n = 5 output 2 2 3 else

    since n is odd, n — 3 is even, and then we can use strong goldbach conjecture to solve the problem. Every number N even, greater than 2, can be written as sum of two primes. Since n — 3 is even, we can find this two primes that added form n — 3 and then add it to 3, which is prime. output

    3 3 prime[i] (N — 3 — prime[i])

    I used Sieve of Eratosthenes to find primes between 2 and 10^7, and if some number K didn't fit in this interval, I test it's primality by brute force. And used binary search to try to find N — 3 — prime[i] in vector of primes;

    http://mirror.codeforces.com/contest/584/submission/13459478

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

Problem A and Problem B is a joke in Python

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

What is The Solution Of div2 E? I tried to find symmetric group, but it seems hard to calculate the minimum step to sort the permutation

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

How to slove D? Damn I spend all contest to it

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

    https://en.wikipedia.org/wiki/Goldbach%27s_conjecture

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

      Still not sure how to do it.

      It is basically coding Goldbach's weak conjecture, right?

      3, and express n-3 as sum of two primes. Do you just brute force it? What about the time complexity?

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

        No.4 cannot be expressed by your logic

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

          The question says input is an odd number.

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

        Then we are assuming that '3' is definitely in the answer. Can you prove it?

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

          That is Goldbach's weak conjecture and it has been verified for numbers larger than the input in the question.

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

            In fact, Goldbach's weak conjecture has been mathematically proven to be valid in general.

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

        So handle small numbers manually for simplicity. (Since n is odd, n-3 is even, and you can brute for 2 remaining 2 primes numbers(other than 3) summing upto n). Handle cases of n=3, etc manually.

        For larger n, always try and express it as sum of exactly 3 primes. Find a prime number g below n and close to it.This is one of your 3 primes. Since prime numbers are not too far apart, n-g is now a small even number(my bound was 50000) and you can brute for how to express it as 2 primes.

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

          Thanks. Your gap was 50,000? According to wiki, a gap of 300 would suffice.

          https://en.wikipedia.org/wiki/Prime_gap

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

            I did not know that. Just wanted to be safe :P

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

          There's no need of different method for larger numbers. You can always brute force to express n-3 as sum of two primes. My solution passed with this method. I think the reason for this is that even when n is around 10^9, there is a very high probability of finding a small prime p(upto which you can iterate in time) such that n-3-p is also prime.

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

            Yes, I realized my solution during the contest failed only because my brain missed the "at most 3" condition. I ended up missing primes below 7 (3 and 5) — I thought they wouldn't be in the input since solution was guaranteed... Unfortunate error.

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

BTW, check this problem: http://acm.timus.ru/problem.aspx?space=1&num=1356. It's almost the same as the problem D, just a bit harder (but the solution for 1356 works here in problem D).

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

    This problem was on National Olympiad of Kazakhstan 2013-2014, as I remember.

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

C pretest 9 ahhhr.

C looks straightforward but did not work out.

My thought.

  1. Count the number of distinct chars in s1 and s2 and tag appropriately.
  2. We can sort based on frequency.
  3. Pick first n1-t and n2-t
  4. Try to find t chars in Universal set but not in union of s1 and s2.
→ Reply
»
9 years ago, # |
  Vote: I like it -15 Vote: I do not like it

System rating finished

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

Hello! I have a question at the second problem, Div 2. During the contest I printed(put(3,3*n)-put(7,n))%m; and i have got wrong answer on test 7. Now I am printing (put(3,3*n)-put(7,n)+m)%m; and I have got accepted. Why the second method works? Thanks!

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

    put(3,3*n)-put(7,n) may be negative number. So first method would be incorrect (returns m minus right answer).

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

      but why should i add m? m is 10^9 + 7. i don't understant..

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

        put(3,3*n)-put(7,n) = Km + ans
        may be less than zero. 0<=put(3, 3*n)<m ans 0<=put(7,n)<m. So -m<put(3,3*n)-put(7,n)<m

        put(3,3*n)-put(7,n) + m guarantee positive. So mod operation would be correct.

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

For D, I just generated primes upto 10^6 and tried to find the answer with simple check. And it passes. Why does it pass?

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

    Because primes are distributed pretty randomly with log(n) distance between them in average. So, there is no such number N that for all small prime numbers M up to 10^6, N — M is not prime.

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

I don't understand.Why 2000 points for problem D??? :o :o :o It was far far easier than B and C.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it 
swap(C, D);
→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why this submission get WA?

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

how to solve C ?

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

just added the condition of a+b+c=n and D passed :( :( :( :(

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

Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).

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

i forget to say :thanks for no delay

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

Some help on E? I can find the minimum cost but I cannot restore the swaps. I thought about going from left to right and if we see an element which is not on its place (it must go to the right) then let's say his position is i and it must go to position j. Let's first handle all elements that are greater than Ai in the interval [i+1,j] and then somehow solve for the current element. Can you please give me a hint?

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

    can E be solved using greedy method ?

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

      Well, the first part (minimum cost) can be called greedy, I guess. The idea is to find for each number its position in B. Then if we want A to become B, that means that some elements will go to the left and some to the right. We can make the observation that we need to consider only those elements which go to the right. Let's assume that after considering them, there is an element that must go to the left (if there is more than one, consider the leftmost). Moving it to the left means moving one element to the right. A contradiction! So if pos[k] is the position of the element with value k in B, we add to the answer max(pos[Ai]-i,0) for each i.

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

      My solution is actually greedy. What I do is in each step I have a vector that keeps all the numbers that have to go to the right (I iterate the numbers from left to right) and whenever I find a number that has to go to the left I just swap them and move the index of my iteration back so I can start from the number I moved.

      Before that I change the permutations so the second permutation is 1 2 3 ... N and the first one changes so it's the same problem but having to move a permutation to the sorted permutation.

      Let's see an example:

      4 4 3 1 2 1 2 4 3

      The problem is the same as solving

      4 3 4 1 2 1 2 3 4

      Now I start with 3, it has to go to the right so my vector is (3), then 4 has to go to the right so my vector is (3,4), then 1 has to go to the left so I swap 1 and 4 now it's

      3 1 4 2

      And my iterator moves back to where the 1 is, now 1 still has to go to the right so I swap 1 with 3 that is the top of my vector (or stack if you want to see it like a stack). Now it's

      1 3 4 2

      Then I continue iterating, 1 has to stay where it is and the vector is empty, then 3 has to go to the right, 4 has to go to the right too, and 2 has to go to the left, and when I analyze 2 my vector is (3,4) so I move 2 to the left and it's

      1 3 2 4

      And in the last step I change 3 with 2 so it's

      1 2 3 4

      And it finishes the process. This is a greedy approach and it's similar to selection sort I think.

      I start with 4 (it

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

    You can maintain an ordered set (balanced binary search tree) of all elements that need to go to the left (call this set L), and all that need to go to the right of the permutation (call this set R).

    In each iteration you perform one swap, that involves swapping the leftmost element in L with its closest element in R to the left (it clearly has to exist). If you store both the elements and their positions, you can efficiently maintain this structure as you go along in logarithmic complexity.

    You may refer to my code: http://mirror.codeforces.com/contest/584/submission/13456405

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

      You don't need such complicated structures as O(N^2) is ok for this problem.

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

        The complexity of my solution is actually something along the lines of O(N^2 log N) in the worst case (something like 5 6 7 8 1 2 3 4) anyway. I try to follow the approach which is easiest for me to comprehend on a high level. If it requires complicated structures, so be it (especially if they're already part of the STL). :)

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

    Consider the element that needs to go to the rightmost location. Lets say that element is in the ith position and needs to go to the nth position. Then, surely there must be an element from positions i+1 to n which needs to go to a position j where j <= i. If no such element exists, then there are (n-i) elements which final location is from (i+1) to (n-1), a contradiction! Find the leftmost element which matches this criteria using a pointer sweep and then swap it with position i then keep repeating until it is moved to its correct location. This is an O(n^2) algorithm.

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

Problem E : For the first time on codeforces, a solution didn't pass for me with cin,cout. My solution failed system tests after passing the pretests. And when I changed it to printf,scanf it passed. I think the problem setters should be careful the next time, as when crtical points and rating gets affected due to such reasons, it feels sad.

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

    Why are you blaming the problem setters for this? It was your fault!

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

      What should be tested is our knowledge, not whether we use fast i/o. And in fact such things have never happened on Codeforces before. Also when you get a problem wrong because of such reasons, it doesnt feel good. I'm not blaming them, but I feel if someone loses out on points for a hard problem, because they didnt use fast i/o, that is just not fair.

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

        If problemsetter increase time limit in order cin/cout submition past, it can cause that slow solutions will past with scanf/printf! Cin/cout speed is well-known fact, be careful, when you use it

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

    Do you use

    ios_base::sync_with_stdio(false);

    ?

    That line can save you from time limits if you use cin/cout

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

    You can add these lines to speed up cin/cout.

    ios_base::sync_with_stdio(0);
cin.tie(0);
    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It is time to midnight,but still waiting for Rating.

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

    It is almost sunrise, still waiting for Rating :P

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

    it's night and i have n't done my homeworks! but still waiting for ratings!

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

      Me too , it's weird how sometimes human being is not able to wait and do assignments both at once!

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

    we have the same time midnight. already tired

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

MikeMirzayanov. When you declare a rating?

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

Happy New Year CF!!! wait(wow), rating still not updated?

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

Wow, my rating is changed to +0 :)

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

What is this?

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

Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).

→ Reply