Блог пользователя chokudai

Автор chokudai, история, 19 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +53
  • Проголосовать: не нравится

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
19 месяцев назад, # |
Rev. 3   Проголосовать: нравится +60 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

502 again:(

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why 502? Does the contest mode work?

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

Edit: I can still view standings btw.

»
19 месяцев назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

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!

»
19 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Unrated again :(

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The contest mode doesn't work...

»
19 месяцев назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится

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.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Whenever my contest is going good

Le Atcoder: Lets make it unrated

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится -25 Проголосовать: не нравится

    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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится -19 Проголосовать: не нравится

    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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Another unrated. Nooooooooooooo

»
19 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem G is a nice implementation problem

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    18 месяцев назад, # ^ |
    Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

    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
    • »
      »
      »
      18 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    Both this and previous round were sponsored rounds

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      18 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
18 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any simple explanation for problem F?

»
18 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?