chokudai's blog

By chokudai, history, 10 months ago, In English

We will hold Tokio Marine & Nichido Fire Insurance Programming Contest 2023(AtCoder Beginner Contest 299).

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

We have implemented a contest mode for our DDoS protection. Please read the following article before starting the contest.

https://atcoder.jp/posts/1022

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

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

we cannot access standings during ABC/ARC/AGC/AHC but can access standings after the contest ends right?

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

    I sometimes use the number of accepted solutions to predict the difficulty of a problem. Oh...

»
10 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Why can't we access standings during contest? Is it because of it takes a lot of load or sth?

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

    I guess that AT rating predictors are useless now xD

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

      Really useless indeed, now that every contest is unrated.

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

Not being able to access standings during the contest really sucks!

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

Can we see number of accepted submissions for a particular problem???

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

I don't understand how not being able to view standings protects against DDoS

»
10 months ago, # |
  Vote: I like it +14 Vote: I do not like it

502 again:(

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

    Is the platform stable enough? why 502 all the time?

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

Why 502? Does the contest mode work?

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

502 Bad Gateway?? I thought you guys added DDoS protection.

Edit: I can still view standings btw.

»
10 months ago, # |
  Vote: I like it +44 Vote: I do not like it

Obviously the hackers are targeting at the Atcoder. I think it would be better to extend some time and publish the problems here instead of just making unrated. And, add cloudflare please!

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

Had an off-by-one error in my sol for C, but got a 502 gateway error when I submitted it then resubmitted it thinking that the previous sol didnt submit.....resulting in two wrong submissions for C....

»
10 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Unrated again :(

Why are people attacking AtCoder? Do they really have nothing better to do?

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

    I think they are targeting at Chokudai. After Chokudai announces the improvement of the Anti-DDOS system, the attackers want to "show up" their muscles.

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

Unrated

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

The contest mode doesn't work...

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

Unrated???!! Two weeks in a row! I wait the entire week to give contest and now both weeks were wasted. Its not like other sites where contests are held multiple times a week, only one contest a week for which we clear our schedules. There should have been an improvement after the last contest got unrated. Both atcoder and codeforces need to have some serious server upgrades.

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

Whenever my contest is going good

Le Atcoder: Lets make it unrated

  • »
    »
    10 months ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    Same!! Thats why I am so angry, last week might have been a mistake but they should have been prepared this time. Atcoder holds only one or two contests a week, not easy to free time on weekends to attend these. This is completely unacceptable

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

    likely half of the rage are the ones who got notified of the contest going unrated while they were doing well, and the other half are the ones whose mindset got fucked by a hundred 502s

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

Another unrated. Nooooooooooooo

»
10 months ago, # |
  Vote: I like it +7 Vote: I do not like it

If the problem of DDOS on the programming competition platform cannot be solved, it will affect the entire programming competition field. I hope AtCoder can resolve this issue as soon as possible and provide a better participation experience for the vast number of participants.

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

How to solve problem G? My idea was something like this :

  1. Define $$$cnt_i$$$ : number of unique element from $$$i, i+1, ..., n$$$

  2. Now we iterate through $$$i$$$ from $$$1, 2, ..., n$$$ and do the following :

  3. We can add $$$A_i$$$ to $$$B$$$ if and only if :

  • Number of unique element from $$$i, i+1, ..., n$$$ is equal to the number of element that has not been taken to $$$B$$$ (that is : $$$cnt_i < size(B)$$$
  1. So I'm searching an interval using a binary search for an index $$$j$$$ such that all numbers between $$$i$$$ and $$$j$$$ are add-able to $$$B$$$

  2. Pick the minimum index $$$idx$$$ between $$$i$$$ and $$$j$$$ (inclusive) such that $$$A_{idx}$$$ has the smallest value between $$$A_i, A_{i+1}, ..., A_j$$$

  3. Add $$$A_{idx}$$$ to $$$B$$$

  4. Since we're taking $$$A_{idx}$$$ to $$$B$$$, therefore we can find the rightmost position of $$$A_{idx}$$$. Name this index as $$$last$$$, then we can subtract $$$cnt_{last}, cnt_{last+1}, ..., cnt_n$$$ (since now one element is taken to $$$B$$$, therefore number of unique element is decreased)

But I'm getting WA https://atcoder.jp/contests/abc299/submissions/40877152

Could someone point out : 1. The mistake on my idea 2. The bug on my code if my idea is correct ?

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

    Does problem F require DP or there exists a non DP solution?

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

Problem G is a nice implementation problem

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

In the problem E, Nearest Black Vertex, how they are claiming this

“The minimum distance from vertex v to a black vertex is exactly d” if and only if “there is a black vertex whose distance from vertex v is less than or equal to d” and “there is a black vertex whose distance from vertex v is strictly less than d.”

I am not getting this, could someone help me with this problem . As of now i have done kind of brute force stuff My Solution

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

    it should be “there is no black vertex whose distance from vertex v is strictly less than d.”

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

      Thanks for clarification, That was my interpretation too.

      What i did is that

      1. Precalculate all node which are a distance 'd' from the any node 'u'
      2. Wrote a recursive function and start with first (node, dist) pair and checking if we have any node which is less than dist and colored black , if so return false
      3. Else mark that node as black and recursively call the function for another pair of (node,dist)
      4. If we are able to reach at the end then return true

      I know this will give TLE as for a pair of (node,dist) we have checking for all d < dist if we have a black node or not but dont know how to optimize that

      Any help is appreciated. Thank you

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

        I would suggest understanding the editorial

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

I think problem F is very difficult for me, and I still can not fully understand the editorials. Would anyone like to share your ideas about this problem? Thank you so much.

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

    Maybe I'm a bit late but I'm sharing my solution anyways since it is a bit different from the editorial and I thought it was simplier. Maybe if you understand mine the editorial will be easier.

    In case you didn't want to see a different solution here is a small explanation of the trickier part of the editorial
    My solution
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      This solutions is awesome, your intuition is very natural as opposed to the editorial's solution.

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

I think there's been some miscommunication. Standings page was clearly visible for the duration of the contest! It's sad that the round went unrated. I don't know the reason for the DDOS, but could it be related to the round being sponsored? Both this and previous round were sponsored rounds, so maybe next one won't be targeted? In any case, AtCoder would need some stronger mechanism to deter the DDOS attack. CF added cloudflare check, but it's terrible right now, it slows access to contest pages, and checks every time you open a link. It's also costly. I hope there's some other way to solve this problem.

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

    Both this and previous round were sponsored rounds

    Actually the upcoming ABC is also sponsored, by UNIQUE VISION this time*

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

    I don't think it is straightforward to have an optimal solution for anti-DDOS unless some experienced experts exist in AtCoder. Imagine in a real company what a anti-DDOS project would cost? I guess the development cycle is surely longer than one week. Just give them some time. But I still don't get how/why AtCoder is the target. Maybe attack is aimless.

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

      I don't think so. They grasped the contest time so accurately. They started attacking after the contest and stop attacking just after the contest is announced unrated. That is the cheapest way. Besides, these guys do not give chokudai any chance to test the real-world attacks during the contests. The more countermeasures chokudai take, the more AtCoder would be attacked, the hackers (actually script guys) are showing off their muscles. If I were chokudai, I would publish the PDF version files on CF, dropbox. When the attacks happen, just extend some time.

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

Any simple explanation for problem F?

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

During ABC, ARC, AGC, and some AHC contests, access to all pages except for the contest will be restricted.

Does that mean we can view the standings of the running contest, but not past contests?