-emli-'s blog

By -emli-, 2 months ago, In English,

Two contests AtCoder Regular Contest 080 and AtCoder Beginner Contest 069 will be held at the same time.

You can participate in whichever contest you want. (However, you can't register to both competitions.) The last two tasks in ABC are the same as the first two tasks in ARC.

ABC is significantly easier than Div2 contest in TopCoder or Codeforces. If you can enjoy Div2 contests in TC or CF, I recommend you to participate in ARC.

Time: August 6th (Sunday), 21:00 JST

・Duration: 100 minutes

・Number of Tasks: 4

・Writer: sugim48

・Rating: ARC is rated for those who have rating < 2800. ABC is rated for those who have rating < 1200. (However, note that current rating is much lower than your actual strength — if you are green or brown, I recommend you to choose ARC.)

The point values will be announced later.

We are looking forward to your participation!

Let's discuss after the contest.

UPD:

The point values are announced.

It is 100 — 200 — 400 — 400 — 800 — 1200.

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

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can I see my " rating changes " after every contest at atcoder ???

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Click to competition history in user profile

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Hints for Problem E:Young Maids?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think toposort

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to solve it using toposort can you please explain?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        My idea is to fix the last pair which divides the aray into three parts. which we can assume as subtrees of that pair and then recurse that and find tree. For finding pair we use rmq.Now the answer will smallest lexicographical toposort of that tree assuming edges point downwards.

        PS: I think idea is correct but still untested

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Try to determine first two numbers in the answer. (Not first two pushed, but two in the real answer)

    Try to understand which pair can serve as second in the answer. This might lead to the solution.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it
    spoiler
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    think of the process in reverse , we must choose 2 indices first such that left one is odd and right one is even and split the range into 3 parts such that pairs now can not go from one part to another , this can be done with priority queue and segtree.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    I didn't manage to get AC during contest, so this might be wrong:

    For the first position in permutation q, it's obvious that you can put any number that is in an odd position in p. For the second position, you can put any number in an even position to the right of the first one.

    If you do this, you break the problem in (at most) three others (to the left of the first, between the first and the second and to the right of the second). You can solve this recursively and then merge the three answers. Finding the first two can be done using RMQ.

    I tested locally for extreme cases and it works fast, but I received TLE during contest, though.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I done it with set and segment tree https://pastebin.com/HYb6f0DV

    You have some intervals, everytime choose smallest element at odd position in some interval and than smallest even element at right side of the same interval. After it current interval split in three new intervals (and add their minimums on odd postion in set)...

    To process everything fast you should save information about erased elements in another set and also you should have segment tree with min at even/odd postions.

    Fine tasks, a little big gap between first two and rest, but I like it :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

sugim48 thanks for problems,I liked it, especially Grid Coloring that I solved with dfs.

»
2 months ago, # |
  Vote: I like it -10 Vote: I do not like it

How to solve Young Maids?

»
2 months ago, # |
  Vote: I like it -10 Vote: I do not like it

How to solve Prime Flip?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You can almost always find editorials a few minutes after the contest.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Task E is named incorrectly in editorial.

      Just to let you know

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      You are right. But what about discussing problems?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, of course, please discuss problems.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Achievement unlocked: work around compiler bugs during a contest!

I submitted for C but got mysterious CE, but the same code with a custom substitute for std::pair compiled normally. I asked the organizers and they also think this is likely a compiler bug. Perhaps I should send a bug report, if I get it right?

»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I really like atcoder, thanks for making it available in english (´・ω・`)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I found a bug in my problem C after submitting and getting an AC.

I wanted to re-submit my program after fixing the bug to make sure the new program still passed tests, but I was worried that would reduce my score.

Can someone clarify if re-submit after AC could reduce your score? Thanks!

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I don't believe it reduces your score after the contest is over. I resubmit the corrected code after almost every contest.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks but I meant DURING the contest. (Yes I should have been working on the next problem but I was curious anyway!)

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This should answer your question. It is from the AtCoder contest page. "When you solve a problem, you get a score assigned to it. Competitors are ranked first by total scores, then by penalties. The penalties are computed as (the time you spend to get your current score) + (5 minutes) * (the number of incorrect attempts). "

»
2 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

In editorial for problem F is a statement: (Strictly speaking, this is related to distribution of primes, for example we have to prove that arbitrary even number can be a difference of two primes. We confirmed this up to the constraints of the problem experimentally.)

Does it mean that authors got a pair of primes with difference X, for each even X up to 10^7?

I thought that for some X's, primes in such pair should be very big.

Edited: OK, I understand, they shouldn't.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks to authors for F problem! It is very exquisite solution, I enjoyed not even solving the problem! Thanks)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the AtCoder Beginner contest69, in the question C.4-adjacent

The testcase :

5 2 2 2 2 1

would fail if the below-mentioned code is used :

int main(){

int n, four, two, val;
four = two = 0;

scanf("%d", &n);
int tmp = n;
while(n--){
scanf("%d", &val);
if(val % 4 == 0) four++;
else if(val % 2 == 0) two++;

}

four += (two / 2);

if(four >= (tmp / 2)) puts("Yes");
else puts("No");

return 0;

}

Still, many people have got the problem right, even after using this code. What am I missing ?! Or this the case of weak test cases?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look my solution. It easy to understand.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      The answer that comes out of your algo is correct for the given test case ( 5 2 2 2 2 1 ) i.e "No". But the code that I mentioned was submitted by many people and the answer comes out to be "Yes" for the above mentioned test case. Still I believe because of weak testcases, it was granted as accepted or perhaps I did not understand the question completely. However, I too did get an AC with my code, which produces "No" as an answer.

      Whichever way, the above test case produces a different answer for my code and some other peoples code, still, all of us got AC!! Which means the given test case was missing.