dalex's blog

Codeforces Beta Round 76
By dalex, 13 years ago, In English

Hi all!

My name is Alexey Dergunov, and I'm glad to present you the first "violet" Codeforces round. I hope the problems will not seem so "violet" to you :)

Many thanks to following people who helped me a lot with contest preparation:

Good luck!

UPD. Contest is over, and we know the winners!

Division 1:
Division 2:
Congratulations!

UPD 2. Analysis: http://codeforces.net/blog/entry/2208 (English version is not full yet...)
  • Vote: I like it
  • +88
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it -6 Vote: I do not like it
gl & hf!
→ Reply
13 years ago, # |
← Rev. 3   Vote: I like it -19 Vote: I do not like it

I hope that the system tests and rating process is faster than the previous one :)  Good Luck :)
→ Reply
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
Yeah, me too. Violet would be very hard to read...
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Lets hope you impress us all with an impressive problem set =)
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
I cannot submit in Div 2 - it doesn't show any language available.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I can't select language. Why?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I also can't submit...
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
In div-2 problem B, what's the meaning of "there are no either three pairwise acquainted or three pairwise unacquainted people" ? would you please explain it more clearerly ?
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it
I managed to submit now, but it's like 30 minutes later...
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Admins please help, I cannot submit. When I click submit page keeps loading and nothing happens...
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it
    This isn't fair :(
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi, thanks for the round! I also didn't manage to submit with google chrome so I switched to firefox.

Regarding the problems, on div 2 problem C, I think the pretests were "too hard". Since codeforces allows for hacking of fellow competitors' solutions, you could have left some of those out of the pretests. I believe it was almost impossible to hack a solution that passed them.
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
When I see the problems as ugly as today's D, I want to quit the contest and do something useful.

I don't understand what are such problems doing in programming contests.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    What's the problem with D? It has two different solutions, one mathematical and one "straight-forward" without any math. So everyone should be happy :)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it
      The problem is that the author tried to compensate the straightforwardness of the problem with some ugly conditions to make the problem more time consuming.

      It happens when the author is afraid that the problems may be too easy for someone and the only goal is to make contestants spend more time. This is not what programming contest problems should be.

      I haven't read B and C because they looked ugly without reading them. Maybe I missed some great problems but what I've read and solved isn't what I enjoy in contests.

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        Yea, you missed good problem "C" =) I VERY like well-masked backtracking =)

        But concerning the rest of the contest - I totally agree with you...
        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So upset!!My english is very poor.I can't understand the meaning of "there are no either three pairwise acquainted or three pairwise unacquainted people" !

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

    Let 1,2,3 are three friend.
    Either all pairs (1,2), (2,3), (1,3) are acquainted each other or all pairs are unacquainted each other.


    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      But if there are four or five pairwise acquainted people ,what shall we do ?
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    At first I also could not understand it's meaning.

    If we create graph g where node is people and they are connected if those pair is acquainted, then find 3 people i,j,k such that g[i][j] ==  g[j][k] == g[k][i] == 1 or g[i][j] ==  g[j][k] == g[k][i] == 0. If those i, j, k are found, then WIN otherwise FAIL.

    I think the statement of div2 problem A and B is sometimes very hard to understand, but turns out very easy when understood. It just consumes time.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually, at first I can guess the meaning and my program is correct,but I always get wrong answer on pretext 2.So I focus on what is the meaning of this sentence.After the contest , I find out that I'm so careless,I print "FALL" instead of "FAIL".So careless I am!!!!

      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Poor description. It have cost 15minutes
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Any quick hint for E?

Seems like I've seen a couple of similar problems before - with different constraints.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    Nothing special. You should play with constraints a little bit.

    Use the recursive inclusion/exclusion as in similar problems and use memoization for small values.

    This problem was too boring for Div1-E as well.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I even couldn't solve D in previous contest , But This is the First E/Div 1 I think i can AC :( , But I ran out of time 
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I liked the contest.(Don't know about div 1)
If I could solve C , it would have been more interesting.(Seemed so easy )
:)
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

I personally liked the contest. Good job, dalex. Thank you :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My B failed on test 12:
50 1000 49

My code got answer "YES" on the server.
But it is weird the same code got "NO" on my machine.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    My AC solution also answers "YES". Maybe you are looking at wrong string in the report.
    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Although there is almost nothing new in algorithm, it's a good contest to test if you are carefully enough.

I think I should practice in some contests like this because I always make mistakes, such as today's Problem C, I make a really stupid mistake.

So, the contest is a little unusual, but also valuable.


[Edit]
By the way, my rating has no change after this contest: 2203 -> 2203.
It's a coincidence that my Rating of TopCoder for latest 3 contest is 2566 -> 2568 -> 2567, almost no change.

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For DIV2 C/DIV1 A, what is the expected result for input "21 3 6 11"?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    2
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      The layout is like this:
      1 2 3 
      4 5 6
      7 8 9
      10 11 12
      ...

      So I think 3 times is needed: first, choose 6; second, choose 7,8,9; third, 10, 11.
      Where is the error?

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        You can choose {6,9} and {7,8,10,11} after that.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Thanks. In the contest, I only consider choosing by an ENTIRE row which turn out to be wrong.
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            It was my bug for an hour, but, fortunately, I managed to find it :-)
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it +6 Vote: I do not like it
              This is the kind of test that should have been left out of the pretests, it would have been very good for hacks.
              → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    2
    Select 7,8,10,11 and 6,9.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Good Contest
→ Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Interesting problems, i hope there will be some analysis because i could solve only problem A.
→ Reply
13 years ago, # |
  Vote: I like it +11 Vote: I do not like it
@dalex, this is a nice contest. An editorial would be very helpful. Thank you. 
→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
The problems are of good quality. Thanks the author!
→ Reply
13 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

isn't it true that testcases for problem E missed the case when all numbers in array a is one and k is pretty big number?
I think many solutions would failed on this case.
Edit: sorry,this is wrong because numbers should be different.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Nice problemset, but A and B seemed hard to read for me (examples with explanation would be very helpful i think), through they were really easy to write when understood. But anyway, thanks for this contest.
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

My solution for div 1 A fails the 6th pretest, which is 21 5 1 21. Apparently the correct output is 1. 
During the contest I asked "In the first test case, can he select all the icons in one move?" and got as answer: "No, because they do not form a rectangle." The one who answered the question must have though that I am asking whether he can select the icons [a,b] in one move, and answered no (it was obvious that he can not in that test case select [a,b] with just one move, so I didn't think that anyone can understand the question that way), but what I wanted to know is whether he can select "all" the icons, [1,n] in one move, in a test case where n%m!=0. Just wanted to share what made me fail the problem, so that everyone can learn from it, and define their question better before they ask.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Now I realized that problems were easier. At the contest they seemed very difficult . REGRETTING :((
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My D for div 2 failed in the first pre test. Judge said it replied with a NO, while it correctly finds the answer in my machine. It's submission 521752, what can be wrong?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It happened with me in topcoder and later i found that i forgot to initialize my flag array with zero and judge gave me wa in 1st test.
    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it


→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Where to find the English version ？
→ Reply