World Action Models 世界行動模型

 Current top-performing Vision-Language-Action models are good at understanding and generalizing across different semantic concepts, but they tend to fall short when encountering unfamiliar physical movements in new environments. This paper presents DreamZero, a new type of model called a World Action Model, which is built on top of a pre-trained video diffusion system. Rather than following the VLA approach, DreamZero learns how the physical world works by predicting what future states and actions will look like, treating video as a rich signal for how things change over time. By learning from both video and action data together, the model can pick up a wide variety of skills from mixed and diverse robot datasets without needing lots of repeated examples. In real-world robot tests, this leads to more than double the performance gains on new tasks and settings compared to leading VLA methods. The team also made significant engineering and algorithmic improvements that allow this large 14-billion-parameter model to run fast enough for real-time robot control at 7 frames per second. Beyond that, the paper shows two ways the model can transfer across different robot bodies: using video demonstrations from other robots or humans brings over a 42% relative boost on unseen tasks with only 10 to 20 minutes of data; and the model can adapt to an entirely new robot body with just 30 minutes of free-play data, while still performing well on tasks it has never explicitly trained for.

目前頂尖的視覺語言動作模型（VLA）擅長跨語義概念的理解與泛化，但在面對新環境中陌生的物理動作時往往表現不佳。本論文提出 DreamZero，一種新型模型，稱為世界動作模型（WAM），建構於預訓練的視頻擴散系統之上。與 VLA 的方式不同，DreamZero 透過預測未來的世界狀態與動作來學習物理世界的運作規律，將視頻視為世界隨時間演變的豐富訊號。藉由同時從視頻與動作資料中共同學習，該模型能夠從多樣化的異質機器人資料集中習得各式各樣的技能，而無需大量重複性示範。在真實機器人實驗中，相較於頂尖的 VLA 方法，DreamZero 在新任務與新環境上的表現提升超過兩倍。研究團隊同時在演算法與系統層面進行了大幅優化，使這個擁有 140 億參數的大型模型能夠以每秒 7 幀的速度執行實時機器人控制。此外，本論文展示了兩種跨機器人本體的遷移方式：利用來自其他機器人或人類的純視頻示範，僅需 10 至 20 分鐘的資料便能在未見任務上帶來超過 42% 的相對性能提升；更令人驚喜的是，模型僅需 30 分鐘的自由探索資料即可適應全新的機器人本體，同時仍能在從未明確訓練過的任務上保持出色的零樣本泛化能力。

UVa _ 10004 _ Bicoloring

 def is_bicolorable(adj_list, n):

    for start_node in range(n):

        color = [-1] * n        

        if color[start_node] != -1:

            continue

        # Iterative approach prevents stack overflow for large graphs

        stack = [(start_node, 0)] 

        color[start_node] = 0

        while stack:

            node, node_color = stack.pop()

            next_color = 1 - node_color  # Toggle between 0 and 1

            for neighbor in adj_list[node]:

                if color[neighbor] == -1:

                    color[neighbor] = next_color

                    stack.append((neighbor, next_color))

                elif color[neighbor] == node_color:  # Same color conflict

                    return False

    return True

while True:

    n = int(input())

    if n == 0:

        break

    m = int(input())

    adj_list = [[] for _ in range(n)] # Build adjacency list 

    for _ in range(m):

        a, b = map(int, input().split())

        adj_list[a].append(b)

        adj_list[b].append(a)

    print("BICOLORABLE." if is_bicolorable(adj_list, n) else "NOT BICOLORABLE.")

UVa _ 00532 _ Dungeon Master

 #include <iostream>

#include <queue>

#include <cstdio>

#include <cstring>

using namespace std;

const int MAXN = 32;

char dungeon[MAXN][MAXN][MAXN];

int Distance[MAXN][MAXN][MAXN];

int L, R, C;

const int direction[6][3] = {{-1, 0, 0}, {1, 0, 0}, {0, -1, 0},

                                     {0, 1, 0}, {0, 0, -1}, {0, 0, 1}};

struct point_type { int x; int y; int z; };

int BFS(int start_i, int start_j, int start_k) {

    // keypoint: Init Distance (-1 = not visited)

    for (int i = 0; i < L; ++i)

        for (int j = 0; j < R; ++j)

            for (int k = 0; k < C; ++k)

                Distance[i][j][k] = -1;

    // keypoint: BFS queue

    queue<point_type> q;

    q.push({start_i, start_j, start_k});

    Distance[start_i][start_j][start_k] = 0;

    while (!q.empty()) {

        point_type cur = q.front();

        q.pop();

        // keypoint: Found end

        if (dungeon[cur.x][cur.y][cur.z] == 'E')

            return Distance[cur.x][cur.y][cur.z];

        for (int i = 0; i < 6; ++i) {

            point_type nxt = {cur.x + direction[i][0], cur.y + direction[i][1], cur.z + direction[i][2]};

            // keypoint: Boundary check

            if (nxt.x < 0 || nxt.x >= L || nxt.y < 0 || nxt.y >= R || nxt.z < 0 || nxt.z >= C) continue;

            // keypoint: Wall check

            if (dungeon[nxt.x][nxt.y][nxt.z] == '#') continue;

            // keypoint: Visited check

            if (Distance[nxt.x][nxt.y][nxt.z] != -1) continue;

            Distance[nxt.x][nxt.y][nxt.z] = Distance[cur.x][cur.y][cur.z] + 1;

            q.push(nxt);

        }

    }

    return -1; // keypoint: No path

}

int main() {

    while (scanf("%d%d%d", &L, &R, &C) == 3) {

        if (!L && !R && !C) break;

        int start_i, start_j, start_k;

        for (int i = 0; i < L; ++i)

            for (int j = 0; j < R; ++j) {

                scanf("%s", dungeon[i][j]);

                for (int k = 0; k < C; ++k)

                    if (dungeon[i][j][k] == 'S')

                        start_i = i, start_j = j, start_k = k;

            }

        int minute = BFS(start_i, start_j, start_k);

        if (minute != -1)

            printf("Escaped in %d minute(s).\n", minute);

        else

            printf("Trapped!\n");

    }

    return 0;

}

UVa _11456 _ Trainsorting

 #include <iostream>

#include <vector>

using namespace std;

int findLongestSymmetricSubsequence(int sequenceLength) {

    // Create mirrored train sequence

    vector<int> symmetricSequence(sequenceLength * 2);

    // Track length of increasing subsequence for each position

    vector<int> subsequenceLengths(sequenceLength * 2, 1);

    int maxSubsequenceLength = 0;

    // Read and mirror the sequence

    for (int i = 0; i < sequenceLength; ++i) {

        int trainCarValue;

        cin >> trainCarValue;

        symmetricSequence[sequenceLength + i] = symmetricSequence[sequenceLength - i - 1] = trainCarValue;

    }

    // Find longest increasing subsequence

    for (int currentIndex = 0; currentIndex < sequenceLength * 2; ++currentIndex) {

        for (int prevIndex = 0; prevIndex < currentIndex; ++prevIndex) {

            // If current element is larger than previous, update subsequence length

            if (symmetricSequence[currentIndex] > symmetricSequence[prevIndex]) {

                subsequenceLengths[currentIndex] = max(

                    subsequenceLengths[currentIndex], 

                    subsequenceLengths[prevIndex] + 1

                );

            }

            // Track maximum subsequence length

            maxSubsequenceLength = max(maxSubsequenceLength, subsequenceLengths[currentIndex]);

        }

    }

    return maxSubsequenceLength;

}

int main() {

    // Optimize input/output performance

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);

    int numberOfTestCases;

    cin >> numberOfTestCases;

    // Process each test case

    while (numberOfTestCases--) {

        int trainLength;

        cin >> trainLength;

        // Solve and output result for current test case

        cout << findLongestSymmetricSubsequence(trainLength) << "\n";

    }

    return 0;

}

UVa _ 10336 _ Rank the Languages

 import sys

# Constants

MX = 10000

class Type:

    def __init__(self, id=None, value=0):

        self.id = id

        self.value = value

def comp(a):

    # Comparison function for sorting ranks

    # Primary sort: descending order of value (using negative to achieve descending)

    # Secondary sort: ascending order of id (in case of equal values)

    # Useful for ranking components by size and then by identifier

    return (-a.value, a.id)

def init(h, w):

    # Initialize a list of Type objects with default values

    # Creates an empty data structure of specified dimensions

    # Useful for pre-allocating space for graph-related data structures

    return [Type() for _ in range(h * w)]

def set_rank(ranks, c, r):

    for rank in ranks:

        if rank.id == c:

            rank.value += r

            return    

    new_rank = Type(id=c, value=r)

    ranks.append(new_rank)

def dfs_visit(graph, a, b, h, w):

    # Capturing the original color/type of the current cell before modification

    temp_c = graph[a][b]

    # label v as discovered

    # Mark the current cell as 'visited' to prevent re-exploration and avoid infinite recursion

    graph[a][b] = 'G'

    

    # Directional movements represent the possible traversal directions

    # These coordinates allow checking adjacent cells (left, up, right, down)

    dr = [0, -1, 0, 1]

    dc = [-1, 0, 1, 0]

    # for all directed edges from v to w that are in G.adjacentEdges(v) do

    # Iterate through all four possible adjacent directions

    for i in range(4):

        r = dr[i] + a

        c = dc[i] + b

        # if vertex w is not labeled as discovered then

        # Check if the adjacent cell is within graph boundaries and of the same color/type

        if (0 <= r < h and 0 <= c < w and 

            graph[r][c] == temp_c):

            # recursively call DFS(G, w)

            # Explore the connected component by recursively visiting adjacent cells

            dfs_visit(graph, r, c, h, w)

    # Mark the cell as completely explored to distinguish from undiscovered cells

    graph[a][b] = 'B'

def dfs(graph, h, w):

    # Initialize a list to store ranked components

    ranks = []

    # for all directed edges from v to w that are in G.adjacentEdges(v) do

    # Traverse through entire graph to find and explore connected components

    for i in range(h):

        for j in range(w): 

            # if vertex w is not labeled as discovered then

            # Check if the current cell hasn't been explored in previous DFS calls

            if graph[i][j] not in ['G', 'B']: 

                # Assign initial rank to the newly discovered component

                set_rank(ranks, graph[i][j], 1)  

                # recursively call DFS(G, w)

                # Start DFS from this undiscovered cell to explore its entire component

                dfs_visit(graph, i, j, h, w)

    return ranks

def process_world(h, w, graph_input):

    # Convert input to 2D list for easier manipulation

    graph = [list(row) for row in graph_input]

    # Perform depth-first search to identify and rank components

    ranks = dfs(graph, h, w)

    # Sort ranks in descending order of component size, with secondary sorting by component ID

    ranks.sort(key=comp)

    return ranks

test_cases = int(input())

cases = 0

for _ in range(test_cases):

    h, w = map(int, input().split())

    graph_input = [input() for _ in range(h)]

    cases += 1

    ranks = process_world(h, w, graph_input)

    print(f"World #{cases}")

    for rank in ranks:

        print(f"{rank.id}: {rank.value}")

SMASHIN' SCOPE

 SMASHIN’ SCOPE is an acronym, created by Tony Buzan, to assist with memorization:

• Synesthesia/Sensuality 
• Movement
• Association
• Sexuality
• Humor
• Imagination
• Numbers
• Symbolism
• Color
• Order and/or Sequence
• Positive Images
• Exaggeration

thread APIs for C/C++ : Creation & Synchronization

Threads share one address space (that is, they can all examine and modify the same variables). On the other hand, each thread has its own registers and execution stack pointer(執行堆疊), and perhaps private memory.

#include <iostream>

#include <condition_variable> // condition variable 條件變量

#include <thread>

#include <chrono>

 

std::condition_variable cv;

std::mutex cv_m;  // This mutex is used for three purposes:

                              // 1) to synchronize accesses to i

                              // 2) to synchronize accesses to std::cerr

                              // 3) for the condition variable cv

int i = 0;

void waits() //used by t1,t2 & t3

{

    std::unique_lock<std::mutex> lk(cv_m);

    std::cerr << "Waiting... \n";

    cv.wait(lk, []{return i == 1;}); //wait(lock)

    std::cerr << "...finished waiting. i == 1\n";

}

void signals()// used by thread t4

{

    std::this_thread::sleep_for(std::chrono::seconds(5));

    {

        std::lock_guard<std::mutex> lk(cv_m);

        std::cerr << "Notifying...\n";

    }

    cv.notify_all();

 

    std::this_thread::sleep_for(std::chrono::seconds(5));

    {

        std::lock_guard<std::mutex> lk(cv_m);

        i = 1;

        std::cerr << "Notifying again...\n";

    }

    cv.notify_all();

}

 

int main()

{

    std::thread t1(waits), t2(waits), t3(waits), t4(signals);

    t1.join(); 

    t2.join(); 

    t3.join();

    t4.join();

}

/*

Produce results in sequence: 

1.thread t1,t2,t3 are waiting

Waiting...

Waiting...

Waiting...

2. broadcast after 5 s

Notifying...

3. broadcast after another 5 s

Notifying again...

4. thread t1,t2,t3 are unlocked

...finished waiting. i == 1

...finished waiting. i == 1

...finished waiting. i == 1

*/