Atef's blog

Codeforces Beta Round #83
By Atef, 13 years ago, In English
Hi all,

Today we would like to invite you to take part in round #83 inspired by the ACM practice sessions last year when Dima was visiting the German University in Cairo (GUC).

We have composed the problemset about life in Egypt and the GUC. Hope you will like it :)

The points for the problems in Div 1 & 2 will be: 500-1000-1500-2000-2500.

The writers of the problems are Dima and myself.

We would like to thank RAD, Connector, it4.kp, Delinur, and MikeMirzayanov, who greatly helped in preparing this contest.

We wish you a pleasant, educational and successful contest!

The editorial is under construction.

Good luck to everyone!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (67)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
No. of pariticipants Div 1 and Div 2 are imvalanced. 371 : 1006
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    if you want balance, you can solve problems better to be in Div 1
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Am i able to unregister now?   
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Of course you are!
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can just ignore the round without any consequences. The rating won't change unless you make at least one submission.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Oh great. So i'll just leave the contest. Anyway GoodLuck to u all :)
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      You can hack without submitting ?!
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        no, no
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Hacking needs Locking and Locking needs Submitting => Hacking needs Submitting
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I know I was just commenting on
          "The rating won't change unless you make at least one submission or hacking attempt."
          → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        No
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Oh, right, you cannot. I just remembered similar rule on TopCoder: you can make a challenge attempt without opening problems and have rating changed.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Doesn't this imply that you can read the problems and then decide if you want to participate?

          If I undesrtood correctly, doesn't seem really fair...
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Challenge phase does not allow coding.
            [Also, there is less chances that in just 15 minutes you will understand the question, then find the corner cases and verify others code.]
            → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            I think it is unfair too
            → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Every weekend , people from all over the world come together and solve some problems.[which are the same problems for each one of us]
            How about solving a BIG problem and everyone contributing a little in it.
            Just in 2 hrs solving a BIG problem, doesn't it sound interesting.?
            I appeal all red coders to think about it, is it possible for you guys to formulate one such problem and distribute it among all the people , so that everyone contribute his part , and finally a big task is done.
            [this will give more satisfaction and fun!]
            ......Just a thought :D
            → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If you dont submit anything,you wont be rated,no need to unregister.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It's very weird...
I swear that I've seen the time yesterday and it was 08/23/2011 08:00PM
I miss this game now....
I was torn!!!
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
when a solution gets hacked and a contestant resubmits.. is his code tested on the hacking test case also??
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In my opinion, this contest in div1 was not so good. Very easy problems A and B with really difficult problems C, D, E. As a result more that 200 participants solved A and B and only time to divide them. Of cource, I'm understand that it's really difficult to think of tasks.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I agree that the gap between number of submissions between B and C was huge, but I think it's really hard to measure difficulty on that fine level.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Are the Java solutions for problem A going to be rejudged?
I sent Java solution for problem A and I got "runtime error", I sent again the same solution few minutes after and I got Accepted, but I guess some points are lost for "wrong" submission.
I noticed the message during the contest that there was some problem with "runtime error" with Java solutions on task A. After the contest I saw that the my first "runtime error" solution was tested again, this time with "Accepted" but I think the points remained the same...
Thanks in advance

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Will the contest be "cancelled" for Java users ? I had to resubmit problem A without understanding what was wrong and my B and C failed too (I am not denying that they can be wrong... but it is hard to debug something when the systems preliminary test is not reliable).
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Sorry... I though the java issue was for ALL problems.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It would be unfair if the contest will be unrated.
    I've probably got my the highest place ever.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      what is the reason that the contest will be unrated.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Java issues.
        It seems that there won't be penalty points for some Java attempts but the whole contest will be rated so relax.
        → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I said : for Java coders.
      I enjoyed the problems :)
      → Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Please Everyone take a look --->

Which one is better translation ??

---------------------------------------------------------------------------------------------------
"Herr Wafa was also able to guarantee a spot on the team, using his special powers. But since he hates floating-point numbers, he needs your help at finding the probability that he will have at least one teammate belonging to his department."

OR

"Due to their paranormal abilities, Mr. Wafa knew that he really gets into the team GUC. Now he wants to calculate the probability that with him in the team will be at least one student in his department. Since he does not like to calculate with fractional numbers, the task entrusted to you. "
---------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------
In the third example, there are three possibilities to compose the team containing Herr Wafa. In two of them the other player from Herr Wafa's department is part of the team.

OR

In the third example, a team which includes Mr. Wafa, can be made in three ways, two of these three comprise the second player from the Faculty of Mr Wafa.
---------------------------------------------------------------------------------------------------

Comparison of problem setters translation and GOOGLE's translation.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why the System-testing didn't run yet?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Do I lose a lot of presision by writing
p *= (long double)a/b; instead of
p /= b;
p*=a; ?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Ok, I had AC with first approach. I just returned -1 instead of 0 when there was only 1 member of sh team...
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Так как во время контеста были некоторые проблемы с тестированием решений на Java, то в этом контесте все успешные, но не последние посылки (на претесты) не приводят к дополнительному штрафу, а игнорируются. Еще раз приносим извинения за доставленное неудобство.
=
Since during the contest, there were some troubles with testing Java solutions, all "pretests passed" (except last) submissions do not decrease score, such submissions are ignored. Once again, we apologize for any inconvenience.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Will it be rated?
    ===
    Будет ли контест рейтинговым?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It seems yes. It will be rated. If Java issue affected somebody for 10 minutes of more, we can make the contest unrated for him/her. This fact should be proved by submissions log.
      ===
      Похоже, что да. Контест будет рейтинговым. Если на кого-то сильно повлияла эта проблема (10 минут и более), то для него мы можем сделать участие внеконкурсным. Этот факт должен быть доказан логом посылок.
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It is written that such submissions are ignored, but having submitted the accepted solution at 19th minute (after the first ignored submission "00:16:40  Skipped [pretests]" at 16th minuted because of the problems with testing Java solutions) I get 412 points, and other coders get for example 458 points for accepted submission in the 21 minute...

    Will the submissions be rescored after the end of System Testing...?

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

What happenes, if I submit a task several times? (all pass pretests)
What if the first is correct submision, but not the second?
How score is calculated?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    What if the first is correct submision, but not the second?

    then you don't solve the problem
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Well, if there is no penalty for second correct submision, I might want to make several submisions "just in case", to make sure I get the right result.

      So, it is a good thing to know.
      I would assume there is a penalty for resubmision, but I wonder, what happens, if 1st submision is correct, but not the second...
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        THEN YOU'LL GET 0 POINTS FOR THIS PROBLEM!
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        System test will only test the last submission that passed the pretest,others will be skipped.
        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
problem D ,div 2
is it a Combinations problem?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anybody explain - why the answer for
7
1 2 3 4 8 16 32
in B (div 2) is Yes?

if we use x=6553510=11111111 11111111 2 we will get x*x=429483622510 = 11111111 11111110 00000000 00000001 which fits in 32 bits

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Because if we use 111 (2), which fits in 3 bits, we will get 111 * 111 = 110001 (2), which does not fit in 4 bits.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Ah !!! .. Misunderstood the problem !! Wish they had covered it in pretests or samples .. Its not fair to fail on nice easy problems.
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      thanks, now i understand..
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    yeah i don't understand it either. I died on the system test on same test case.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Try this case:
      3 3 5 12
      the answer should be "YES".
      I hacked 5 solutions with this case.

      (Edited)
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    (111)2=49 doesn't fit in 4 bits, so the answer is "Yes".
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      but 111 can fit in 8 bit, right?

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        sorry (111)2
        → Reply
        • 13 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Read this sentence carefully "If there exists an integer x, such that x fits in some type i(in ai bits) and x· x does not fit in some other type j (in aj bits) where ai < aj, then Tuftuf will stop using Gava."

          If there exists at least one pair (ai , aj) then the answer is "Yes".
          → Reply
      • 13 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Read carefully: if it "does not fit in some other type".
        → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    But (112)2 does not fit into 3 bits I think.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    even i failed on that test(61 test no.) but now it is clear to me.Thanks
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    But if we use x=310=112 which fits in 2 bits, we will get x2=910=10012, which doesn't feet in 3 bits.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
the test case for problem E in DivI I is so weak...
The passing java code during the contest didn't handle the 
case that there's a rectangle in a empty space surrounding by other rectangles..
Some Sample:

5

0 0 3 0 3 3 0 3

6 0 9 0 9 3 6 3

6 6 9 6 9 9 6 9

0 6 3 6 3 9 0 9

4 4 5 4 5 5 4 5

It gives 1.0571428571428572

obviously the answer is 1

→ Reply