jqdai0815's blog

Codeforces Round #268
By jqdai0815, 10 years ago, In English

Hello everyone! Codeforces Round #268 is coming soon! We invite you to participate in this round. It will be held on September 20th at 17:00 MSK.

Problems have been prepared by me. Thanks xyz111 and dhh1995 for giving me the idea of some problems. Thanks vfleaking, foreseeable, MinakoKojima, Ruchiose and xllend3 for testing.

I also want to thank Gerald for helping to prepare this round, Delinur for translating the statements, and also MikeMirzayanov for Codeforces and Polygon.

It is my first round on Codeforces. Hope you will enjoy this round.

You'll help a boy named Little X in this round. Good luck and have fun :)

UPD

Round has finished. Thanks for participating.

Congratulations to the winners.

Div. 1

  1. PavelKunyavskiy
  2. Kostroma
  3. HellKitsune
  4. SirShokoladina
  5. DemiGuo

Div. 2

  1. manman
  2. topcodecheforces
  3. mhy12345
  4. GS_ZJ_137
  5. z.last

Congratulations to ecnerwala, the only participant to solve the problem D!

Unfortunately, no one has solved the problem E in both divisions.

Editorial for the round will be added tomorrow.

UPD

Editorial is here.

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

Comments Comments (215)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Looking at the level of the setters, I would say a Div 1 round would have been possible :( Edit: I thought today's round was their round, don't mind :P

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

another china round! good luck everyone :)

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

Why "Little X", but not simply "x"? :)

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

It's the first time to see contest announcement before the start of previous contest :D

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

Why are there so many numbers in the handles of the problem setters ? =D

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

    No, many handles for testing not problem setting

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

    Because 233 is a special number in Chinese... It means "LOL"(Laugh Out Loud) in English which shows a man bursts into laughter. And we use repeating "3" many times strengthen the funny meaning. 233 is a photo id in a famous forum of China. here is the photo.

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

      Link is broken.

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

        poor link...

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

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

            what is APEX KEK means

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

              Oh right, I should've included a

              see more on Know Your Meme

              and apex = top (it's made using rarely used words, like nay = no). I just found the "poor link" reaction seriously funny :D

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

                Oh...I thought LOL is the short from Lots Of Laughter... After clicking your URL, I have just known LOL is short from Laugh Out Loud......

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

                  It's hard to say what people want it to be (and it doesn't really matter), it could even be short from "Lots of LOL" :D

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

          fix the photos.

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

Yessssss

Chinese round -> more math

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

    There is actually going HackerRank contest "Ad Infinitum — Math Programming Contest September'14 ". It lasts 2 days :). Give it a try.

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

    First of all, before this commented is downvoted, I would like to point out that codeforces is for developing your algorithmic knowledge. Depending on your definition of "algorithmic", math could be considered an algorithm; and this is a perfectly valid opinion. However, what is the point of competing in coding contests if all you want is math all the time. Every time you post, it's about math; nothing else. Coding contests are meant to introduce you to varied ways of thinking, not limited to math.

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

      I'm agree with you and I don't know why many people downvoted you. Someone like math, someone not. But everyone love coding. I think we shouldn't care about kinds of problems.

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

Oh, god, I think I can't participate any more Chinese round, because it is 6:00 am here.

Btw, I guess more testers you have then more difficult this round will be.. let's see if it is correct.

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

    early sleep and early wake~ After brushing teeth and washing face, you can participate the Chinese round relaxedly

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

    Have fun getting used to the U.S :)

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

nice

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

    newSolar BigGod is here! You are a Yellow! But you say you are only div2.....

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

      When did I say that? I didn't use this Id for more than half a year.

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

So, its going to be a typical chinese round . good luck everyone :)

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

My last contest in summer! I'm going to school on Tuesday! Hope a good contest! Good Luck!

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

    I think it's everyone's last contest in summer in northern hemisphere :|

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

    :|

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

    It is already 20th of September. What kind of summer do you have?

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

I have registered for the contest, but due to time constraints (I have to participate in a qualifying round of some other contest), I will not be able to participate for the entire 2 hours. Can I appear as a virtual participant (If I participate for the first hour of the contest)?

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

    No, if you submit during contest, it will be counted in your actual participation and rating changes will also apply. So it is better to take the entire contest as a virtual contest at some suitable later time.

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

I will try to help Little X as much as possible but can Little X tell us score distribution ?

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

Attention please,it's a Chinese round!There is reason to believe that it's impossible for the konjacs(its Chinese name ‘juruo’ means the people with low level like me)to improve rating.Good luck to every super cattle(you may be able to understand it)! TAT

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

Many GranMaster & Master for prepare this round. My premonition told to me that "be careful with tricky test"

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

Ehm, score distribution?

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

It seems that I will participate in the next contest (Div2) Officially :D

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

500 — 1000 — 2000 — 3000 — 3000 :(

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

B(div1) 4 7 9 2 4 5 7 If someone need.

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

    The answer is "YES 1 1 1 1", right?

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

    would it be correct if ans is YES 1 1 1 1 ?

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

      Yes. ) But any people have answer : "NO".

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

    Or
    3 5 8
    2 3 5

    (sometimes they remove numbers from first set without checking if first set stay valid)
    Edit: the answer is "NO", but some were giving for output "YES 0 1 1"

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

what was the hacking case in div-1 B...my solution got hacked :(

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

How to solve C ??

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

    I took the following greedy approach:

    for n <= 8, run recursion
else
1 * 2 = 2
3 * 4 = 12
2 * 12 = 24
5 - 6 = -1
7 - 8 = -1
-1 - -1 = 0
for i > 8 && i <= n ( i * 0 = 0 )
24 + 0 = 24
    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used the following :

    for n<4 print NO
for n=4/n=5 find solution by hand
for n>=6
n - (n-1) = 1
1 - 1 = 0
for all i = 5 to i = n-2
i * 0 = 0

you are left with {0,2,3,4} - just do 2*3*4+0
    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do we solve Div2 Problem C?

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

    There are several ways to solve it. You can see that with N < 4, there is no answer. With N = 4, you can easily take (1 + 2 + 3) * 4 = 24. N = 5, 2 * 4 = 8, 3 * 5 = 15, 8 + 15 + 1 = 24. From N = 6, 4 * 6 = 24, 3 — 5 = -2, -2 + 2 = 0, 0 * 1 = 0, then for i from 7 to N, 0 * i = 0, and finally, 24 + 0 = 24.

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

    I took special cases for 4,5,6 and

    and for n>=6

    used pre-created sequence for 5 and 6 based on even or odd n,

    made every element n and n-1 as (n)-(n-1)=1

    and multiplied all the ones in the end.

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

Can anyone share his/her approach in Div2 C problem ?

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

    If n is even and >= 4: 1 * 2 * 3 * 4 = 24 n-(n-1) = 1, (n-2) — (n-3) = 1 and so on. So just multiply the 24 with the ones.

    If n is odd and >= 4: 5 * 4 + 2 + 3 — 1 = 24 n-(n-1) = 1, (n-2)-(n-3) = 1 and so on. Same.

    There is no answer if n < 4.

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

    for n >= 6 erase all numbers except 2,3,4 using: (5 — 6 + 1) * z
    for n = 4 and n = 5 — hardcoded answer

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

      Yes got the idea now couldn't think about it in contest :(

      Thanks :)

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

How to solve Problem D of Div. 2 ?

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

    My solution was, to just use pair(value,pos) in a set, and modify the set comparing function to consider only the first value. Then just keep checking if each element has its match in either A or B. hope it passes final tests :)

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

    Your graph is inspirational !!!

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

    It's a bipartite matching problem ;)

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

    Hm, i had two maps, one <int,bool> where i stored if there exists some number, and one where do i keep position of that number in initial array. Then, for every number, check map1[a-array[i]], map1[b-array[i]], if there is both do sth, if there is only one put it into the set, if there is none return -1. See my code for details UPD: It failed on systest, so this approach may be wrong

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

    Pick a number in the list, say x. Then we are interested in whether a-x and b-x are also in the list. If

    1) Neither are in the list, then partitioning is not possible.

    2) If only a-x is in the list, then both x and a-x go into set A

    3) If only b-x is in the list, then both x and b-x go into set B

    4) If both are in the list, then this is inconclusive. We need to further check b-(a-x) and a-(b-x) according to the same rules (for example, if only b-(a-x) is in the list then all of a, a-x, b-x, and b-(a-x) go into set B).

    The implementation of this is pretty straightforward, though in contest I mishandled the a=b case (which requires special handling as a-x=b-x=b-(a-x)=a-(b-x)=...). See 7882478.

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

      Why do we need to check further ??? Can you give test ??

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

      i got it on contest , but i missed when cout no

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

    hopcroft-karp bipartite matching

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

      Hii, palmerstone, I like your approach using Hopcroft karp, but I am having trouble understanding the case when both a-x and b-x (along with x) are present in given array. Here's a part of your code

      if (!c && !d){
      flag = false;
      break;
}
/*...*/
if(!flag) puts("NO");

      how did u came to such conclusion that when both a-x and b-x are not present, there can't be any possible matching?

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

        What do you mean? x is an element of the given set. If both a-x and b-x are not present then it is certainly not possible to include x in any of the sets, is it? Hence not possible.

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

          Oh yes. Thanks, I get it now... By the way can you please tell what does array L and R store in your implementation of hopcroft-karp ??

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

    My solution for div2 D/div1 B:

    Assume that b>a because we can switch them anyway and b=a is trivial case. Let x be the smallest value which hasn't been assigned yet to either of the sets. If there exist a value b-x, then we have to pair values x and b-x into set B because value b-x can't be paired into set A because a<b and therefore a-(b-x)<x and there exist no values smaller than x. So we know that if there exist value b-x, we have to pair it with x. If there doesn't exist value b-x, we have to pair x with a-x into set A. If we can't do that, the answer is NO. This approach can be implemented just by iterating over elements which haven't been assigned to either set in ascending order. 7874034

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

What's the solution for problem C? Is it some kind of greedy/constructive algorithm based on number theory, or is it dynamic programming? The numbers are from 1 to N, so I assumed it was a number theory problem but couldn't come up with a solution.

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

    For numbers up to 3 answer is 'NO'.

    Solution for 4:
1 * 2 = 2
2 * 3 = 6
6 * 4 = 24

    Solution for 5:
5 - 3 = 2
2 + 1 = 3
2 * 3 = 6
6 * 4 = 24

    Other solutions:
N - (N - 1) = 1
(N - 2) - (N - 3) = 1
...
1 * 1 = 1
...
<- solution for 4 if N is even or 5 if N is odd
    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just notice this if(n<4) no soln if(n==4) 1*2*3*4=24 if(n==5) 4*5+3+2-1=24 and for all other numbers, if n is even then you do the 4 thingy and keep doing i+1-i=1 for all the numbers, and at last do 24*1=24 as many times is you need same thing for odd n, just you would use 5 thing

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

    You can get the 24 by using 2, 3, 4 or 1, 2, 3, 4. For the neighbor number, say, i and i + 1, we can get 1 by using - operator, and 1 can be eliminated by * with other number. Then I think you get the answer:-)

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

    if n is less than 4, obviously no solution. Then 2 cases, if n is even, we can reduce the sequence to 1,2,3,4 (after which we just multiply each element one at a time). By subtracting n and n — 1, multiplying 1 and 1, then n — 2 and n — 3 and so on.. if n is odd, you can similarly bring it to 1,2,3,4,5, we can reduce to 2,3,4 by doing the following: 1 + 5 = 6, 6 — 3 = 3. After this we just multiply each one again. Hope its clear :)

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

    A much easier solution is to get 1 by doing n-(n-1) and then 1-1=0. Now do i*0=0 for all i from 5 to n-2. And then do 2*3*4 = 24. For n<=6 pre calculate the ans. I hope you get it.

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

This contest reminds me of the Codeforces Round #146 (Div. 1) which was prepared by WJMZBMR... Codeforces Round 146 (Div. 1)

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

To those who have problems with div. 2 C here is my approach:

First print out the answer for cases n <= 5. Then for n > 6 you realize that you can make 24 by multiplying 6 and 4. Then you are left with the burden of creating n — 2 more operations, thus, you subtract adjacent numbers so you get a long chain of 1's, be careful that you cannot use 6 and 4 again. Then you simply keep alternating between: 1 — 1 = 0 1 — 0 = 1

until you are left with 1 or 0 then you can just do either 24 + 0 = 24 or 24 * 1 = 24

I did this approach during this contest and it seems to work. I was a bit dumb for the first hour because I forgot to print out "YES" at the beginning >.<

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

    Haha I forgot to print "YES too :P

    My solution was as follows: the n = 4 is easy, because we can just multiply 1 * 2 * 3 * 4 = 24. The n = 5 is a tiny bit trickier, but we have 4 * 5 = 20, then 20 + 2 + 3 — 1 = 24. Now, if n > 5, we can take the two largest numbers, n and n-1, and subtract n-1 from n to get 1. Now, our list is 1, 2, 3, ..., n-3, n-2, 1. If we multiply the two 1s, we are left with 1, 2, 3, ..., n-3, n-2, which is the list for n-2, a smaller case! This means that n = 6 will work, since we can reduce it to the n = 4 case, n = 7 will work, since we can reduce it to the n = 5 case, and so on.

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

    my answer is 1*2*3*4*(6-5)*(8-7)*...*(n-(n-1))=24 for n is even 5*4+3+2-1*(7-6)*(9-8)*...*(n-(n-1))=24 for n is odd

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

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

    Our Little X is in upper case. Too big!!

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

Fuck math with no programming!

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

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

    Got butthurt? Go away.

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

      Why so serious?

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

        Because he was rude, used swear word and continues math-hate here which I'm completely fed up with.

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

    I am not sure, but only the last problem seems to be mathematical one.

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

      First one was also mathematical more than programming I'd say. But, a major chunk of programming is maths and logic, so it is only expected.

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

        Of course all the problems are about math here(discrete math mostly), but here, I believe people mean complicated math by saying "fu**ing math again", but noticing that 6*4=24, a*0=0 and a*1=a.

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

That was one fast system test!

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

Why so weak pretests???
I guess lots of Bs will fail.
Also there was too many WA2 in problem A... For constructive problems, first sample should be more difficult. :|

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

    IMHO, pretests complexity is completely up to the Problem Setter.

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

I spent all 2 hours on problem D but still cannot finish coding it...

Calculating "lexicographically smallest" one is very confusing, and I couldn't make solution without very complex iteration. Doesn't there exist any simpler solution?

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

    Indeed. If it weren't for this "lexicographically smallest" than it would be doable with centroids and that kind of stuff, but it is a significant obstacle :/.

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

      Yes. Thinking about centroid is fun, but I think main part of this problem is more complex part, because only 1 people solved it despite thinking about centroid is not so hard...

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

Like 90% of 469D - Two Sets has failed tests. Lol!

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

Wow, system test over in 10 minutes this time!

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

thanks for the fast system test~ I think I could back to blue.

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

problem A:

for n=1,2,3: no

for n=4 : 1*2*3*4

for n=5 : (3*1+5-2)*4

for n>=6 : 2*3*4+(6-5-1)*7*8*...*n

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

for div 2 B And D

what is the bug in my solutions ??

Code_B

Code_D

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

    For D:

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

    about D:

    |cpp| if (n % 2) { puts("NO"); return 0; } <||

    it will fall on the case

    3 2 6 1 2 4

    because 2-1=1.

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

    about B: Your check for intersection doesn't look right. See if you can find your error here: if ((x >= a[j].first && x <= a[j].second) || (y >= a[j].first && y <= a[j].second))

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

      can you please explain why this is wrong?

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

      Same question, please explain what's wrong here?

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

        Seriously... 17 months ago

        Anyway, look at the conditions inside the if statement. What is it doing? Is it checking that the two segments overlap, or if one segment is completely within the other segment? What we want is for the two segments to intersect, one segment does not necessarily have to completely contain the other.

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

Isn't this code wrong 7871552 ??

Test: 2 1 0 0

1 5

2 4

7 7

UPD:The inputis illegal sorry.

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

    I think it is wrong. The answer should be 0, but it is giving 1. oh! Inputs are not valid.

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

Ehh..

if (n % 4 == 1) { ... cout<<"3+1 = 4\n"; ... }

There wasn't any pretest for n % 4 == 1? It's really disappointing :\

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

My solution for div-1 B using dinic's algorithm for maxflow TLEd :(

I thought it would run in O(E * sqrt(V)) time as all edges are of unit length. Can anyone please let me know why dinic would be suboptimal? Isn't it the same as Hopcroft-Karp for unit graph?

My Submission

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

    The nodes in the subgraphs can have at most 2 degrees. I think you didnt need such a complicated algorithm

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

    My implementation of hopcroft-karp got Accepted in 514 ms

    Solution

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

By the way, somebody solved problem E in Division 1...

→ Reply
»
10 years ago, # |
  Vote: I like it +101 Vote: I do not like it 
printf("24 * 1 = 1\n");

and Failed A...

What a sad story :((

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

Great test for problem D Div 2. Lots of Failed System Test

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

Can you give me an example on which my code doesn't work ? ( Sorry for my poor English) http://codeforces.com/contest/468/submission/7883022

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

    Why would everybody use tonns of #define? It puts my bum on fire.

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

      Because it's easier to write MP than make_pair or something else... You write faster

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

        It makes code harder to read in my opinion. Especially when I see that 50% of code are definitions for "for" and other shit.

        If you use snippets you can write fast enough. As for me is more important to think fast, not write.

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

          FOR0(x[i],8) vs. for(x[i]=0;x[i]<8;x[i]++) not only saves keystrokes, but also reduces probability of typing errors.

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

            Ok-ok. I understand, I am bad programmer if I don't use #define.

            → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    2 8 10
4 6
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's well... output : YES 1 1

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

        Sorry. Try this.

        3 12 14
5 7 9
        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Thank you very much for this example :). Now, I understood why my code doesn't work

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

I can not understand the reason why many of the chinese authors make hard and mathy problem set. In my opinion, contest's easy problem should be easy. Otherwise it is not motivating enough for people to participate.

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

I've entered for the next div2 contest.The konjac(its Chinese name ‘juruo’ means the people with low level like me) has no human rights.

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

winter is coming

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

when will the ratings be updated?

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

About Div1 B. Does anybody have a case with an odd n and positive answer? Or could explain why this is possible? I assumed this wasn't possible during the contest, but apparently it is. Maybe I misunderstood the problem.

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

can someone explain why this solution is incorrect? http://codeforces.com/contest/469/submission/7867443

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

    you should use resize not reserve

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

      reserve only reserves space but the size of your vector stays the same. it is only useful for example you read numbers and push them back of a vector. the vector resizes itself when you push back sometimes. if u know how many numbers u are going to push back then u reserve some memory and when u push a number back of the vector it doesnt allocate new memory

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

How to solve Div 2D/ DIV 1B ?

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

Task D div 2 (Two Sets) Test Case 9:

How could the correct answer be YES 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?

when it is stated in the text: If there is a way to divide the numbers into two sets, then print "YES" in the first line.

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

    You should know that {} is a set. it is an empty set.

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

      It is like sharing 5 apples between you and me. You take all of the apples and I get none of them. But what we just did was sharing :D

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

    Note

    It's OK if all the numbers are in the same set, and the other one is empty.

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

    You Didn't read this Note:

    "Note It's OK if all the numbers are in the same set, and the other one is empty."

    By the way, I got WA too in this case :(

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

Can any one please point out the mistake in my code. I am a newbie and am unable to find the glitch in CODE 469D. Thanks in advance

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

When will they update ratings?

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

Chinese Round again, so difficult problems again...

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

Can anyone tell me what's wrong with my code for problem D, please?

7882442

Thank you!

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

    Check this test:

    10 12 14

    3 2 10 9 4 9 3 2 5 10

    Answer is:

    YES

    0 0 1 1 1 0 0 0 1 0

    Edit: Sorry. Test is incorrect.

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

      Explanation: Some numbers may occur several times and you should put some of them in set A, and some other in set B.

      Edit: It's not true. My mistake.

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

        That's not true, the problem statement specifies that the numbers are distinct.

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

very interesting and enjoyable problem indeed..i enjoyed this very much :D

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

I have a question regarding this submission 7868179 Div.2 problem A .. I unsuccessfully tried to hack the solution using a testcase where the algorithm will try to access h[100] while the size of the array is actually 100! so the last element i can access is h[99], but the hack was unsuccessful .. any explanation ??

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

    When you access beyond the range of an array in C/C++, it gives an undefined behavior. This undefined behavior may or may not throw an exception.

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

My first time doing the first three problems . Best wishes.

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

So much math, it's awesome round!

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

jqdai0815 Thanks! It was a great Round!

Could anyone clarify on grading policy?

I've successfully submitted solutions for 2 tasks without penalties or resubmissions but my final round score is negative why it could be so?

Thanks!

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

Round Stats

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +34 Vote: I do not like it

I just wanted to leave this here: 7878473

In case you're too lazy to open, here is the whole accepted code to C in Python (authored by ZhouYuChen)

m = int(input())
x,t=10**100-1,m-100*45*10**99%m
print(t,t+x)

I have to say that I'm impressed :P

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

    A really neat/impressive solution!!

    What is the logic behind the solution?

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

      Let S(l, r) be the sum of digits of numbers form interval [l, r]. Take big k and see that S(1, 10k) = S(2, 10k + 1) - 1 = S(3, 10k + 2) - 2 = ...

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

        Here we have with x=10^100 — 1 and t=m-(450*10^100)%m = m-r , where r<m

        S(t,t+x) = S(1,1+x)+(t-1) = S(1,10^100)+(m-r-1)

        Above must be equal to 0 when taken mod m

        (S(1,10^100)+(m-r-1))%m should be = 0

        S(1,10^100)%m + (-r-1)%m

        If the above steps are accurate, I cant follow the proof after that.

        Can you please explain?

        Thanks.

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

          You are taking a hard way to understand this problem. I used the same idea and I think I can explain more clearly.

          There are 4 things to observe:

          1) S(1,10^k) = 45 * k * 10^(k-1) + 1

          You can try to convince yourself doing some mathematical proof or just run a script that calculates in a brute force fashion when k is small.

          2) S(1,10^k) = S(2,10^k)-1 = S(n+1,10^k+n)-n

          This is the trickiest part! In the first case, l = 1 and r = 10^k. What happens if we increase them both? l = 2 and r = 10^k+1. In this case, we "removed" one element whose function value equals to 1 and "added" another one whose value is 2 (10^k+1 has two 1's and a lot of 0). You can observe (by induction) that the same holds for any value we add to both l and r. Therefore, this formula I wrote here is correct

          3) S(1,10^k) % M = x if and only if S(M-x+1,10^k+M-x) % M = 0

          Well, if you add M-x to both boundaries of S(1,10^k), you will have S(1,10^k) = S(M-x+1,M-x10^k) + x — M, according to property (2). Then you take modulo M and you will have S(M-x+1,M-x10^k) % M = [ S(1,10^k) + M — x ] % M = [ x + M — x ] % M.

          4) S(1,10^17) > 7 * 10^18

          Finally, as a is at most 10^18, you have to find a power of 10 that guarantees a sum that is greater than that value. I wrote a simple script in Python that calculated S(1,10^k), according to formula (1), for some k and I found that k = 17 was enough.

          If you have any further questions, you can take a look at my last submission for this code or write a message.

          Regards

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

Can someone explain the greedy approach to Div.2 D / Div. 1 B Two Sets?

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

This round taught me a lesson and warned me about my deficiency in coding details. Besides I eventually understood that you may never think about getting more rating in Chinese Round. But actually it may not be the reason for not participating the contest, for the main purpose that we compete in CF isn't the for the rating. Even so, there will be a long time for me to regain my confident and to participate another round especially the Chinese Round.

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

Can anybody explain what is the flaw in my approach Solution ?

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

Can any one tell how to approach problems in competition so that it takes less time complexity and how to approach math problem fastly.

And what's the time complexity of program if i write n^2 solution to the problem in test case loop.

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

    There are no shortcut, you know what to do.

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

      What do u think about bold line .

      And what's the time complexity of program if i write n^2 solution to the problem in test case loop.

      → Reply